Η συνδυαστική είναι κλάδος των μαθηματικών που ασχολείται με τη μελέτη των πεπερασμένων και των άπειρων αλλά μετρήσιμων διακριτών δομών. Πτυχές με τις οποίες ασχολείται η συνδυαστική περιλαμβάνουν την καταμέτρηση των δομών ενός δεδομένου είδους και μεγέθους (απαριθμητική συνδυαστική), την απόφαση πότε μπορούν να πληρούν ορισμένα κριτήρια, την κατασκευή και την ανάλυση των αντικειμένων που πληρούν τα κριτήρια (όπως τα συνδυαστικά σχέδια και την θεωρία μιτροειδών ) την εύρεση "μεγαλύτερου", "μικρότερου" ή "βέλτιστου" αντικειμένου (extremal συνδυαστική και συνδυαστική βελτιστοποίησης) και την μελέτη συνδυαστικών δομών που προκύπτουν σε ένα αλγεβρικό πλαίσιο ή ερφαμόζοντας αλγεβρικές τεχνικές σε προβλήματα συνδυαστικής (αλγεβρική συνδυαστική).

Προβλήματα συνδυαστικής προκύπτουν σε πολλές περιοχές των καθαρών μαθηματικών, ιδίως στην άλγεβρα,θεωρία πιθανοτήτων,τοπολογία και την γεωμετρία και η συνδυαστική έχει επίσης πολλές εφαρμογές στη μαθηματική βελτιστοποίηση, επιστήμη των υπολογιστών, εργοδική θεωρία και στατιστική φυσική. Πολλές ερωτήσεις συνδυαστικής ιστορικά έχουν εξεταστεί μεμονωμένα, δίνοντας μια ad hoc λύση σε ένα πρόβλημα που ανακύπτει σε κάποιο μαθηματικό πλαίσιο. Μετά τον εικοστό αιώνα, ωστόσο έχουν αναπτυχθεί ισχυρές και γενικά θεωρητικές μέθοδοι, καθιστώντας την συνδυαστική ανεξάρτητο κλάδο των μαθηματικών από μόνη της, Ένα από τα παλαιότερα και πιο προσβάσιμα μέρη της συνδυαστικής είναι η θεωρία γραφών, η οποία έχει επίσης πολλές φυσικές συνδέσεις με άλλες περιοχές των μαθηματικών και αρκετές εφαρμογές. Η συνδυαστική χρησιμοποιείται συχνά στην επιστήμη των υπολογιστών για την απόκτηση φόρμουλων και εκτιμήσεων για την ανάλυση των αλγορίθμων.

Βασικές έννοιες συνδυαστικής και απαρίθμησης αποτελεσμάτων εμφανίστηκαν σε όλο τον αρχαίο κόσμο. Τον 6ο αιώνα π.Χ., η αρχαία ινδή ιατρός Sushruta ισχυρίστηκε στο Sushruta Samhita οτι 63 συνδυασμοί μπορούν να γίνουν από 6 διαφορετικές γεύσεις, λαμβάνοντας μια φορά, δύο φορές σε έναν χρόνο κλπ., υπολογίζοντας έτσι όλες τις 2⁶-1 δυνατότητες. Ο έλληνας ιστορίκος Πλούταρχος συζήτησε ένα επιχείρημα μεταξύ Χρύσιππου (3ο αιώνα π.Χ) και Ίππαρχου (2ο αιώνα π.Χ) από ένα αρκετά λεπτό απαριθμήσιμο πρόβλημα, το οποίο αργότερα φαίνεται ότι σχετίζεται με τους αριθμούς Schröder-Ίππαρχου.^[1][2][3] Στο Οστομάχιον, ο Αρχιμήδης (3ος αιώνας π.Χ) θεωρεί μια πλακόστρωση παζλ,^[4] ενώ συνδυαστικά θέματα μπορεί να υπήρχαν ήδη από τα έργα του Απολλωνίου.^[5][6]

