Προβολή πηγαίου κώδικα για τη σελίδα Συνδυαστική

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

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

==  Ιστορία ==
Βασικές έννοιες συνδυαστικής και απαρίθμησης αποτελεσμάτων εμφανίστηκαν σε όλο τον [[Αρχαία Ιστορία|αρχαίο κόσμο]]. Τον 6ο αιώνα π.Χ., η [[αρχαία ινδία|αρχαία ινδή]] [[ιατρός]] [[Sushruta]] ισχυρίστηκε στο [[Sushruta Samhita]] οτι 63 συνδυασμοί μπορούν να γίνουν από 6 διαφορετικές γεύσεις, λαμβάνοντας μια φορά, δύο φορές σε έναν χρόνο κλπ., υπολογίζοντας έτσι όλες τις 2<sup>6</sup>-1 δυνατότητες. Ο [[έλληνας]] [[ιστορίκος]] [[Πλούταρχος]] συζήτησε ένα επιχείρημα μεταξύ [[Χρύσιππος ο Σολεύς|Χρύσιππου]] (3ο αιώνα π.Χ) και [[Ίππαρχος ο Ρόδιος|Ίππαρχου]] (2ο αιώνα π.Χ) από ένα αρκετά λεπτό απαριθμήσιμο πρόβλημα, το οποίο αργότερα φαίνεται ότι σχετίζεται με τους [[αριθμοί Schröder-Ίππαρχου|αριθμούς Schröder-Ίππαρχου]].<ref>{{Cite journal|last=Acerbi|first=F.|title=On the shoulders of Hipparchus|url=https://link.springer.com/article/10.1007/s00407-003-0067-0|journal=Archive for History of Exact Sciences|year=2003|volume=57|issue=6|pages=465–502|doi=10.1007/s00407-003-0067-0|s2cid=122758966|access-date=2021-03-12|archive-date=2022-01-23|archive-url=https://web.archive.org/web/20220123111759/https://link.springer.com/article/10.1007%2Fs00407-003-0067-0|url-status=live}}</ref><ref>[[Richard P. Stanley|Stanley, Richard P.]]; "Hipparchus, Plutarch, Schröder, and Hough", ''American Mathematical Monthly'' '''104''' (1997), no. 4, 344–350.</ref><ref>{{cite journal |doi=10.1080/00029890.1998.12004906 |title=On the Second Number of Plutarch |url=https://archive.org/details/sim_american-mathematical-monthly_1998-05_105_5/page/446 |year=1998 |last1=Habsieger |first1=Laurent |last2=Kazarian |first2=Maxim |last3=Lando |first3=Sergei |journal=The American Mathematical Monthly |volume=105 |issue=5 |pages=446 }}</ref> Στο [[Οστομάχιον]], ο [[Αρχιμήδης]] (3ος αιώνας π.Χ) θεωρεί μια [[πλακόστρωση παζλ]],<ref>{{Cite journal|last1=Netz|first1=R.|last2=Acerbi|first2=F.|last3=Wilson|first3=N.|title=Towards a reconstruction of Archimedes' Stomachion|url=https://www.sciamvs.org/2004.html|journal=Sciamvs|volume=5|pages=67–99|access-date=2021-03-12|archive-date=2021-04-16|archive-url=https://web.archive.org/web/20210416095205/https://www.sciamvs.org/2004.html|url-status=live}}</ref> ενώ συνδυαστικά θέματα μπορεί να υπήρχαν ήδη από τα έργα του [[Απολλώνιος ο Περγαίος|Απολλωνίου]].<ref>{{Cite journal|last=Hogendijk|first=Jan P.|date=1986|title=Arabic Traces of Lost Works of Apollonius|url=https://www.jstor.org/stable/41133783|journal=Archive for History of Exact Sciences|volume=35|issue=3|pages=187–253|doi=10.1007/BF00357307|jstor=41133783|s2cid=121613986|issn=0003-9519|access-date=2021-03-26|archive-date=2021-04-18|archive-url=https://web.archive.org/web/20210418221029/https://www.jstor.org/stable/41133783|url-status=live}}</ref><ref>{{Cite journal|last=Huxley|first=G.|date=1967|title=Okytokion|url=https://grbs.library.duke.edu/article/view/11131/4205|journal=Greek, Roman, and Byzantine Studies|volume=8|issue=3|pages=203|access-date=2021-03-26|archive-date=2021-04-16|archive-url=https://web.archive.org/web/20210416100956/https://grbs.library.duke.edu/article/view/11131/4205|url-status=live}}</ref>

Κατά τον [[Μεσαίωνας|μεσαίωνα]], η συνδυαστική συνέχισε να μελετάται, σε μεγάλο βαθμό εκτός του [[Ευρωπαϊκός πολιτισμός|ευρωπαϊκού πολιτισμού]]. Ο Ινδός μαθηματικός [[Μαχαβίρα]] (850 μ.Χ.) διατύπωσε τύπους για το πλήθος των [[μεταθέσεων]] και των [[συνδυασμών]],<ref>{{cite book |last=Puttaswamy |first=Tumkur K. |contribution=The Mathematical Accomplishments of Ancient Indian Mathematicians |editor-last=Selin |editor-first=Helaine |title=Mathematics Across Cultures: The History of Non-Western Mathematics |publisher=Kluwer Academic Publishers |location=Netherlands |url=https://books.google.com/books?id=2hTyfurOH8AC |year=2000 |isbn=978-1-4020-0260-1 |page=417 <!-- pages 409–422 --> |access-date=2015-11-15 |archive-date=2021-04-16 |archive-url=https://web.archive.org/web/20210416100852/https://books.google.com/books?id=2hTyfurOH8AC |url-status=live }}</ref> και αυτοί οι τύποι μπορεί να ήταν γνωστοί στους Ινδούς μαθηματικούς ήδη από τον 6ο αιώνα μ.Χ.<ref>{{cite journal | last1 = Biggs | first1 = Norman L. | year = 1979 | title = The Roots of Combinatorics | journal = Historia Mathematica | volume = 6 | issue = 2| pages = 109–136 | doi=10.1016/0315-0860(79)90074-0| doi-access = free }}</ref> Ο [[φιλόσοφος]] και [[αστρονόμος]] ραβίνος [[Αβραάμ ιμπν Έζρα]] (1140) απέδειξε τη συμμετρία των [[διωνυμικός συντελεστής|διωνυμικών συντελεστών]], ενώ ένας κλειστός τύπος βρέθηκε αργότερα από τον ταλμουδιστή και [[Μαθηματικός|μαθηματικό]] [[Γερσονίδη]] (''Gersonides'') το 1321.<ref>{{citation|title=Probability Theory: A Historical Sketch|first=L.E.|last=Maistrov|publisher=Academic Press|year=1974|isbn=978-1-4832-1863-2|url=https://books.google.com/books?id=2ZbiBQAAQBAJ&pg=PA35|page=35|access-date=2015-01-25|archive-date=2021-04-16|archive-url=https://web.archive.org/web/20210416091311/https://books.google.com/books?id=2ZbiBQAAQBAJ&pg=PA35|url-status=live}}. (Translation from 1967 Russian ed.)</ref> Το αριθμητικό τρίγωνο - ένα γραφικό διάγραμμα που δείχνει τις σχέσεις μεταξύ των διωνυμικών συντελεστών - παρουσιάστηκε από τους μαθηματικούς σε πραγματείες που χρονολογούνται από τον 10ο αιώνα και τελικά εμεινε γνωστό ως το [[τρίγωνο του Πασκάλ]]. Αργότερα, στη μεσαιωνική Αγγλία, υπάρχουν παραδείγματα που σήμερα είναι γνωστα ως [[κύκλοι Χάμιλτον]] σε ορισμένα [[γραφήματα Κέιλι]] για τις μεταθέσεις.<ref>{{cite journal |doi=10.1080/00029890.1987.12000711 |title=Ringing the Cosets |url=https://archive.org/details/sim_american-mathematical-monthly_1987-10_94_8/page/721 |year=1987 |last1=White |first1=Arthur T. |journal=The American Mathematical Monthly |volume=94 |issue=8 |pages=721–746 }}</ref><ref>{{cite journal |doi=10.1080/00029890.1996.12004816 |title=Fabian Stedman: The First Group Theorist? |url=https://archive.org/details/sim_american-mathematical-monthly_1996-11_103_9/page/771 |year=1996 |last1=White |first1=Arthur T. |journal=The American Mathematical Monthly |volume=103 |issue=9 |pages=771–778 }}</ref>

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

Στο δεύτερο μισό του 20ου αιώνα, η συνδυαστική απόλαυσε μια ταχεία ανάπτυξη, η οποία οδήγησε στην ίδρυση δεκάδων νέων περιοδικών και συνέδριων στον τομέα.<ref>Δείτε [http://www.math.iit.edu/~kaul/Journals.html#CGT Journals in Combinatorics and Graph Theory] {{Webarchive|url=https://web.archive.org/web/20210217150357/http://www.math.iit.edu/~kaul/Journals.html#CGT |date=2021-02-17 }}</ref> Εν μέρει, η ανάπτυξη ήταν ωθούμενη από νέες συνδέσεις και εφαρμογές σε άλλους τομείς, που κυμαίνονται από την άλγεβρα στην [[θεωρία πιθανοτήτων]], από τη [[συναρτησιακή ανάλυση]] στην [[θεωρία αριθμών]], κ.λπ. Αυτές οι συνδέσεις έφεραν πιο κοντά την συνδυαστική και άλλους κλάδους των μαθηματικών και της [[θεωρητική πληροφορική|θεωρητικής πληροφορικής]], αλλά ταυτόχρονα οδήγησαν σε μερικό κατακερματισμό του τομέα.

== Προσεγγίσεις και υποκατηγορίες συνδυαστικής ==

[[Image:Catalan 4 leaves binary tree example.svg|320px|right|thumb|Πέντε [[Δυαδικό δέντρο|δυαδικά δέντρα]] σε τρεις κορυφές (δείτε επίσης τους [[αριθμός Κάταλαν|αριθμούς Κάταλαν]]).]]

=== Απαριθμητική συνδυαστική ===
Απαριθμητική συνδυαστική είναι η πιο κλασσική προσέγγιση της συνδυαστικής και επικεντρώνεται στην καταμέτρηση του πλήθους ορισμένων συνδυαστικών αντικειμένων (π.χ. πόσα [[Δυαδικό δέντρο|δυαδικά δέντρα]] υπάρχουν για <math>n</math> κορυφές).<ref>{{cite web |last=Αθανασιάδης |first=Χρήστος |title=Αλγεβρική και απαριθμητική συνδυαστική |url=http://users.uoa.gr/~caath/book.pdf |publisher=Τμήμα Μαθηματικών, Πανεπιστήμιο Αθηνών |accessdate=13 Νοεμβρίου 2023}}</ref> Αν και μετρώντας τον αριθμό των στοιχείων σε ένα σύνολο είναι ένα μάλλον ευρύ [[μαθηματικά|μαθηματικό]] [[πρόβλημα]], που πολλά από τα προβλήματα που προκύπτουν σε εφαρμογές έχουν μια σχετικά απλή συνδυαστική περιγραφή. Οι [[αριθμοί Φιμπονάτσι]] είναι ένα βασικό πρόβλημα απαριθμητικής συνδυαστικής. Ο [[δωδεκαπλάσιος τρόπος]] παρέχει ένα ενιαίο πλαίσιο για την [[μέτρηση μεταθέσεων]], [[Συνδυασμός (μαθηματικά)|συνδυασμών]] και [[χώρισμα|χωρισμάτων]].

=== Αναλυτική συνδυαστική ===
Η αναλυτική συνδυαστική αφορά την απαρίθμηση των συνδυαστικών δομών χρησιμοποιώντας εργαλεία από την [[μιγαδική ανάλυση]] και τη [[θεωρία πιθανοτήτων]]. Σε αντίθεση με απαριθμητική συνδυαστική που χρησιμοποιεί σαφείς συνδυαστικούς τύπους και [[παραγωγήσιμη συνάρτηση|παραγωγήσιμες συναρτήσεις]] για να περιγράψει τα αποτελέσματα, η αναλυτική συνδυαστική στοχεύει στην απόκτηση [[ασυμπτωτική μέθοδος|ασυμπτωτικών αποτελεσμάτων]].<ref>{{cite book |last=Flajolet |first=Philippe |title=Analytic combinatorics |publisher=Cambridge Univ. Press |location=Cambridge |isbn=978-0521898065 |edition=4th pr |author2=Sedgewick, Robert}}</ref>

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

=== Θεωρία γράφων ===
{{Κύριο|θεωρία γράφων}}
Οι γράφοι είναι βασικά αντικείμενα στη συνδυαστική. Οι ερωτήσεις κυμαίνονται από την καταμέτρηση (π.χ., ο αριθμός των γραφημάτων με <math>n</math> κορυφές και <math>k</math> ακμές) σε δομικές (π.χ., έχει ο γράφος <math>G</math> έναν [[κύκλος Χάμιλτον|κύκλο Χάμιλτον]]) σε αλγεβρικές ερωτήσεις (π.χ., σε έναν [[γράφος|γράφο]] <math>G</math>, ποια είναι η συνδυαστική ερμηνεία του [[πολυώνυμο Tutte]] <math>\mathrm{T}_G(x, y)</math> για δύο αριθμούς <math>x</math> και <math>y</math>;). Θα πρέπει να σημειωθεί ότι, ενώ υπάρχουν πολύ ισχυρές συνδέσεις μεταξύ της θεωρίας γράφων και της συνδυαστικής, αυτά τα δύο μερικές φορές θεωρούνται ξεχωριστεί κλάδοι των μαθηματικών.<ref>Sanders, Daniel P.; [http://www.math.gatech.edu/~sanders/graphtheory/writings/2-digit.html ''2-Digit MSC Comparison''] {{webarchive|url=https://web.archive.org/web/20081231163112/http://www.math.gatech.edu/~sanders/graphtheory/writings/2-digit.html |date=2008-12-31 }}</ref>

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

[[Image:Hasse diagram of powerset of 3.svg|thumb|right|150px|Ένα [[διάγραμμα Hasse]] ενός [[δυναμοσύνολο|δυναμοσυνόλου]] <math>\{ x, y, z \}</math> με την σχέση του [[Υποσύνολο|υποσυνόλου]].]]
=== Θεωρία διάταξης ===
{{Κύριο|Θεωρία διάταξης}}
Η θεωρία διάταξης ασχολείται με την μελέτη των [[μερικώς διαταταγμένο σύνολο|μερικώς διατεταγμένων συνόλων]] πεπερασμένων αλλά και απείρου μεγέθους. Δίνει αυστηρούς ορισμούς σε διατυπώσεις "το Α είναι μεγαλύτερο του Β" ή το "Α προηγείται του Β". Διάφορα παραδείγματα της μερικής "διάταξης" εμφανίζονται στην [[άλγεβρα]], τη [[γεωμετρία]], τη [[θεωρία αριθμών]] και σε όλη την συνδυαστική και στη θεωρία γράφων. Ξεχωριστές τάξεις και παραδείγματα της μερικής διάταξης περιλαμβάνουν [[πλέγμα]]τα και την [[άλγεβρα Μπουλ]].

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

[[File:RamseyTheory_K5_no_mono_K3.svg|right|thumb|Ένα από τα θεωρήματα στην θεωρία Ράμσεϋ λέει ότι μεταξύ οποιονδήποτε έξι ατόμων, θα υπάρχουν τρεις που είτε όλοι γνωρίζονται μεταξύ τους είτε όλοι δεν γνωρίζονται μεταξύ τους (δήλαδή θα υπάρχει ένα τρίγωνο του ίδιου χρώματος). Και αυτό δεν ισχύει για <math>n = 5</math>]]

=== Συνδυαστική ακρότατων ===
Η συνδυαστική ακρότατων μελετά πόσο μεγάλο ή μικρό μπορεί να είναι ένα σύνολο πεπερασμένων αντικειμένων ([[αριθμός|αριθμοί]], [[Γράφος|γράφοι]], [[Δυανισματικός χώρος|διανυσματικοί χώροι]], [[σύνολο|σύνολα]], κ.τ.λ.), αν πρέπει να ικανοποιεί κάποιους περιορισμούς. Μεγάλο μέρος της συνδυαστικής ακροτάτων αφορά [[Κλάση (θεωρία συνόλων)|κλάσεις]] από [[σύνολο συστημάτων|σύνολα συστημάτων]]. Για παράδειγμα, σε ένα σύνολο με <math>n</math> στοιχεία, ποιο είναι το μεγαλύτερο πλήθος από [[υποσύνολο|υποσύνολα]] αποτελούμενα από ''k'' στοιχεία, έτσι ώστε ανά δύο να έχουν μη-[[κενό σύνολο|κενή]] [[Τομή συνόλων|τομή]];  Ποιοι είναι το μεγαλύτερο πλήθος από υποσύνολα ώστε κανένα να μην περιέχει το άλλο;  Στην τελευταία ερώτηση η απάντηση δίνεται από το [[θερώρημα του Σπένσερ]], που είναι κεντρικό στα ακρότητα για την θεωρία συνόλων.

Αντίστοιχα ερωτήματα τίθενται στην [[θεωρία γράφων]] για το μεγαλύτερο δυνατό γράφο που ικανοποιεί κάποιους περιορισμούς.  Για παράδειγμα, ο μεγαλύτερος γράφος χωρίς τρίγωνα σε ''2n'' κορυφές είναι το [[πλήρες διμερές γράφημα]] ''K<sub>n,n</sub>''. Συχνά είναι πολύ δύσκολο να βρεθεί ακριβώς η απάντηση <math>f(n)</math> και τότε γίνονται [[ασυμπτωτικές]] εκτιμήσεις.

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

[[Image:Self avoiding walk.svg|thumb|right|150px|Ένας [[τυχαίος περίπατος]] που αποφεύγει τα σημεία που έχει επισκεφθεί σε ένα [[πλέγμα]].]]
=== Πιθανοθεωρητική συνδυαστική ===
Στην [[πιθανοθεωρητική συνδυαστική]], τα ερωτήματα είναι του εξής τύπου: ποια είναι η πιθανότητα να ισχύει κάποια συγκεκριμένη ιδιότητα για ένα τυχαίο διακριτό αντικείμενο, όπως ένας τυχαίος [[γράφος]]; Για παράδειγμα, τί είναι ο [[αναμενόμενη τιμή|μέσος αριθμός]] των τριγώνων σε έναν [[τυχαίο γράφημα|τυχαίο γράφο]]; Οι πιθανοτικές μέθοδοι που χρησιμοποιούνται επίσης για να διαπιστωθεί η ύπαρξη συνδυαστικών αντικειμένων με ορισμένες ιδιότητες (για τις οποίες γίνονται σαφή παραδείγματα μπορεί να είναι δύσκολο να βρει κανείς), απλά με την παρατήρηση ότι η πιθανότητα τυχαίας επιλογής ενός αντικειμένου με τις ιδιότητες αυτές είναι μεγαλύτερη από το [[μηδέν]]. Αυτή η μέθοδος (που συχνά αναφέρεται ως η [[πιθανοθεωρητική μέθοδος]]) αποδείχθηκε ιδιαίτερα αποτελεσματική σε εφαρμογές της συνδυαστικής ακρότατων και της [[θεωρία γράφων|θεωρίας γράφων]]. Μία στενά συνδεδεμένη περιοχή είναι η μελέτη των πεπερασμένων [[Αλυσίδα Μαρκόφ|αλυσίδων Μαρκόφ]], ειδικά σε συνδυαστικά αντικείμενα. Εδώ πάλι τα πιθανοθεωρητικά εργαλεία χρησιμοποιούνται για την εκτίμηση του χρόνου μίξης των αλυσίδων.

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

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

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

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

[[Image:Collier-de-perles-rouge-vert.svg|150px|thumb|right|Το [[πρόβλημα μοιράσματος ενός περιδέραιου]] σε δύο τμήματα.]]
=== Τοπολογική συνδυαστική ===
Ανάλογα της συνδυαστικής τις έννοιες και μεθόδους της [[τοπολογία]]ς χρησιμοποιούνται για τη μελέτη [[χρωματισμός γραφήματος|χρωματισμού γράφων]], τις [[δίκαιη μοιρασιά|δίκαιες μοιρασιές]], τους [[διαμερισμός συνόλου|διαμερισμούς]], τα [[μερικώς διατεταγμένο σύνολο|μερικώς διατεταγμένα σύνολα]], τα [[δέντρο απόφασης|δέντρα αποφάσεων]], το [[πρόβλημα μοιράσματος ενός περιδέραιου]] και τη [[διακριτή θεωρία Morse]]. Δεν πρέπει να συγχέεται με τη [[συνδυαστική τοπολογία]], που είναι ένα παλαιότερο όνομα για την [[Αλγεβρική Τοπολογία]] .

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

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

== Σχετικά πεδία ==

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

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

=== Διακριτή και υπολογιστική Γεωμετρία ===
Η διακριτή γεωμετρία (ονομάζεται επίσης και συνδυαστική γεωμετρία) ξεκίνησε επίσης ένα μέρος της συνδυαστικής, με τα πρώτα αποτελέσματα σχετικά με τα κυρτά πολύτοπα και τους [[αριθμός φιλί|αριθμούς φιλιά]].<ref>{{cite book |title=Combinatorial Geometry |author1=János Pach |author2=Pankaj K. Agarwal |publisher=John Wiley & Sons |year=1995 |isbn=9781118031360 }}</ref> Με την εμφάνιση των εφαρμογών της διακριτής γεωμετρίας στην [[υπολογιστική γεωμετρία]], τα δύο αυτά πεδία εν μέρει συγχωνεύτηκαν και έγιναν ένα ξεχωριστό πεδίο μελέτης. Εξακολουθούν να υπάρχουν πολλές συνδέσεις με τη γεωμετρική και την τοπολογική συνδυαστική, που οι ίδιες μπορούν να θεωρηθούν ως αποφύσεις της πρώιμης διακριτής γεωμετρίας.

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

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

== Παραπομπές ==
<references />

== Εξωτερικοί σύνδεσμοι ==
{{commonscat}}
* {{cite web|title= Γρίφοι Συνδυασμών|url= http://grifoi.org/syndyasmvn.html}}


{{Μαθηματικά-υποσέλιδο}}
{{Portal bar|Μαθηματικά}}

[[Κατηγορία:Διακριτά μαθηματικά]]
[[Κατηγορία:Συνδυαστική| ]]