Συνδυαστική

Συνδυασμός
μετάθεση
επανάληψη



- Ένας Επιστημονικός Κλάδος των Μαθηματικών.
Ετυμολογία[]
Η ονομασία "Συνδυαστική" σχετίζεται ετυμολογικά με την λέξη "συνδυασμός".
Εισαγωγή[]
Η συνδυαστική είναι κλάδος των μαθηματικών που ασχολείται με τη μελέτη των πεπερασμένων και των άπειρων αλλά μετρήσιμων διακριτών δομών. Πτυχές με τις οποίες ασχολείται η συνδυαστική περιλαμβάνουν την καταμέτρηση των δομών ενός δεδομένου είδους και μεγέθους( Απαριθμήσιμη Συνδυαστική), την απόφαση πότε μπορούν να πληρούν ορισμένα κριτήρια, την κατασκευή και την ανάλυση των αντικειμένων που πληρούν τα κριτήρια(όπως τα συνδυαστικά σχέδια και την θεωρία Μάτροϊντ ) την εύρεση "μεγαλύτερου", "μικρότερου" ή "βέλτιστου" αντικειμένου (συνδυαστική extremal και συνδυαστική βελτιστοποίησης) και την μελέτη συνδυαστικών δομών που προκύπτουν σε ένα αλγεβρικό πλαίσιο ή ερφαμόζοντας αλγεβρικές τεχνικές σε προβλήματα συνδυαστικής (αλγεβρική συνδυαστική).
Προβλήματα συνδιαστικής προκύπτουν σε πολλές περιοχές των καθαρών μαθηματικών, ιδίως στην άλγεβρα,θεωρία πιθανοτήτων,τοπολογία και την γεωμετρία και η συνδυαστική έχει επίσης πολλές εφαρμογές στη μαθηματική βελτιστοποίηση, επιστήμη των υπολογιστών, ergodic θεωρία και στατιστική φυσική. Πολλές ερωτήσεις συνδυαστικής ιστορίκα έχουν εξεταστεί μεμονωμένα, δίνοντας μια ad hoc λύση σε ένα πρόβλημα που ανακύπτει σε κάποιο μαθηματικό πλαίσιο. Μετά τον εικοστό αιώνα, ωστόσο έχουν ανατπυχθεί ισχυρές και γενικά θεωρητικές μέθοδοι,καθιστώντας την συνδυαστική ανεξάρτητο κλάδο των μαθηματικών από μόνη της, Ένα από τα παλαιότερα και πιο προσβάσιμα μέρη της συνδυαστικής είναι η θεωρία γραφών, η οποία έχει επίσης πολλές φυσικές συνδέσεις με άλλες περιοχές. Η συδυαστική χρησιμοποίειται συχνά στην επιστήμη των υπολογιστών για την απόκτηση φόρμουλων και εκτιμήσεων για την ανάλυση των αλγορίθμων.
Ιστορία[]
Βασικές έννοιες συνδυαστικής και απαριθμήσιμων αποτελεσμάτων εμφανίστηκαν σε όλο τον αρχαίο κόσμο. Τον 6ο αιώνα π.Χ., η αρχαία ινδή ιατρός Sushruta ισχυρίστηκε στο Sushruta Samhita οτι 63 συνδυασμοί μπορούν να γίνουν από 6 διαφορετικές γεύσεις, λαμβάνοντας μια φορά, δύο φορές σε έναν χρόνο κλπ., υπολογίζοντας έτσι όλες 26-1 δυνατότητες.
Ο έλληνας ιστορίκος Πλούταρχος συζήτησε ένα επιχείρημα μεταξύ Χρύσιππου (3ο αιώνα π.Χ) και Ίππαρχου (2ο αιώνα π.Χ) από ένα αρκετά λεπτό απαριθμήσιμο πρόβληνα, το οποίο αργότερα φαίνεται ότι σχετίζεται οι Schröder αριθμοί. Στο Οστομάχιον, ο Αρχιμήδης(3ος αιώνας π.Χ) θεωρεί μια πλακόστρωση παζλ.
Κατά τον Μεσαίωνα, η Συνδυαστική συνέχισε να μελετάται, σε μεγάλο βαθμό εκτός του ευρωπαϊκού πολιτισμού. Ο ινδός μαθηματικός Μαχαβίρα (850) παρήγαγε φόρμουλες για τον αριθμό των μεταθέσεων και των συνδυασμών, και αυτοί οι τύποι μπορεί να είχαν εξοικειωθεί με τους Ινδούς μαθηματικούς ήδη από τον 6ο αιώνα μ.Χ. Ο φιλόσοφος και αστρονόμος ραβίνος Αβραάμ ιμπν Έζρα (1140) θέσπισε τη συμμετρία των διωνυμικών συντελεστών, ενώ ένας κλειστός τύπος ελήφθη αργότερα από τον ταλμουδιστή και μαθηματικό Gersonides το 1321.
Το αριθμητικό τρίγωνο- ένα γραφικό διάγραμμα που δείχνει τις σχέσεις μεταξύ των διωνυμικών συντελεστών- παρουσιάστηκε από τους μαθηματικούς σε πραγματείες που χρονολογούνται από τον 10ο αιώνα και τελικά θα γινόταν γνωστή ως τρίγωνο του Πασκάλ.
Αργότερα, στη μεσαιωνική Αγγλία, παρέχονται παραδείγματα του τι είναι τώρα γνωστή ως κύκλοι Χάμιλτον σε ορισμένα γραφήματα Κέιλι (Cayley) για μεταθέσεις.
Κατά τη διάρκεια της Αναγέννησης, μαζί με το υπόλοιπο των μαθηματικών και των επιστημών, συνδυαστική απολαμβάνουν μια αναγέννηση. Έργα των Μπλεζ Πασκάλ, Ισαάκ Νεύτωνα, Γιακόμπ Μπερνούλλι, και Λέοναρντ Όιλερ, έγινε θεμελιώδεις στον αναδυόμενο τομέα.Στη σύγχρονη εποχή, οι εργασίες του James Joseph Sylvester, τέλη 19ου αιώνα) και Percy Alexander MacMahon, αρχές 20ου αιώνα) έθεσε τα θεμέλια για enumerative και αλγεβρική συνδυαστική.
Η θεωρία γράφων απόλαυσε επίσης μια έκρηξη ενδιαφέροντος, ταυτόχρονα, ειδικά σε σχέση με το πρόβλημα των τεσσάρων χρωμάτων.
Στο δεύτερο μισό του 20ου αιώνα, η συνδυαστική απόλαυσε μια ραγδαία ανάπτυξη, η οποία οδήγησε στην ίδρυση δεκάδων νέων περιοδικών και συνέδριων για το θέμα αυτό.Εν μέρει, η ανάπτυξη ήταν ωθούμενη από νέους συνδυασμούς και εφαρμογές σε άλλους τομείς, που κυμαίνονται από άλγεβρα σε πιθανότητα, από τη Λειτουργική Ανάλυση σε θεωρία Αριθμών, κ.λπ.Αυτές οι συνδυασμοί έριξαν τα όρια μεταξύ της Συνδυαστικής και των μερών των μαθηματικών και της θεωρητικής επιστήμης των υπολογιστών, αλλά ταυτόχρονα οδήγησαν σε μερικό κατακερματισμό του τομέα.
Προσεγγίσεις και υποκατηγορίες συνδυαστικής[]
Απαριθμήσιμη Συνδυαστική[]
Απαριθμήσιμη συνδυαστική είναι η πιο κλασσική προσέγγιση της συνδυαστικής και επικεντρώνεται στην καταμέτρηση του αριθμού ορισμένων συνδυαστικών αντικειμένων. Αν και μετρώντας τον αριθμό των στοιχείων σε ένα σύνολο είναι ένα μάλλον ευρύ μαθηματικό πρόβλημα, που πολλά από τα προβλήματα που προκύπτουν σε εφαρμογές έχουν μια σχετικά απλή συνδυαστική περιγραφή. Οι αριθμοί Φιμπονάτσι είναι ένα βασικό πρόβλημα απαριθμήσιμης συνδυαστικής. Ο δωδεκαπλάσιος τρόπος παρέχει ένα ενιαίο πλαίσιο για την μέτρηση μεταθέσεων,συνδυασμών και χωρισμάτων.
Αναλυτική Συνδυαστική[]
Η αναλυτική Συνδυαστική αφορά την απαρίθμηση των συνδυαστικών δομών χρησιμοποιώντας εργαλεία από την ανάλυση και τη θεωρία Πιθανοτήτων.
Σε αντίθεση με απαριθμητική συνδυαστική που χρησιμοποιεί σαφείς συνδυαστικούς τύπους και παραγωγήσιμες συναρτήσεις για να περιγράψει τα αποτελέσματα, η αναλυτική Συνδυαστική στοχεύει στην απόκτηση ασυμπτωτικών μεθόδων.
Θεωρία Κατανομής[]
Η θεωρία κατανομής μελετά διάφορα προβλήματα απαρίθμησης και ασυμπτωτικής που σχετίζονται με ακέραια χωρίσματα και συνδέεται στενά με q-σειρές,ειδικές λειτουργίες και ορθογώνια πολυώνυμα. Αρχικά ένα μέρος της θεωρίας αριθμών και ανάλυσης, θεωρείται πλέον ένα μέρος της συνδυαστικής ή ένα ανεξάρτητο πεδίο. Ενσωματώνει την bijective προσέγγιση και διάφορα εργαλεία στην ανάλυση, στην αναλυτική θεωρία αριθμών και έχει διασυνδέσεις με την στατιστική μηχανική.
Θεωρία Γραφημάτων[]
Τα γραφήματα είναι βασικά αντικείμενα στη συνδυαστική. Οι ερωτήσεις κυμαίνονται από την καταμέτρηση (π.χ., ο αριθμός των γραφημάτων σε n κορυφές με ακμές k) σε διαρθρωτικές (π.χ., η οποία περιέχει γραφήματα κύκλους του Hamilton) σε αλγεβρικές ερωτήσεις (π.χ., δίνεται ένα γράφημα G και δύο αριθμοί x και y, κάνει το πολυώνυμο Τατ (Tutte) TG (x, y) έχει μια συνδυαστική ερμηνεία;).Θα πρέπει να σημειωθεί ότι, ενώ υπάρχουν πολύ ισχυρές συνδέσεις μεταξύ της θεωρίας γραφημάτων και της συνδυαστικής, αυτά τα δύο μερικές φορές θεωρούνται ως ξεχωριστά μαθήματα.
Πεπερασμένη Γεωμετρία[]
Πεπερασμένη γεωμετρία είναι η μελέτη των γεωμετρικών συστημάτων που έχουν μόνο έναν πεπερασμένο αριθμό σημείων.Δομές ανάλογες με εκείνες που βρίσκονται σε συνεχείς γεωμετρίες (Ευκλείδειο Επίπεδο, το πραγματικό προβολικό χώρο, κ.λπ.), αλλά ορίζονται συνδυαστικά είναι τα κύρια στοιχεία που μελετήθηκαν.Αυτή η περιοχή προσφέρει μια πλούσια πηγή παραδειγμάτων για την θεωρία Σχεδιασμού. Δεν πρέπει να συγχέεται με τη διακριτή γεωμετρία (Συνδυαστική Γεωμετρία).
Θεωρία Παραγγελίας[]
Θεωρία παραγγελίας είναι η μελέτη των μερικώς διατεταγμένων συνόλων των πεπερασμένων και απείρων. Διάφορα παραδείγματα της μερικής "παραγγελίας" εμφανίζονται στην άλγεβρα,στη γεωμετρία, θεωρία αριθμών και σε όλη την συνδυαστική και στη θεωρία γραφημάτων. Ξεχωριστές τάξεις και πραδείγματα της μερικής παραγγελίας περιλαμβάνουν πλέγματα και Boolean άλγεβρα.
Θεωρία Matroid[]
Η θεωρία Matroid γενικεύει κάποια μέρη της γεωμετρίας. Μελετά τις ιδιότητες των συνόλων (συνήθως, πεπερασμένα σύνολα ) των διανυσμάτων σε ένα διανυσματικό χώρο που δεν εξαρτώνται από τους ιδιαίτερους συντελεστές σε μια σχέση γραμμικής εξάρτησης. Οχι μονο η δομή αλλά και οι απαριθμητικές ιδιότητες ανήκουν στη θεωρία Matroid. Η θεωρία εισήχθη από τον Hassler Whitney και μελετήθηκε ως μέρος της θεωρίας τάξης. Τώρα είναι ένας ανεξάρτητος τομέας της μελέτης με έναν αριθμό συνδέσεων με άλλα μέρη της Συνδυαστικής .
Extremal Συνδυαστική[]
Η extremal συνδυαστική μελετά extremal ερωτήσεις σχετικά με ενα σύνολο συστημάτων. Οι τύποι των ερωτησέων που απευθύνονται σε αυτή την περίπτωση είναι περίπου όσο το δυνατόν μεγαλύτερο γράφημα το οποίο πληρεί ορισμένες ιδιότητες, Για παράδειγμα, το μεγαλύτερο τρίγωνο χωρίς γράφημα για δυο κορυφές είναι ένα πλήρες διμερές γράφημα Kn,n . Συχνά είναι πολύ δύσκολο ακόμη και να βρείτε την extremal απάντηση f(n) ακριβώς και κάποιος μόνο μπορεί να δωσει ασυμπτωτική εκτίμηση.
Θεωρία Ramsey είναι ένα άλλο μέρος της extremal συνδυαστικής. Αναφέρει ότι κάθε αρκετά μεγάλη διαμόρφωση θα περιέχει κάποιο είδος της παραγγελίας. Πρόκειται για μια προηγμένη γενίκευση της αρχής της θυρίδας.
Πιθανολογική Συνδυαστική[]
Στην πιθανολογική συνδυαστική, τα ερωτήματα είναι του εξής τύπου : ποια είναι η πιθανότητα σε μια ορισμένη ιδιότητα για ένα τυχαίο διακριτό αντικείμενο , όπως ένα τυχαίο γράφημα; Για παράδειγμα, τί είναι ο μέσος αριθμός των τριγώνων σε ένα τυχαίο γράφημα; Οι πιθανοτικές μέθοδοι που χρησιμοποιούνται επίσης για να διαπιστωθεί η ύπαρξη συνδυαστικών αντικειμένων με ορισμένες προδιαγεγραμμένες ιδιότητες ( για τις οποίες γίνονται σαφή παραδείγματα μπορεί να είναι δύσκολο να βρει κανείς), απλά με την παρατήρηση ότι η πιθανότητα τυχαίας επιλογής ενός αντικειμένου με τις ιδιότητες αυτές είναι μεγαλύτερη από μηδέν .Αυτή η προσέγγιση ( που συχνά αναφέρεται ως η πιθανολογική μέθοδος ) αποδείχθηκε ιδιαίτερα αποτελεσματική σε εφαρμογές της συνδυαστικής άκρων και της θεωρίας γραφημάτων . Μία στενά συνδεδεμένη περιοχή είναι η μελέτη των πεπερασμένων αλυσίδων Μαρκόφ, ειδικά σε συνδυαστικά αντικείμενα. Εδώ πάλι τα πιθανολογικά εργαλεία χρησιμοποιούνται για την εκτίμηση του χρόνου ανάμιξης.
Συχνά σχετίζεται με τον Πολ Έρντος ο οποίος έκανε την πρωτοποριακή εργασία σχετικά με το θέμα, πιθανολογική συνδυαστική παραδοσιακά θεωρούνταν ως ένα σύνολο εργαλείων για τη μελέτη των προβλημάτων σε άλλα μέρη της συνδυαστικής. Ωστόσο , με την αύξηση των αιτήσεων για την ανάλυση των αλγορίθμων στην επιστήμη των υπολογιστών , καθώς επίσης και την κλασική πιθανότητα πρόσθετης ύλης και τη πιθανολογική θεωρία αριθμών, η περιοχή πρόσφατα αναπτύχθηκε για να γίνει ένας ανεξάρτητος τομέας της Συνδυαστικής .
Αλγεβρική Συνδυαστική[]
Η αλγεβρική συνδυαστική είναι μια περιοχή των μαθηματικών που χρησιμοποιεί την μέθοδο της αφηρημένης άλγεβρας, την θεωρία ομάδων και την θεωρία εκπροσώπησης, σε διάφορα συνδυαστικά πλαίσια και, αντιστρόφως, εφαρμόζονται τεχνικές συνδυαστικής για προβλήματα στην άλγεβρα. Η αλγεβρική Συνδυαστική συνεχώς επεκτείνεται στο πεδίο εφαρμογής της, και στα δύο θέματα και στις τεχνικές, και μπορεί να θεωρηθεί ως η περιοχή των μαθηματικών, όπου η αλληλεπίδραση της συνδυαστικής και των αλγεβρικών μεθόδων είναι ιδιαίτερα ισχυρή και σημαντική.
Συνδυαστική σε λέξεις[]
Η Συνδυαστική στις λέξεις ασχολείται με τις επίσημες γλώσσες. Προέκυψε ανεξάρτητα, εντός διαφόρων κλάδων των μαθηματικών , συμπεριλαμβανομένων της θεωρίας Αριθμών, της θεωρίας της ομάδας και των πιθανοτήτων. Έχει εφαρμογές σε απαριθμητική συνδυαστική, ανάλυση φράκταλ, θεωρητική επιστήμη των υπολογιστών , στη θεωρίας αυτομάτων και στη γλωσσολογία . Ενώ πολλές εφαρμογές είναι νέες, η κλασσική ιεραρχία Τσόμσκι-Σάτσενμπέργκερ (Chomsky–Schützenberger) των ομάδων τυπικών γραμματικών είναι ίσως το καλύτερο γνωστό αποτέλεσμα στον τομέα .
Γεωμετρική Συνδυαστική[]
Η γεωμετρική Συνδυαστική σχετίζεται με κυρτά και με διακριτή γεωμετρία, ιδίως πολυεδρική Συνδυαστική. Μελετά, για παράδειγμα, πόσες έδρες σε κάθε διάσταση μπορεί να έχει ένα κυρτό πολύτοπο.
Οι μετρικές ιδιότητες polytopes διαδραματίζουν σημαντικό ρόλο, καθώς, π.χ. το θεώρημα Cauchy για την ακαμψία των κυρτών polytopes.
Ειδικές polytopes θεωρούνται επίσης, όπως permutohedra, associahedra και Birkhoff polytopes. Θα πρέπει να σημειώσουμε ότι η Συνδυαστική Γεωμετρία είναι ένα παλαιό όνομα για Διακριτή Γεωμετρία.
Τοπολογική Συνδυαστική[]
Η Συνδυαστική ανάλογα με τις έννοιες και μεθόδους της Τοπολογίας χρησιμοποιούνται για τη μελέτη χρωματισμού γραφήματος, τη Δίκαιη Κατανομή ,τα χωρίσματα, τα μερικώς διατεταγμένα σύνολα, τα δέντρα απόφασης, προβλήματα αλυσίδας και διακριτή Morse θεωρία. Δεν πρέπει να συγχέεται με τη Συνδυαστική Τοπολογία, που είναι ένα παλαιότερο όνομα για την Αλγεβρική Τοπολογία .
Αριθμητική Συνδυαστική[]
Η αριθμητική συνδυαστική προέκυψε απο την αλληλεπίδραση μεταξύ θεωρίας αριθμών, συνδυαστική θεωρία, Εργοδηγική Θεωρία και Αρμονική Ανάλυση. Πρόκειται για εκτιμήσεις συνδυαστικής που σχετίζονται με αριθμητικές πράξεις (πρόσθεση, αφαίρεση, πολλαπλασιασμό και διαίρεση). Η πρόσθετη συνδυαστική αναφέρεται στην ειδική περίπτωση, όταν μόνο οι πράξεις της πρόσθεσης και της αφαίρεσης εφαρμόζονται. Μια σημαντική τεχνική στην αριθμητική συνδυαστική είναι η Εργοδηγική Θεωρία των δυναμικών συστημάτων.
Άπειρη Συνδυαστική[]
Η άπειρη συνδυαστική ή θεωρία συνδυαστικών συνόλων, είναι μια επέκταση των ιδεών της Συνδυαστικής σε άπειρες σειρές. Είναι ένα μέρος της θεωρίας Συνόλων, μιας περιοχής της μαθηματικής Λογικής, αλλά χρησιμοποιεί τα εργαλεία και τις ιδέες τόσο από την θεωρία των συνόλων όσο και από την extremal Συνδυαστική.
Σχετικά πεδία[]
Συνδυαστική Βελτιστοποίηση[]
Η Συνδυαστική Βελτιστοποίηση είναι η μελέτη της βελτιστοποίησης σε διακριτά και συνδυαστικά αντικείμενα. Ξεκίνησε ως ένα μέρος της Συνδυαστικής και της θεωρίας Γραφημάτων, αλλά θεωρείται πλέον ως κλάδος των εφαρμοσμένων μαθηματικών και της επιστήμης των υπολογιστών, που σχετίζονται με την Επιχειρησιακή Έρευνα, την Θεωρία Αλγορίθμων και την θεωρία Πολυπλοκότητας.
Θεωρία Κωδικοποίησης[]
Η θεωρία Κωδικοποίησης άρχισε ως ένα μέρος της θεωρίας του σχεδιασμού με πρώιμες κατασκευές Συνδυαστικής των κωδικων διόρθωσης σφαλμάτων. Η κύρια ιδέα του θέματος είναι να σχεδιασθούν αποτελεσματικές και αξιόπιστες μέθοδοι μετάδοσης δεδομένων που πλέον είναι ένα μεγάλο πεδίο μελέτης, μέρος της θεωρίας της πληροφορίας.
Διακριτή Γεωμετρία και Υπολογιστική Γεωμετρία[]
Η Διακριτή Γεωμετρία (ονομάζεται επίσης Συνδυαστική Γεωμετρία) άρχισε επίσης ένα μέρος της Συνδυαστικής, με τα πρώτα αποτελέσματα σχετικά με το κυρτό polytopes και τους αριθμούς. Με την εμφάνιση των εφαρμογών της διακριτής γεωμετρίας στην υπολογιστική γεωμετρία, τα δύο αυτά πεδία εν μέρει συγχωνεύθηκαν και έγιναν ένα διακριτό πεδίο μελέτης. Εξακολουθούν να υπάρχουν πολλές συνδέσεις με τη γεωμετρική και την Τοπολογική Συνδυαστική, που οι ίδιες μπορούν να θεωρηθούν ως αποφύσεις της πρώιμης διακριτής γεωμετρίας.
Συνδυαστική και Δυναμικά Συστήματα[]
Πτυχές Συνδυαστικής των δυναμικών συστημάτων είναι ένας άλλος αναδυόμενος τομέας. Εδώ δυναμικά συστήματα μπορούν να οριστούν ως αντικείμενα Συνδυαστικής. Δείτε για παράδειγμα Διάγραμμα Δυναμικού Συστήματος.
Συνδυαστική και Φυσική[]
Υπάρχουν αυξανόμενες αλληλεπιδράσεις μεταξύ της Συνδυαστικής και της Φυσικής, ιδιαίτερα της Στατιστικής Φυσικής. Παραδείγματα περιλαμβάνουν μια ακριβή λύση του μοντέλου Ising, και μια σύνδεση μεταξύ του μοντέλου Potts από τη μια πλευρά, και της χρωματικής και των πολυωνύμων Tutte από την άλλη.
Θεματογραφία[]
- Αλγεβρική Συνδυαστική
- Κρυπτογραφία
- Binomial Coefficient
- Bracketing
- Combinatorial Identity
- Combinatorial Optimization
- Configuration
- Cover
- Design
- Enumeration
- General Combinatorics
- Lattice Path and Polygon
- Partition
- Permutation
- Weighing
Υποσημειώσεις[]
Εσωτερική Αρθρογραφία[]
- Μαθηματική Λογική
- Μαθηματικά
- συνδυασμός (combination)
- μετάθεση (permutation)
Βιβλιογραφία[]
Ιστογραφία[]
![]() ![]() |
---|
Αν και θα βρείτε εξακριβωμένες πληροφορίες "Οι πληροφορίες αυτές μπορεί πρόσφατα Πρέπει να λάβετε υπ' όψη ότι Επίσης, |
- Μην κάνετε χρήση του περιεχομένου της παρούσας εγκυκλοπαίδειας
αν διαφωνείτε με όσα αναγράφονται σε αυτήν
- Όχι, στις διαφημίσεις που περιέχουν απαράδεκτο περιεχόμενο (άσεμνες εικόνες, ροζ αγγελίες κλπ.)