Κατά τον μεσαίωνα, η συνδυαστική συνέχισε να μελετάται, σε μεγάλο βαθμό εκτός του ευρωπαϊκού πολιτισμού. Ο Ινδός μαθηματικός Μαχαβίρα (850 μ.Χ.) διατύπωσε τύπους για το πλήθος των μεταθέσεων και των συνδυασμών,^[7] και αυτοί οι τύποι μπορεί να ήταν γνωστοί στους Ινδούς μαθηματικούς ήδη από τον 6ο αιώνα μ.Χ.^[8] Ο φιλόσοφος και αστρονόμος ραβίνος Αβραάμ ιμπν Έζρα (1140) απέδειξε τη συμμετρία των διωνυμικών συντελεστών, ενώ ένας κλειστός τύπος βρέθηκε αργότερα από τον ταλμουδιστή και μαθηματικό Γερσονίδη (Gersonides) το 1321.^[9] Το αριθμητικό τρίγωνο - ένα γραφικό διάγραμμα που δείχνει τις σχέσεις μεταξύ των διωνυμικών συντελεστών - παρουσιάστηκε από τους μαθηματικούς σε πραγματείες που χρονολογούνται από τον 10ο αιώνα και τελικά εμεινε γνωστό ως το τρίγωνο του Πασκάλ. Αργότερα, στη μεσαιωνική Αγγλία, υπάρχουν παραδείγματα που σήμερα είναι γνωστα ως κύκλοι Χάμιλτον σε ορισμένα γραφήματα Κέιλι για τις μεταθέσεις.^[10][11]

Κατά τη διάρκεια της αναγέννησης, μαζί με τους υπόλοιπους κλάδους των μαθηματικών και των επιστημών, η συνδυαστική απολαμβάνει μια αναγέννηση. Τα έργα των Μπλεζ Πασκάλ, Ισαάκ Νεύτωνα, Γιακόμπ Μπερνούλι, και Λέοναρντ Όιλερ, ήταν θεμελιώδεις στον αναδυόμενο τομέα. Στη σύγχρονη εποχή, οι εργασίες του Τζέιμς Τζόσεφ Συλβέστερ (τέλη 19ου αιώνα) και του Πέρσι Αλεξάντερ Μακμέιχον (αρχές 20ου αιώνα) έθεσαν τα θεμέλια για την απαριθμιστική και την αλγεβρική συνδυαστική. Ταυτόχρονα, υπήρξε ραγδαία έκρηξη ενδιαφέροντος για την θεωρία γράφων, ειδικά σε σχέση με το θεώρημα των τεσσάρων χρωμάτων.

Στο δεύτερο μισό του 20ου αιώνα, η συνδυαστική απόλαυσε μια ταχεία ανάπτυξη, η οποία οδήγησε στην ίδρυση δεκάδων νέων περιοδικών και συνέδριων στον τομέα.^[12] Εν μέρει, η ανάπτυξη ήταν ωθούμενη από νέες συνδέσεις και εφαρμογές σε άλλους τομείς, που κυμαίνονται από την άλγεβρα στην θεωρία πιθανοτήτων, από τη συναρτησιακή ανάλυση στην θεωρία αριθμών, κ.λπ. Αυτές οι συνδέσεις έφεραν πιο κοντά την συνδυαστική και άλλους κλάδους των μαθηματικών και της θεωρητικής πληροφορικής, αλλά ταυτόχρονα οδήγησαν σε μερικό κατακερματισμό του τομέα.

Απαριθμητική συνδυαστική είναι η πιο κλασσική προσέγγιση της συνδυαστικής και επικεντρώνεται στην καταμέτρηση του πλήθους ορισμένων συνδυαστικών αντικειμένων (π.χ. πόσα δυαδικά δέντρα υπάρχουν για ${\displaystyle n}$ κορυφές).^[13] Αν και μετρώντας τον αριθμό των στοιχείων σε ένα σύνολο είναι ένα μάλλον ευρύ μαθηματικό πρόβλημα, που πολλά από τα προβλήματα που προκύπτουν σε εφαρμογές έχουν μια σχετικά απλή συνδυαστική περιγραφή. Οι αριθμοί Φιμπονάτσι είναι ένα βασικό πρόβλημα απαριθμητικής συνδυαστικής. Ο δωδεκαπλάσιος τρόπος παρέχει ένα ενιαίο πλαίσιο για την μέτρηση μεταθέσεων, συνδυασμών και χωρισμάτων.

Η αναλυτική συνδυαστική αφορά την απαρίθμηση των συνδυαστικών δομών χρησιμοποιώντας εργαλεία από την μιγαδική ανάλυση και τη θεωρία πιθανοτήτων. Σε αντίθεση με απαριθμητική συνδυαστική που χρησιμοποιεί σαφείς συνδυαστικούς τύπους και παραγωγήσιμες συναρτήσεις για να περιγράψει τα αποτελέσματα, η αναλυτική συνδυαστική στοχεύει στην απόκτηση ασυμπτωτικών αποτελεσμάτων.^[14]

Η θεωρία διαμέρισης μελετά διάφορα προβλήματα απαρίθμησης και ασυμπτωτικής που σχετίζονται με διαμέρισης ακεραίων αριθμών και συνδέεται στενά με q-σειρές, ειδικές συναρτήσεις και ορθογώνια πολυώνυμα. Αρχικά ήταν ένα μέρος της θεωρίας αριθμών και ανάλυσης, αλλά πλέον θεωρείται ένα τμήμα της συνδυαστικής ή ένα ανεξάρτητο πεδίο. Ενσωματώνει τις αμφιμονοσήμαντες αποδείξεις και διάφορα εργαλεία στην ανάλυση, στην αναλυτική θεωρία αριθμών και έχει διασυνδέσεις με την στατιστική μηχανική.

Οι γράφοι είναι βασικά αντικείμενα στη συνδυαστική. Οι ερωτήσεις κυμαίνονται από την καταμέτρηση (π.χ., ο αριθμός των γραφημάτων με ${\displaystyle n}$ κορυφές και ${\displaystyle k}$ ακμές) σε δομικές (π.χ., έχει ο γράφος ${\displaystyle G}$ έναν κύκλο Χάμιλτον) σε αλγεβρικές ερωτήσεις (π.χ., σε έναν γράφο ${\displaystyle G}$, ποια είναι η συνδυαστική ερμηνεία του πολυώνυμο Tutte ${\displaystyle \mathrm {T} _{G}(x,y)}$ για δύο αριθμούς ${\displaystyle x}$ και ${\displaystyle y}$;). Θα πρέπει να σημειωθεί ότι, ενώ υπάρχουν πολύ ισχυρές συνδέσεις μεταξύ της θεωρίας γράφων και της συνδυαστικής, αυτά τα δύο μερικές φορές θεωρούνται ξεχωριστεί κλάδοι των μαθηματικών.^[15]

Πεπερασμένη γεωμετρία είναι η μελέτη των γεωμετρικών συστημάτων που έχουν μόνο έναν πεπερασμένο αριθμό σημείων. Δομές ανάλογες με εκείνες που βρίσκονται σε συνεχείς γεωμετρίες (Ευκλείδειο επίπεδο, το πραγματικό προβολικό χώρο, κ.λπ.), αλλά ορίζονται συνδυαστικά είναι τα κύρια στοιχεία που μελετούνται. Αυτός ο τομέας είναι μια πλούσια πηγή παραδειγμάτων για την θεωρία σχεδιασμού. Δεν πρέπει να συγχέεται με τη διακριτή γεωμετρία (Συνδυαστική γεωμετρία).

Η θεωρία διάταξης ασχολείται με την μελέτη των μερικώς διατεταγμένων συνόλων πεπερασμένων αλλά και απείρου μεγέθους. Δίνει αυστηρούς ορισμούς σε διατυπώσεις "το Α είναι μεγαλύτερο του Β" ή το "Α προηγείται του Β". Διάφορα παραδείγματα της μερικής "διάταξης" εμφανίζονται στην άλγεβρα, τη γεωμετρία, τη θεωρία αριθμών και σε όλη την συνδυαστική και στη θεωρία γράφων. Ξεχωριστές τάξεις και παραδείγματα της μερικής διάταξης περιλαμβάνουν πλέγματα και την άλγεβρα Μπουλ.

Η θεωρία μητροειδών γενικεύει κάποια μέρη της γεωμετρίας. Μελετά τις ιδιότητες των συνόλων (συνήθως, πεπερασμένων) διανυσμάτων σε ένα διανυσματικό χώρο που δεν εξαρτώνται από τους ιδιαίτερους συντελεστές σε μια σχέση γραμμικής εξάρτησης. Όχι μόνο η δομή αλλά και οι απαριθμητικές ιδιότητες ανήκουν στη θεωρία μητροειδών. Η θεωρία εισήχθη από τον Χάσλερ Χουίτνεϋ και μελετήθηκε ως μέρος της θεωρίας διάταξης. Τώρα είναι ένας ανεξάρτητος τομέας της μελέτης με έναν αριθμό συνδέσεων με άλλα μέρη της συνδυαστικής αλλά και της ανάλυσης άπληστων αλγορίθμων.

Η συνδυαστική ακρότατων μελετά πόσο μεγάλο ή μικρό μπορεί να είναι ένα σύνολο πεπερασμένων αντικειμένων (αριθμοί, γράφοι, διανυσματικοί χώροι, σύνολα, κ.τ.λ.), αν πρέπει να ικανοποιεί κάποιους περιορισμούς. Μεγάλο μέρος της συνδυαστικής ακροτάτων αφορά κλάσεις από σύνολα συστημάτων. Για παράδειγμα, σε ένα σύνολο με ${\displaystyle n}$ στοιχεία, ποιο είναι το μεγαλύτερο πλήθος από υποσύνολα αποτελούμενα από k στοιχεία, έτσι ώστε ανά δύο να έχουν μη-κενή τομή; Ποιοι είναι το μεγαλύτερο πλήθος από υποσύνολα ώστε κανένα να μην περιέχει το άλλο; Στην τελευταία ερώτηση η απάντηση δίνεται από το θερώρημα του Σπένσερ, που είναι κεντρικό στα ακρότητα για την θεωρία συνόλων.

Αντίστοιχα ερωτήματα τίθενται στην θεωρία γράφων για το μεγαλύτερο δυνατό γράφο που ικανοποιεί κάποιους περιορισμούς. Για παράδειγμα, ο μεγαλύτερος γράφος χωρίς τρίγωνα σε 2n κορυφές είναι το πλήρες διμερές γράφημα K_n,n. Συχνά είναι πολύ δύσκολο να βρεθεί ακριβώς η απάντηση ${\displaystyle f(n)}$ και τότε γίνονται ασυμπτωτικές εκτιμήσεις.

Η θεωρία Ράμσεϋ είναι ένα άλλο μέρος της συνδυαστικής ακροτάτων. Αναφέρει ότι κάθε αρκετά μεγάλη διάταξη θα περιέχει κάποιο είδος της δομής. Πρόκειται για μια προηγμένη γενίκευση της αρχής της περιστεροφωλιάς.

Στην πιθανοθεωρητική συνδυαστική, τα ερωτήματα είναι του εξής τύπου: ποια είναι η πιθανότητα να ισχύει κάποια συγκεκριμένη ιδιότητα για ένα τυχαίο διακριτό αντικείμενο, όπως ένας τυχαίος γράφος; Για παράδειγμα, τί είναι ο μέσος αριθμός των τριγώνων σε έναν τυχαίο γράφο; Οι πιθανοτικές μέθοδοι που χρησιμοποιούνται επίσης για να διαπιστωθεί η ύπαρξη συνδυαστικών αντικειμένων με ορισμένες ιδιότητες (για τις οποίες γίνονται σαφή παραδείγματα μπορεί να είναι δύσκολο να βρει κανείς), απλά με την παρατήρηση ότι η πιθανότητα τυχαίας επιλογής ενός αντικειμένου με τις ιδιότητες αυτές είναι μεγαλύτερη από το μηδέν. Αυτή η μέθοδος (που συχνά αναφέρεται ως η πιθανοθεωρητική μέθοδος) αποδείχθηκε ιδιαίτερα αποτελεσματική σε εφαρμογές της συνδυαστικής ακρότατων και της θεωρίας γράφων. Μία στενά συνδεδεμένη περιοχή είναι η μελέτη των πεπερασμένων αλυσίδων Μαρκόφ, ειδικά σε συνδυαστικά αντικείμενα. Εδώ πάλι τα πιθανοθεωρητικά εργαλεία χρησιμοποιούνται για την εκτίμηση του χρόνου μίξης των αλυσίδων.

Συχνά σχετίζεται με τον Πολ Έρντος ο οποίος έκανε την πρωτοποριακή εργασία σχετικά με το θέμα, πιθανολογική συνδυαστική παραδοσιακά θεωρούνταν ως ένα σύνολο εργαλείων για τη μελέτη των προβλημάτων σε άλλα μέρη της συνδυαστικής. Ωστόσο, με την αύξηση των εφαρμογών στην ανάλυση αλγορίθμων στην θεωτική πληροφορική καθώς και άλλους τομής, η πιθανοθεωρητική συνδυαστική αναπτύχθηκε σε ανεξάρτητο τομέα της συνδυαστικής.

Η αλγεβρική συνδυαστική είναι μια περιοχή των μαθηματικών που χρησιμοποιεί την μέθοδο της αφηρημένης άλγεβρας, την θεωρία ομάδων και την θεωρία εκπροσώπησης, σε διάφορα συνδυαστικά πλαίσια και, αντιστρόφως, εφαρμόζονται τεχνικές συνδυαστικής για προβλήματα στην άλγεβρα. Η αλγεβρική Συνδυαστική συνεχώς επεκτείνεται στο πεδίο εφαρμογής της, και στα δύο θέματα και στις τεχνικές, και μπορεί να θεωρηθεί ως η περιοχή των μαθηματικών, όπου η αλληλεπίδραση της συνδυαστικής και των αλγεβρικών μεθόδων είναι ιδιαίτερα ισχυρή και σημαντική.

Η συνδυαστική στις λέξεις ασχολείται με τις τυπικές γλώσσες. Προέκυψε ανεξάρτητα, εντός διαφόρων κλάδων των μαθηματικών, συμπεριλαμβανομένων της θεωρίας αριθμών, της θεωρίας των ομάδων και των θεωρίας πιθανοτήτων. Έχει εφαρμογές στην απαριθμητική συνδυαστική, την ανάλυση φράκταλ, την θεωρητική πληροφορική, τη θεωρίας αυτομάτων και τη γλωσσολογία. Ενώ πολλές εφαρμογές είναι νέες, η κλασική ιεραρχία Τσόμσκι-Σάτσενμπέργκερ των τυπικών γραμματικών είναι ίσως το πιο γνωστό αποτέλεσμα στον τομέα.

Η γεωμετρική συνδυαστική σχετίζεται με την κυρτή και την διακριτή γεωμετρία (παλιότερα γνωστή ως συνδυαστική γεωμετρία), ιδίως η πολυεδρική συνδυαστική. Για παράδειγμα, ένα ερώτημα με το οποίο ασχολείται είναι πόσες έδρες σε κάθε διάσταση μπορεί να έχει ένα κυρτό πολύτοπο. Οι μετρικές ιδιότητες των πολυτόπων διαδραματίζουν σημαντικό ρόλο, καθώς, π.χ. το θεώρημα του Κωσύ για την ακαμψία των κυρτών πολυτόπων. Ειδικά πολύτοπα θεωρούνται επίσης, όπως permutohedra, associahedra και τα πολύτοπα Birkhoff.

Ανάλογα της συνδυαστικής τις έννοιες και μεθόδους της τοπολογίας χρησιμοποιούνται για τη μελέτη χρωματισμού γράφων, τις δίκαιες μοιρασιές, τους διαμερισμούς, τα μερικώς διατεταγμένα σύνολα, τα δέντρα αποφάσεων, το πρόβλημα μοιράσματος ενός περιδέραιου και τη διακριτή θεωρία Morse. Δεν πρέπει να συγχέεται με τη συνδυαστική τοπολογία, που είναι ένα παλαιότερο όνομα για την Αλγεβρική Τοπολογία .

Η αριθμητική συνδυαστική προέκυψε από την αλληλεπίδραση μεταξύ θεωρίας αριθμών, τη συνδυαστική, την εργοδική θεωρία και την αρμονική ανάλυση. Πρόκειται για εκτιμήσεις συνδυαστικής που σχετίζονται με αριθμητικές πράξεις (πρόσθεση, αφαίρεση, πολλαπλασιασμό και διαίρεση). Η πρόσθετη συνδυαστική αναφέρεται στην ειδική ερίπτωση, όταν μόνο οι πράξεις της πρόσθεσης και της αφαίρεσης εφαρμόζονται. Μια σημαντική τεχνική στην αριθμητική συνδυαστική είναι η εργοδική θεωρία των δυναμικών συστημάτων.

Η άπειρη συνδυαστική ή θεωρία συνδυαστικών συνόλων, είναι μια επέκταση των ιδεών της συνδυαστικής σε άπειρες σειρές. Είναι ένα μέρος της θεωρίας συνόλων, μιας περιοχής της μαθηματικής λογικής, αλλά χρησιμοποιεί τα εργαλεία και τις ιδέες τόσο από την θεωρία συνόλων όσο και από την συνδυαστική ακρότατων.

Η συνδυαστική βελτιστοποίηση είναι η μελέτη της βελτιστοποίησης σε διακριτά και συνδυαστικά αντικείμενα. Ξεκίνησε ως ένα μέρος της συνδυαστικής και της θεωρίας γράφων, αλλά θεωρείται πλέον ως κλάδος των εφαρμοσμένων μαθηματικών και της θεωρητικής πληροφορικής, που σχετίζονται με την επιχειρησιακή έρευνα, την ανάλυση αλγορίθμων και την θεωρία πολυπλοκότητας.

Η θεωρία κωδικοποίησης ξεκίνησε ως ένα μέρος της θεωρίας του σχεδιασμού με πρώιμες κατασκευές συνδυαστικής των κωδικων διόρθωσης σφαλμάτων. Η κύρια ιδέα του θέματος είναι να σχεδιαστούν αποτελεσματικές και αξιόπιστες μέθοδοι μετάδοσης δεδομένων που πλέον είναι ένα μεγάλο πεδίο μελέτης, μέρος της θεωρίας της πληροφορίας.

Η διακριτή γεωμετρία (ονομάζεται επίσης και συνδυαστική γεωμετρία) ξεκίνησε επίσης ένα μέρος της συνδυαστικής, με τα πρώτα αποτελέσματα σχετικά με τα κυρτά πολύτοπα και τους αριθμούς φιλιά.^[16] Με την εμφάνιση των εφαρμογών της διακριτής γεωμετρίας στην υπολογιστική γεωμετρία, τα δύο αυτά πεδία εν μέρει συγχωνεύτηκαν και έγιναν ένα ξεχωριστό πεδίο μελέτης. Εξακολουθούν να υπάρχουν πολλές συνδέσεις με τη γεωμετρική και την τοπολογική συνδυαστική, που οι ίδιες μπορούν να θεωρηθούν ως αποφύσεις της πρώιμης διακριτής γεωμετρίας.

Πτυχές συνδυαστικής των δυναμικών συστημάτων είναι ένας άλλος αναδυόμενος τομέας. Εδώ δυναμικά συστήματα μπορούν να οριστούν ως ατικείμενα συνδυαστικής. Δείτε για παράδειγμα διάγραμμα δυναμικού συστηματος.

Υπάρχουν αυξανόμενες αλληλεπιδράσεις μεταξύ της συνδυαστικής και της φυσικής, ιδιαίτερα της στατιστικής μηχανικής. Παραδείγματα περιλαμβάνουν μια ακριβή λύση του μοντέλου Ising, και μια σύνδεση μεταξύ του μοντέλου Potts από τη μια, και των χρωματικών πολυωνύμων και των πολυωνύμων Tutte από την άλλη.

Τα Wikimedia Commons έχουν πολυμέσα σχετικά με το θέμα    Συνδυαστική

• «Γρίφοι Συνδυασμών».