Συνδυασμοί με επαναλήψεις στοιχείων. Συνδυαστικοί αλγόριθμοι: δείκτης συνδυασμού, δείκτης διαμερισμάτων υποσυνόλου Φέρνοντας τους αλγόριθμους σε σταθερή πολυπλοκότητα
Όλα τα N στοιχεία, και κανένα δεν επαναλαμβάνονται, τότε αυτό είναι ένα πρόβλημα σχετικά με τον αριθμό των μεταθέσεων. Η λύση μπορεί να βρεθεί απλή. Η πρώτη θέση στη σειρά μπορεί να είναι οποιοδήποτε από τα N στοιχεία, επομένως, υπάρχουν N επιλογές. Στη δεύτερη θέση - οποιοδήποτε, εκτός από αυτό που έχει ήδη χρησιμοποιηθεί για την πρώτη θέση. Επομένως, για καθεμία από τις N επιλογές που έχουν ήδη βρεθεί, υπάρχουν (N - 1) επιλογές δεύτερης θέσης και ο συνολικός αριθμός συνδυασμών γίνεται N*(N - 1).
Το ίδιο μπορεί να επαναληφθεί και για τα υπόλοιπα στοιχεία της σειράς. Για την τελευταία θέση, απομένει μόνο μία επιλογή - το τελευταίο στοιχείο που απομένει. Για την προτελευταία υπάρχουν δύο επιλογές κ.ο.κ.
Επομένως, για μια σειρά Ν μη επαναλαμβανόμενων στοιχείων, οι πιθανές μεταθέσεις είναι ίσες με το γινόμενο όλων των ακεραίων από το 1 έως το Ν. Το γινόμενο αυτό ονομάζεται παραγοντικό του Ν και συμβολίζεται με Ν! (διαβάστε "en factorial").
Στην προηγούμενη περίπτωση, ο αριθμός των πιθανών στοιχείων και ο αριθμός των θέσεων στη σειρά συνέπιπταν και ο αριθμός τους ήταν ίσος με N. Αλλά μια κατάσταση είναι δυνατή όταν υπάρχουν λιγότερες θέσεις στη σειρά από ό, τι είναι πιθανά στοιχεία. Με άλλα λόγια, ο αριθμός των στοιχείων στο δείγμα είναι ίσος με έναν ορισμένο αριθμό M και M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Αρχικά, μπορεί να θέλετε να μετρήσετε τον συνολικό αριθμό των πιθανών τρόπων με τους οποίους μπορούν να τακτοποιηθούν σε μια σειρά στοιχεία M από το N. Αυτοί οι τρόποι ονομάζονται ρυθμίσεις.
Δεύτερον, ο ερευνητής μπορεί να ενδιαφέρεται για τον αριθμό των τρόπων με τους οποίους μπορούν να επιλεγούν στοιχεία M από το N. Στην περίπτωση αυτή, η σειρά των στοιχείων δεν είναι πλέον σημαντική, αλλά οποιεσδήποτε δύο επιλογές πρέπει να διαφέρουν μεταξύ τους κατά τουλάχιστον ένα στοιχείο . Τέτοιες μέθοδοι ονομάζονται συνδυασμοί.
Για να βρείτε τον αριθμό των τοποθετήσεων των στοιχείων M από το N, μπορείτε να καταφύγετε στην ίδια μέθοδο συλλογισμού όπως στην περίπτωση των μεταθέσεων. Μπορεί ακόμα να υπάρχουν N στοιχεία στην πρώτη θέση, N - 1 στη δεύτερη θέση, και ούτω καθεξής. Αλλά για την τελευταία θέση, ο αριθμός των πιθανών επιλογών δεν είναι ίσος με μία, αλλά (N - M + 1), αφού όταν ολοκληρωθεί η τοποθέτηση, θα εξακολουθούν να υπάρχουν (N - M) αχρησιμοποίητα στοιχεία.
Έτσι, ο αριθμός των τοποθετήσεων των στοιχείων Μ από το Ν είναι ίσος με το γινόμενο όλων των ακεραίων από (Ν - Μ + 1) έως Ν, ή, τι είναι το ίδιο, το πηλίκο Ν!/(Ν - Μ)!.
Προφανώς, ο αριθμός των συνδυασμών των στοιχείων Μ από το Ν θα είναι μικρότερος από τον αριθμό των τοποθετήσεων. Για κάθε πιθανό συνδυασμό υπάρχει ένα Μ! πιθανές τοποθετήσεις ανάλογα με τη σειρά των στοιχείων αυτού του συνδυασμού. Επομένως, για να βρείτε αυτή την ποσότητα, πρέπει να διαιρέσετε τον αριθμό των τοποθετήσεων των στοιχείων M από το N με το N!. Με άλλα λόγια, ο αριθμός των συνδυασμών των στοιχείων Μ από το Ν ισούται με Ν!/(Μ!*(Ν - Μ)!).
Ένας συνδυασμός είναι μια αδιάτακτη επιλογή στοιχείων ενός πεπερασμένου συνόλου με σταθερό αριθμό και χωρίς επαναλήψεις στοιχείων. Οι διαφορετικοί συνδυασμοί πρέπει να διαφέρουν σε τουλάχιστον ένα στοιχείο και η σειρά των στοιχείων δεν έχει σημασία. Για παράδειγμα, από το σύνολο όλων των φωνηέντων των λατινικών γραμμάτων (AEIOU), μπορείτε να κάνετε 10 διαφορετικούς συνδυασμούς 3 γραμμάτων, σχηματίζοντας τις ακόλουθες μη ταξινομημένες τρίδυμες:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Είναι ενδιαφέρον να σημειωθεί ότι από τα ίδια πέντε γράμματα μπορείτε επίσης να λάβετε 10 διαφορετικούς συνδυασμούς αν τους συνδυάσετε 2 γράμματα τη φορά, δημιουργώντας τα ακόλουθα μη ταξινομημένα ζεύγη:
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
Ωστόσο, εάν συνδυάσετε τα ίδια φωνήεντα λατινικά γράμματα κατά 4, θα λάβετε μόνο τους ακόλουθους 5 διαφορετικούς συνδυασμούς:
AEIO, AEIU, AIOU, EIOU, AEOU.
Σε γενικές γραμμές, για να δηλώσουμε τον αριθμό των συνδυασμών n διαφορετικών στοιχείων των m στοιχείων, χρησιμοποιείται ο ακόλουθος συναρτητικός, δείκτης ή διανυσματικός συμβολισμός (Appel):
Ανεξάρτητα από τη μορφή συμβολισμού, ο αριθμός των συνδυασμών n στοιχείων ανά m στοιχεία μπορεί να προσδιοριστεί χρησιμοποιώντας τους ακόλουθους πολλαπλασιαστικούς και παραγοντικούς τύπους:
Είναι εύκολο να ελεγχθεί ότι το αποτέλεσμα των υπολογισμών που χρησιμοποιούν αυτούς τους τύπους συμπίπτει με τα αποτελέσματα του παραδείγματος που συζητήθηκε παραπάνω με συνδυασμούς φωνηέντων με λατινικά γράμματα. Συγκεκριμένα, με n=5 και m=3, οι υπολογισμοί που χρησιμοποιούν αυτούς τους τύπους θα δώσουν το ακόλουθο αποτέλεσμα:
Στη γενική περίπτωση, οι τύποι για τον αριθμό των συνδυασμών έχουν συνδυαστική σημασία και ισχύουν για οποιεσδήποτε ακέραιες τιμές των n και m, έτσι ώστε n > m > 0. Εάν m > n και m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Επιπλέον, είναι χρήσιμο να θυμάστε τους ακόλουθους περιοριστικούς αριθμούς συνδυασμών, οι οποίοι μπορούν εύκολα να ελεγχθούν με άμεση αντικατάσταση στους πολλαπλασιαστικούς και παραγοντικούς τύπους:
Θα πρέπει επίσης να σημειωθεί ότι ο πολλαπλασιαστικός τύπος παραμένει έγκυρος ακόμα και όταν το n είναι πραγματικός αριθμός, εφόσον το m εξακολουθεί να είναι ακέραια τιμή. Ωστόσο, τότε το αποτέλεσμα του υπολογισμού που το χρησιμοποιεί, ενώ διατηρεί την τυπική εγκυρότητα, χάνει τη συνδυαστική του σημασία.
ΤΑΥΤΟΤΗΤΕΣ ΣΥΝΔΥΑΣΜΩΝ
Η πρακτική χρήση πολλαπλασιαστικών και παραγοντικών τύπων για τον προσδιορισμό του αριθμού των συνδυασμών για αυθαίρετες τιμές n και m αποδεικνύεται μικρή παραγωγικότητα λόγω της εκθετικής αύξησης των παραγοντικών προϊόντων του αριθμητή και του παρονομαστή τους. Ακόμη και για σχετικά μικρές τιμές n και m, αυτά τα προϊόντα συχνά υπερβαίνουν τις δυνατότητες αναπαράστασης ακεραίων στα σύγχρονα συστήματα υπολογιστών και λογισμικού. Επιπλέον, οι τιμές τους αποδεικνύονται σημαντικά μεγαλύτερες από την προκύπτουσα τιμή του αριθμού των συνδυασμών, ο οποίος μπορεί να είναι σχετικά μικρός. Για παράδειγμα, ο αριθμός των συνδυασμών n=10 επί m=8 στοιχείων είναι μόνο 45. Ωστόσο, για να βρείτε αυτήν την τιμή χρησιμοποιώντας τον παραγοντικό τύπο, πρέπει πρώτα να υπολογίσετε πολύ μεγαλύτερες τιμές του 10! στον αριθμητή και το 8! στον παρονομαστή:
Για να εξαλείψετε χρονοβόρες λειτουργίες για την επεξεργασία μεγάλων ποσοτήτων, για να καθορίσετε τον αριθμό των συνδυασμών, μπορείτε να χρησιμοποιήσετε διάφορες σχέσεις επανάληψης, οι οποίες προκύπτουν άμεσα από τους πολλαπλασιαστικούς και παραγοντικούς τύπους. Συγκεκριμένα, η ακόλουθη σχέση επανάληψης προκύπτει από τον πολλαπλασιαστικό τύπο, ο οποίος μας επιτρέπει να πάρουμε την αναλογία των δεικτών του πέρα από το πρόσημο του αριθμού των συνδυασμών:
Τέλος, η διατήρηση του δείκτη σταθερού παρέχει την ακόλουθη σχέση επανάληψης, η οποία προκύπτει εύκολα από τον παραγοντικό τύπο για τον αριθμό των συνδυασμών:
Μετά από στοιχειώδεις μετασχηματισμούς, οι τρεις προκύπτουσες σχέσεις επανάληψης μπορούν να αναπαρασταθούν με τις ακόλουθες μορφές:
Αν τώρα προσθέσουμε την αριστερή και τη δεξιά πλευρά των 2 πρώτων τύπων και μειώσουμε το αποτέλεσμα κατά n, θα έχουμε μια σημαντική σχέση επανάληψης, η οποία ονομάζεται ταυτότητα της πρόσθεσης αριθμών συνδυασμού:
Η ταυτότητα πρόσθεσης παρέχει έναν βασικό κανόνα επανάληψης για τον αποτελεσματικό προσδιορισμό του αριθμού των συνδυασμών για μεγάλες τιμές n και m, καθώς επιτρέπει την αντικατάσταση των πράξεων πολλαπλασιασμού σε παραγοντικά γινόμενα από τις απλούστερες πράξεις πρόσθεσης και για μικρότερους αριθμούς συνδυασμών. Συγκεκριμένα, χρησιμοποιώντας την ταυτότητα πρόσθεσης, είναι πλέον εύκολο να προσδιοριστεί ο αριθμός των συνδυασμών n=10 επί m=8 στοιχείων, που συζητήθηκε παραπάνω, εκτελώντας την ακόλουθη ακολουθία επαναλαμβανόμενων μετασχηματισμών:
Επιπλέον, πολλές χρήσιμες σχέσεις για τον υπολογισμό πεπερασμένων αθροισμάτων μπορούν να προκύψουν από την ταυτότητα πρόσθεσης, ειδικότερα από τον τύπο για άθροιση ανά δείκτη, ο οποίος έχει την ακόλουθη μορφή:
Αυτή η σχέση προκύπτει εάν στην ταυτότητα πρόσθεσης επεκτείνουμε την επανάληψη κατά μήκος του όρου με τον μεγαλύτερο εκθέτη ενώ ο δείκτης του είναι μεγαλύτερος από 0. Το ακόλουθο αριθμητικό παράδειγμα επεξηγεί αυτή τη διαδικασία επαναλαμβανόμενων μετασχηματισμών:
Ο τύπος άθροισης δείκτη χρησιμοποιείται συχνά για τον υπολογισμό του αθροίσματος των δυνάμεων των φυσικών αριθμών. Συγκεκριμένα, υποθέτοντας m=1, χρησιμοποιώντας αυτόν τον τύπο είναι εύκολο να βρεθεί το άθροισμα των πρώτων n αριθμών της φυσικής σειράς:
Μια άλλη χρήσιμη εκδοχή του τύπου άθροισης μπορεί να ληφθεί επεκτείνοντας την επανάληψη της ταυτότητας πρόσθεσης κατά μήκος του όρου με τον μικρότερο εκθέτη. Το ακόλουθο αριθμητικό παράδειγμα επεξηγεί αυτήν την έκδοση επαναλαμβανόμενων μετασχηματισμών:
Στη γενική περίπτωση, ως αποτέλεσμα τέτοιων μετασχηματισμών, προκύπτει το άθροισμα των αριθμών των συνδυασμών, και οι δύο δείκτες των οποίων διαφέρουν κατά ένα από τους γειτονικούς όρους και η διαφορά στους δείκτες παραμένει σταθερή (στο εξεταζόμενο παράδειγμα, είναι επίσης ίσο με ένα). Έτσι, λαμβάνουμε τον ακόλουθο τύπο άθροισης και για τους δύο δείκτες συνδυαστικών αριθμών:
Εκτός από τις σχέσεις επανάληψης και τους τύπους άθροισης που συζητήθηκαν παραπάνω, πολλές άλλες χρήσιμες ταυτότητες για αριθμούς συνδυασμού έχουν ληφθεί σε συνδυαστική ανάλυση. Το πιο σημαντικό από αυτά είναι ταυτότητα συμμετρίας, που μοιάζει με αυτό:
Η εγκυρότητα της ταυτότητας συμμετρίας μπορεί να επαληθευτεί στο ακόλουθο παράδειγμα συγκρίνοντας τους αριθμούς συνδυασμών 5 στοιχείων κατά 2 και κατά (5 2) = 3:
Η ταυτότητα συμμετρίας έχει μια προφανή συνδυαστική σημασία, αφού, προσδιορίζοντας τον αριθμό των επιλογών για την επιλογή m στοιχείων από n στοιχεία, καθορίζει ταυτόχρονα τον αριθμό των συνδυασμών από τα υπόλοιπα (nm) μη επιλεγμένα στοιχεία. Η υποδεικνυόμενη συμμετρία λαμβάνεται αμέσως αντικαθιστώντας το m με (nm) στον παραγοντικό τύπο για τον αριθμό των συνδυασμών:
Οι αριθμοί και οι ταυτότητες συνδυασμών χρησιμοποιούνται ευρέως σε διάφορους τομείς των σύγχρονων υπολογιστικών μαθηματικών. Ωστόσο, οι πιο δημοφιλείς εφαρμογές τους σχετίζονται με το διώνυμο του Νεύτωνα και το τρίγωνο του Πασκάλ.
ΔΙΩΝΥΜΙΚΟ ΘΕΩΡΗΜΑ
Για να εκτελέσετε διάφορους μαθηματικούς μετασχηματισμούς και υπολογισμούς, είναι σημαντικό να μπορείτε να αναπαραστήσετε οποιαδήποτε φυσική δύναμη ενός αλγεβρικού διωνύμου (διωνύμου) με τη μορφή πολυωνύμου. Για μικρές δυνάμεις, το επιθυμητό πολυώνυμο μπορεί να ληφθεί εύκολα πολλαπλασιάζοντας απευθείας τα διώνυμα. Συγκεκριμένα, οι ακόλουθοι τύποι για το τετράγωνο και τον κύβο του αθροίσματος δύο όρων είναι πολύ γνωστοί από το μάθημα των μαθηματικών της δημοτικής:
Στη γενική περίπτωση, για έναν αυθαίρετο βαθμό n ενός διωνύμου, η απαιτούμενη αναπαράσταση με τη μορφή πολυωνύμου παρέχεται από το διωνυμικό θεώρημα του Νεύτωνα, το οποίο δηλώνει αληθή την ακόλουθη ισότητα:
Αυτή η ισότητα συνήθως ονομάζεται διώνυμο του Νεύτωνα. Το πολυώνυμο στη δεξιά πλευρά του σχηματίζεται από το άθροισμα των γινομένων των n όρων X και Y του διωνύμου στην αριστερή πλευρά και οι συντελεστές μπροστά τους ονομάζονται διωνυμικοί και είναι ίσοι με τον αριθμό των συνδυασμών με δείκτες που προέρχονται από τις δυνάμεις τους. Δεδομένης της ιδιαίτερης δημοτικότητας του διωνυμικού τύπου του Newton στη συνδυαστική ανάλυση, οι όροι διωνυμικός συντελεστής και αριθμός συνδυασμών θεωρούνται γενικά συνώνυμοι.
Προφανώς, οι τύποι του τετραγώνου και του αθροίσματος σε κύβους είναι ειδικές περιπτώσεις του διωνυμικού θεωρήματος για n=2 και n=3, αντίστοιχα. Για τον χειρισμό υψηλότερων βαθμών (n>3), θα πρέπει να χρησιμοποιηθεί ο διωνυμικός τύπος του Newton. Η εφαρμογή του για ένα διώνυμο τέταρτου βαθμού (n=4) αποδεικνύεται από το ακόλουθο παράδειγμα:
Πρέπει να σημειωθεί ότι ο διωνυμικός τύπος ήταν γνωστός ακόμη και πριν από τον Νεύτωνα στους μεσαιωνικούς μαθηματικούς της Αραβικής Ανατολής και της Δυτικής Ευρώπης. Επομένως, το γενικά αποδεκτό όνομά του δεν είναι ιστορικά δίκαιο. Το πλεονέκτημα του Νεύτωνα είναι ότι γενίκευσε αυτόν τον τύπο στην περίπτωση ενός αυθαίρετου πραγματικού εκθέτη r, ο οποίος μπορεί να λάβει οποιεσδήποτε θετικές ή αρνητικές ορθολογικές και παράλογες τιμές. Στη γενική περίπτωση, ένας τέτοιος διωνυμικός τύπος του Νεύτωνα έχει ένα άπειρο άθροισμα στη δεξιά πλευρά και συνήθως γράφεται ως εξής:
Για παράδειγμα, με θετική κλασματική τιμή του εκθέτη r=1/2, λαμβάνοντας υπόψη τις τιμές των διωνυμικών συντελεστών, προκύπτει η ακόλουθη επέκταση:
Στη γενική περίπτωση, ο διωνυμικός τύπος του Νεύτωνα για οποιονδήποτε εκθέτη είναι μια ειδική έκδοση του τύπου του Maclaurin, ο οποίος δίνει την επέκταση μιας αυθαίρετης συνάρτησης σε μια σειρά ισχύος. Ο Νεύτων έδειξε ότι για |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Αν τώρα θέσουμε Z=X/Y και πολλαπλασιάσουμε την αριστερή και τη δεξιά πλευρά με Yn, θα έχουμε μια έκδοση του διωνυμικού τύπου Newton που συζητήθηκε παραπάνω.
Παρά την καθολικότητά του, το διωνυμικό θεώρημα διατηρεί τη συνδυαστική του σημασία μόνο για τις μη αρνητικές ακέραιες δυνάμεις του διωνύμου. Σε αυτή την περίπτωση, μπορεί να χρησιμοποιηθεί για να αποδείξει πολλές χρήσιμες ταυτότητες για διωνυμικούς συντελεστές. Ειδικότερα, οι τύποι για την άθροιση των αριθμών των συνδυασμών ανά δείκτη και κατά αμφότερους τους δείκτες συζητήθηκαν παραπάνω. Η ταυτότητα αθροίσματος που λείπει μπορεί εύκολα να ληφθεί από τον διωνυμικό τύπο του Νεύτωνα βάζοντας X = Y = 1 ή Z = 1 σε αυτόν:
Μια άλλη χρήσιμη ταυτότητα καθιερώνει την ισότητα των αθροισμάτων διωνυμικών συντελεστών με άρτιους και περιττούς αριθμούς. Λαμβάνεται αμέσως από τον διωνυμικό τύπο του Νεύτωνα εάν X = 1 και Y = 1 ή Z = 1:
Τέλος, και από τις δύο θεωρούμενες ταυτότητες παίρνουμε την ταυτότητα του αθροίσματος των διωνυμικών συντελεστών με μόνο ζυγούς ή μόνο περιττούς αριθμούς:
Με βάση τις εξεταζόμενες ταυτότητες και τον επαναλαμβανόμενο κανόνα αφαίρεσης των δεικτών κάτω από το πρόσημο του αριθμού των συνδυασμών, μπορεί να ληφθεί ένας αριθμός από ενδιαφέρουσες σχέσεις. Για παράδειγμα, εάν στον τύπο άθροισης εκθέτη αντικαταστήσουμε το n παντού με το (n1) και αφαιρέσουμε τους δείκτες σε κάθε όρο, παίρνουμε την ακόλουθη σχέση:
Χρησιμοποιώντας μια παρόμοια τεχνική στον τύπο για το άθροισμα των διωνυμικών συντελεστών με άρτιους και περιττούς αριθμούς, είναι δυνατό να αποδειχθεί η εγκυρότητα, για παράδειγμα, της ακόλουθης σχέσης:
Μια άλλη χρήσιμη ταυτότητα σάς επιτρέπει να υπολογίζετε εύκολα το άθροισμα των γινομένων των συμμετρικά τοποθετημένων διωνυμικών συντελεστών δύο διωνύμων αυθαίρετων βαθμών n και k χρησιμοποιώντας τον ακόλουθο τύπο Cauchy:
Η εγκυρότητα αυτού του τύπου προκύπτει από την απαραίτητη ισότητα συντελεστών για οποιονδήποτε βαθμό m της μεταβλητής Z στην αριστερή και δεξιά πλευρά της ακόλουθης πανομοιότυπης σχέσης:
Στην ειδική περίπτωση που n=k=m, λαμβάνοντας υπόψη την ταυτότητα συμμετρίας, προκύπτει ένας πιο δημοφιλής τύπος για το άθροισμα των τετραγώνων των διωνυμικών συντελεστών:
Πολλές άλλες χρήσιμες ταυτότητες για διωνυμικούς συντελεστές μπορούν να βρεθούν στην εκτενή βιβλιογραφία για τη συνδυαστική ανάλυση. Ωστόσο, η πιο διάσημη πρακτική εφαρμογή τους σχετίζεται με το τρίγωνο του Πασκάλ.
ΤΟ ΤΡΙΓΩΝΟ ΤΟΥ ΠΑΣΚΑΛ
Το αριθμητικό τρίγωνο του Pascal σχηματίζει έναν άπειρο αριθμητικό πίνακα που αποτελείται από διωνυμικούς συντελεστές. Οι γραμμές του ταξινομούνται με δυνάμεις διωνύμων από πάνω προς τα κάτω. Σε κάθε γραμμή, οι διωνυμικοί συντελεστές είναι διατεταγμένοι σε αύξουσα σειρά των εκθέτων των αντίστοιχων αριθμών συνδυασμού από αριστερά προς τα δεξιά. Το τρίγωνο του Πασκάλ συνήθως γράφεται είτε σε ισοσκελή είτε σε ορθογώνια μορφή.
Πιο οπτική και κοινή είναι η ισοσκελής μορφή, όπου οι διωνυμικοί συντελεστές, κλιμακωτοί, σχηματίζουν ένα άπειρο ισοσκελές τρίγωνο. Το αρχικό του θραύσμα για διώνυμα έως 4ου βαθμού (n=4) έχει την εξής μορφή:
Γενικά, το ισοσκελές τρίγωνο του Pascal παρέχει έναν βολικό γεωμετρικό κανόνα για τον προσδιορισμό των διωνυμικών συντελεστών, ο οποίος βασίζεται στις ταυτότητες της πρόσθεσης και στη συμμετρία των συνδυασμών αριθμών. Συγκεκριμένα, σύμφωνα με την ταυτότητα πρόσθεσης, οποιοσδήποτε διωνυμικός συντελεστής είναι το άθροισμα των δύο συντελεστών της προηγούμενης σειράς που βρίσκεται πλησιέστερα σε αυτόν. Σύμφωνα με την ταυτότητα συμμετρίας, το ισοσκελές τρίγωνο του Pascal είναι συμμετρικό ως προς τη διχοτόμο του. Έτσι, κάθε γραμμή του είναι ένα αριθμητικό παλίνδρομο διωνυμικών συντελεστών. Τα υποδεικνυόμενα αλγεβρικά και γεωμετρικά χαρακτηριστικά καθιστούν δυνατή την εύκολη επέκταση του ισοσκελούς τριγώνου του Pascal και τη σταθερή εύρεση των τιμών των διωνυμικών συντελεστών αυθαίρετων δυνάμεων.
Ωστόσο, για να μελετήσετε διάφορες ιδιότητες του τριγώνου του Pascal, είναι πιο βολικό να χρησιμοποιήσετε την τυπικά πιο αυστηρή ορθογώνια μορφή. Σε αυτή τη μορφή, καθορίζεται από έναν χαμηλότερο τριγωνικό πίνακα διωνυμικών συντελεστών, όπου σχηματίζουν ένα άπειρο ορθογώνιο τρίγωνο. Το αρχικό θραύσμα του ορθογωνίου τριγώνου του Πασκάλ για διώνυμα μέχρι την 9η μοίρα (n=9) έχει την ακόλουθη μορφή:
Γεωμετρικά, ένας τέτοιος ορθογώνιος πίνακας προκύπτει παραμορφώνοντας οριζόντια το ισοσκελές τρίγωνο του Pascal. Ως αποτέλεσμα, οι αριθμητικές σειρές παράλληλες στις πλευρικές πλευρές του ισοσκελούς τριγώνου του Πασκάλ μετατρέπονται σε κάθετες και διαγώνιες του ορθογωνίου τριγώνου του Πασκάλ και οι οριζόντιες γραμμές και των δύο τριγώνων συμπίπτουν. Ταυτόχρονα, οι κανόνες της πρόσθεσης και της συμμετρίας των διωνυμικών συντελεστών παραμένουν σε ισχύ, αν και το ορθογώνιο τρίγωνο του Pascal χάνει την οπτική συμμετρία που χαρακτηρίζει το ισοσκελές αντίστοιχό του. Για να αντισταθμιστεί αυτό, γίνεται πιο βολικό να αναλύσουμε επίσημα τις διάφορες αριθμητικές ιδιότητες των διωνυμικών συντελεστών για τις οριζόντιες, τις κατακόρυφες και τις διαγώνιες του ορθογωνίου τριγώνου του Pascal.
Ξεκινώντας την ανάλυση των οριζόντιων του ορθογωνίου τριγώνου του Pascal, είναι εύκολο να παρατηρήσετε ότι το άθροισμα των στοιχείων οποιασδήποτε γραμμής με αριθμό n είναι ίσο με 2n σύμφωνα με τον τύπο για την άθροιση διωνύμων με εκθέτη. Από αυτό προκύπτει ότι το άθροισμα των στοιχείων πάνω από οποιαδήποτε από τις οριζόντιες γραμμές με αριθμό n είναι ίσο με (2 n 1). Αυτό το αποτέλεσμα γίνεται αρκετά προφανές εάν η τιμή του αθροίσματος των στοιχείων κάθε οριζόντιας γραφτεί στο δυαδικό σύστημα αριθμών. Για παράδειγμα, για n=4 αυτή η προσθήκη μπορεί να γραφτεί ως εξής:
Εδώ είναι μερικές ακόμη ενδιαφέρουσες ιδιότητες των οριζόντιων που σχετίζονται επίσης με τις δυνάμεις των δύο. Αποδεικνύεται ότι αν ο οριζόντιος αριθμός είναι δύναμη του δύο (n=2 k), τότε όλα τα εσωτερικά του στοιχεία (εκτός από τα εξωτερικά) είναι ζυγοί αριθμοί. Αντίθετα, όλοι οι αριθμοί μιας οριζόντιας ευθείας θα είναι περιττοί αν ο αριθμός της είναι κατά ένα μικρότερος από τη δύναμη του δύο (n=2 k 1). Η εγκυρότητα αυτών των ιδιοτήτων μπορεί να επαληθευτεί ελέγχοντας την ισοτιμία των εσωτερικών διωνυμικών συντελεστών, για παράδειγμα, στις οριζόντιες θέσεις n=4 και n=3 ή n=8 και n=7.
Έστω τώρα ο αριθμός σειράς του ορθογωνίου τριγώνου του Pascal πρώτος αριθμός p. Τότε όλοι οι εσωτερικοί διωνυμικοί συντελεστές του διαιρούνται με το p. Αυτή η ιδιότητα είναι εύκολο να ελεγχθεί για μικρές τιμές πρώτων αριθμών περιγράμματος. Για παράδειγμα, όλοι οι εσωτερικοί διωνυμικοί συντελεστές της πέμπτης οριζόντιας (5, 10 και 5) διαιρούνται προφανώς με το 5. Για να αποδείξετε αυτό το αποτέλεσμα για οποιονδήποτε πρώτο οριζόντιο αριθμό p, πρέπει να γράψετε τον πολλαπλασιαστικό τύπο για τους διωνυμικούς συντελεστές του ως εξής:
Εφόσον το p είναι πρώτος αριθμός και, επομένως, δεν διαιρείται με το m!, το γινόμενο των υπόλοιπων παραγόντων του αριθμητή αυτού του τύπου πρέπει να διαιρείται με το m! για να εγγυηθεί μια ακέραια τιμή του διωνυμικού συντελεστή. Από αυτό προκύπτει ότι ο λόγος σε αγκύλες είναι ένας φυσικός αριθμός N και το επιθυμητό αποτέλεσμα γίνεται προφανές:
Χρησιμοποιώντας αυτό το αποτέλεσμα, μπορούμε να διαπιστώσουμε ότι οι αριθμοί όλων των οριζόντιων γραμμών του τριγώνου του Pascal, των οποίων τα εσωτερικά στοιχεία διαιρούνται με έναν δεδομένο πρώτο αριθμό p, είναι δυνάμεις του p, δηλαδή έχουν τη μορφή n=p k. Συγκεκριμένα, αν p=3, τότε ο πρώτος αριθμός p διαιρεί όχι μόνο όλα τα εσωτερικά στοιχεία της σειράς 3, όπως ορίστηκε παραπάνω, αλλά, για παράδειγμα, την 9η οριζόντια (9, 36, 84 και 126). Από την άλλη πλευρά, στο τρίγωνο του Pascal είναι αδύνατο να βρεθεί μια οριζόντια γραμμή της οποίας τα εσωτερικά στοιχεία είναι όλα διαιρούμενα με έναν σύνθετο αριθμό. Διαφορετικά, ο αριθμός μιας τέτοιας οριζόντιας γραμμής πρέπει ταυτόχρονα να είναι μια δύναμη πρώτων διαιρετών του σύνθετου αριθμού με τον οποίο διαιρούνται όλα τα εσωτερικά στοιχεία της, αλλά αυτό είναι αδύνατο για προφανείς λόγους.
Οι θεωρήσεις που εξετάστηκαν μας επιτρέπουν να διατυπώσουμε το ακόλουθο γενικό κριτήριο για τη διαιρετότητα των οριζόντιων στοιχείων του τριγώνου του Pascal. Ο μεγαλύτερος κοινός διαιρέτης (GCD) όλων των εσωτερικών στοιχείων οποιασδήποτε οριζόντιας ευθείας του τριγώνου του Pascal με αριθμό n είναι ίσος με τον πρώτο αριθμό p εάν n=pk ή 1 σε όλες τις άλλες περιπτώσεις:
GCD(Cmn) = ( ) για οποιοδήποτε 0< m < n .
Ολοκληρώνοντας την ανάλυση των οριζόντιων, αξίζει να εξετάσουμε μια ακόμη ενδιαφέρουσα ιδιότητα που έχει η σειρά των διωνυμικών συντελεστών που τις σχηματίζουν. Εάν οι διωνυμικοί συντελεστές οποιασδήποτε οριζόντιας ευθείας με αριθμό n πολλαπλασιαστούν με τις διαδοχικές δυνάμεις του αριθμού 10, και στη συνέχεια προστεθούν όλα αυτά τα γινόμενα, το αποτέλεσμα είναι 11 n. Η επίσημη αιτιολόγηση για αυτό το αποτέλεσμα είναι η αντικατάσταση των τιμών X=10 και Y=1 (ή Z=1) στον διωνυμικό τύπο Newton. Το ακόλουθο αριθμητικό παράδειγμα επεξηγεί την εκπλήρωση αυτής της ιδιότητας για n=5:
Η ανάλυση των ιδιοτήτων των κατακόρυφων του ορθογώνιου τριγώνου του Pascal μπορεί να ξεκινήσει με τη μελέτη των επιμέρους χαρακτηριστικών των στοιχείων που τα αποτελούν. Τυπικά, κάθε κατακόρυφος m σχηματίζεται από την ακόλουθη άπειρη ακολουθία διωνυμικών συντελεστών με σταθερό εκθέτη (m) και μια αύξηση του δείκτη:
Προφανώς, όταν m=0 προκύπτει μια ακολουθία μονάδων, και όταν m=1 σχηματίζεται μια σειρά φυσικών αριθμών. Όταν m=2 η κατακόρυφη αποτελείται από τριγωνικούς αριθμούς. Κάθε τριγωνικός αριθμός μπορεί να απεικονιστεί σε ένα επίπεδο με τη μορφή ενός ισόπλευρου τριγώνου, το οποίο είναι γεμάτο με αυθαίρετα αντικείμενα (πυρήνες) διατεταγμένα σε μοτίβο σκακιέρας. Σε αυτήν την περίπτωση, η τιμή κάθε τριγωνικού αριθμού T k καθορίζει τον αριθμό των αντιπροσωπευτικών πυρήνων και ο δείκτης δείχνει πόσες σειρές πυρήνων χρειάζονται για να τον αναπαραστήσουν. Για παράδειγμα, 4 αρχικοί τριγωνικοί αριθμοί αντιπροσωπεύουν τις ακόλουθες διαμορφώσεις του αντίστοιχου αριθμού πυρηνικών συμβόλων "@":
Πρέπει να σημειωθεί ότι με παρόμοιο τρόπο μπορεί κανείς να εισαγάγει υπόψη τετράγωνους αριθμούς S k , οι οποίοι προκύπτουν από τον τετραγωνισμό των φυσικών αριθμών και, γενικά, πολυγωνικούς αριθμούς που σχηματίζονται με κανονική πλήρωση κανονικών πολυγώνων. Συγκεκριμένα, οι 4 αρχικοί τετραγωνικοί αριθμοί μπορούν να αναπαρασταθούν ως εξής:
Επιστρέφοντας στην ανάλυση των κατακόρυφων του τριγώνου του Pascal, μπορούμε να σημειώσουμε ότι η επόμενη κατακόρυφος στο m=3 είναι γεμάτη με τετραεδρικούς (πυραμιδικούς) αριθμούς. Κάθε τέτοιος αριθμός P k καθορίζει τον αριθμό των πυρήνων που μπορούν να διαταχθούν σε σχήμα τετραέδρου και ο δείκτης καθορίζει πόσα οριζόντια τριγωνικά στρώματα σειρών πυρήνων απαιτούνται για να τον απεικονίσουν σε τρισδιάστατο χώρο. Σε αυτήν την περίπτωση, όλα τα οριζόντια στρώματα πρέπει να αντιπροσωπεύονται ως διαδοχικοί τριγωνικοί αριθμοί. Τα στοιχεία των ακόλουθων κατακόρυφων του τριγώνου του Pascal για m>3 σχηματίζουν σειρές υπερτετραεδρικών αριθμών, οι οποίοι δεν έχουν οπτική γεωμετρική ερμηνεία στο επίπεδο ή στον τρισδιάστατο χώρο, αλλά τυπικά αντιστοιχούν σε πολυδιάστατα ανάλογα τριγωνικών και τετραεδρικών αριθμών.
Αν και οι κατακόρυφες σειρές αριθμών του τριγώνου του Pascal έχουν τα θεωρούμενα μεμονωμένα διαμορφωμένα χαρακτηριστικά, γι 'αυτούς είναι δυνατός ο υπολογισμός των μερικών αθροισμάτων των τιμών των αρχικών στοιχείων με τον ίδιο τρόπο, χρησιμοποιώντας τον τύπο για την άθροιση των αριθμών των συνδυασμών ανά δείκτη . Στο τρίγωνο του Pascal, αυτός ο τύπος έχει την ακόλουθη γεωμετρική ερμηνεία. Το άθροισμα των τιμών των n άνω διωνυμικών συντελεστών οποιουδήποτε κατακόρυφου είναι ίσο με την τιμή του στοιχείου του επόμενου κατακόρυφου, το οποίο βρίσκεται μια γραμμή παρακάτω. Αυτό το αποτέλεσμα είναι επίσης συνεπές με τη γεωμετρική δομή των τριγωνικών, τετραεδρικών και υπερτετραεδρικών αριθμών, καθώς η αναπαράσταση κάθε τέτοιου αριθμού αποτελείται από στρώματα πυρήνα που αντιπροσωπεύουν αριθμούς χαμηλότερης τάξης. Συγκεκριμένα, ο ν ο τριγωνικός αριθμός T n μπορεί να ληφθεί αθροίζοντας όλους τους φυσικούς αριθμούς που αντιπροσωπεύουν τα γραμμικά του στρώματα:
Ομοίως, δεν είναι δύσκολο να βρεθεί ο τετραεδρικός αριθμός Pn υπολογίζοντας το ακόλουθο άθροισμα των πρώτων n τριγωνικών αριθμών που αποτελούν τα οριζόντια στρώματα πυρήνα του:
Εκτός από τις οριζόντιες και κάθετες στο ορθογώνιο τρίγωνο του Pascal, μπορεί κανείς να εντοπίσει διαγώνιες σειρές στοιχείων, η μελέτη των ιδιοτήτων των οποίων παρουσιάζει επίσης κάποιο ενδιαφέρον. Σε αυτή την περίπτωση, συνήθως γίνεται διάκριση μεταξύ φθίνουσας και αύξουσας διαγωνίου. Οι προς τα κάτω διαγώνιοι είναι παράλληλες με την υποτείνουσα του ορθογωνίου τριγώνου του Πασκάλ. Σχηματίζονται από σειρές διωνυμικών συντελεστών με προσαύξηση και των δύο δεικτών. Λόγω της ταυτότητας της συμμετρίας, οι φθίνουσες διαγώνιοι συμπίπτουν στις τιμές των στοιχείων τους με τις αντίστοιχες κάθετες σειρές του τριγώνου του Pascal και επομένως επαναλαμβάνουν όλες τις ιδιότητές τους που συζητήθηκαν παραπάνω. Η υποδεικνυόμενη αντιστοιχία μπορεί να εντοπιστεί από τη σύμπτωση των τιμών των στοιχείων της φθίνουσας διαγωνίου και της κατακόρυφης με οποιονδήποτε αριθμό n, εάν δεν ληφθούν υπόψη τα κατακόρυφα μηδενικά:
Οι αύξουσες διαγώνιες σχηματίζουν αριθμητικές σειρές γεωμετρικά κάθετες στην υποτείνουσα του ορθογωνίου τριγώνου του Πασκάλ. Γεμίζονται με διωνυμικούς συντελεστές με μείωση του κατώτερου και προσαύξηση του εκθέτη. Ειδικότερα, οι 7 άνω αύξουσες διαγώνιοι σχηματίζουν την ακόλουθη αριθμητική ακολουθία χωρίς να λαμβάνονται υπόψη τα μηδενικά που ακολουθούν:
Γενικά, η αύξουσα διαγώνιος αριθμός n περιέχει τους ακόλουθους διωνυμικούς συντελεστές, το άθροισμα των δεικτών καθενός από τα οποία είναι ίσο με (n1):
Λόγω της ταυτότητας πρόσθεσης για αριθμούς συνδυασμού, κάθε διαγώνιο στοιχείο ισούται με το άθροισμα δύο στοιχείων που αντιστοιχούν σε δείκτες από τις δύο προηγούμενες αύξουσες διαγώνιους. Αυτό επιτρέπει σε κάθε επόμενη αύξουσα διαγώνιο να κατασκευαστεί με ζεύγος άθροιση γειτονικών οριζόντιων στοιχείων από τις δύο προηγούμενες διαγώνιους, επεκτείνοντας άπειρα το τρίγωνο του Pascal κατά μήκος της διαγώνιου. Το ακόλουθο τμήμα του τριγώνου του Πασκάλ απεικονίζει την κατασκευή μιας αύξουσας διαγώνιου αριθμού 8 κατά μήκος των διαγωνίων με αριθμό 6 και 7:
Με αυτόν τον τρόπο κατασκευής, το άθροισμα των στοιχείων οποιασδήποτε αύξουσας διαγωνίου, ξεκινώντας από την 3η, θα είναι ίσο με το άθροισμα των στοιχείων των δύο προηγούμενων αύξουσας διαγώνιου και οι 2 πρώτες διαγώνιες αποτελούνται από ένα μόνο στοιχείο, την τιμή εκ των οποίων είναι 1. Τα αποτελέσματα των αντίστοιχων υπολογισμών σχηματίζουν την ακόλουθη αριθμητική σειρά, σύμφωνα με την οποία μπορείτε να ελέγξετε την εγκυρότητα της θεωρούμενης ιδιότητας των αύξουσας διαγωνίου του ορθογωνίου τριγώνου του Pascal:
Αναλύοντας αυτούς τους αριθμούς, μπορείτε να δείτε ότι σύμφωνα με έναν παρόμοιο νόμο, σχηματίζεται η γνωστή ακολουθία αριθμών Fibonacci, όπου κάθε επόμενος αριθμός είναι ίσος με το άθροισμα των δύο προηγούμενων και οι δύο πρώτοι αριθμοί είναι ίσοι με 1:
Έτσι, μπορούμε να βγάλουμε το ακόλουθο σημαντικό συμπέρασμα: τα διαγώνια αθροίσματα των στοιχείων του τριγώνου του Pascal αποτελούν την ακολουθία Fibonacci. Αυτή η ιδιότητα μας επιτρέπει να δημιουργήσουμε ένα άλλο ενδιαφέρον χαρακτηριστικό του τριγώνου του Pascal. Επεκτείνοντας τον τύπο Fibonacci αναδρομικά, είναι εύκολο να αποδείξουμε ότι το άθροισμα των πρώτων n αριθμών Fibonacci είναι ίσο με (F n+2 1).
Επομένως, το άθροισμα των διωνυμικών συντελεστών που γεμίζουν τις άνω n διαγώνιους είναι επίσης ίσο με (F n+2 1). Από αυτό προκύπτει ότι το άθροισμα των πρώτων n διαγωνίων του τριγώνου του Pascal είναι 1 μικρότερο από το άθροισμα των διωνυμικών συντελεστών που βρίσκονται στη διαγώνιο του με τον αριθμό (n+2).
Συμπερασματικά, πρέπει να σημειωθεί ότι οι εξεταζόμενες ιδιότητες των οριζόντιων, κατακόρυφων και διαγωνίων του τριγώνου του Pascal δεν εξαντλούν την τεράστια ποικιλία δυνατοτήτων που συνδέουν διάφορες μαθηματικές πτυχές που με την πρώτη ματιά δεν έχουν τίποτα κοινό. Τέτοιες ασυνήθιστες ιδιότητες μας επιτρέπουν να θεωρήσουμε το τρίγωνο του Pascal ένα από τα πιο τέλεια αριθμητικά συστήματα, του οποίου όλες οι δυνατότητες δεν μπορούν να απαριθμηθούν και είναι δύσκολο να υπερεκτιμηθούν.
Ο αλγόριθμος για τον υπολογισμό του αριθμού των συνδυασμών χρησιμοποιώντας το τρίγωνο του Pascal παρουσιάζεται παρακάτω:
Ιδιωτική συνάρτηση SochTT (ByVal n Ως ακέραιος, ByVal k ως ακέραιος) Ως διπλό Dim i ως ακέραιος Dim j Ως ακέραιος αριθμός Dim TT () Ως Double ReDim TT (n, k) Για i = 0 έως n TT (0, i) = 1 TT (i, i) = 1 Επόμενο Για i = 2 Προς n Για j = 1 Προς i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Επόμενο Επόμενο SochTT = TT (n, k) Τελική συνάρτηση
Εάν χρειάζεται να υπολογίσετε τον αριθμό των συνδυασμών πολλές φορές, τότε μπορεί να είναι πιο βολικό να κατασκευάσετε το τρίγωνο του Pascal μία φορά και στη συνέχεια να λάβετε δεδομένα από τον πίνακα.
Dim TT () Ως Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n ως ακέραιος, ByVal k ως ακέραιος) Ως διπλό Εάν n > Ubound (TT) Στη συνέχεια, BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) End Function Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal start As Integer, ByVal end As Integer) Dim i As Integer Dim j Ως ακέραιος ReDim Διατήρηση TT (τέλος, τέλος) Για i = έναρξη Μέχρι τέλος TT (0, i) = 1 TT (i, i) = 1 Επόμενο Εάν τέλος< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
Πρώτα πρέπει να καλέσετε τη διαδικασία CreateTT. Στη συνέχεια, μπορείτε να λάβετε τον αριθμό των συνδυασμών χρησιμοποιώντας τη συνάρτηση SochTT. Όταν δεν χρειάζεστε πλέον το τρίγωνο, καλέστε τη διαδικασία TerminateTT. Στον παραπάνω κωδικό, κατά την κλήση της συνάρτησης SochTT, εάν το τρίγωνο δεν έχει ακόμη συμπληρωθεί στο απαιτούμενο επίπεδο, τότε ολοκληρώνεται με τη διαδικασία BuildTT. Στη συνέχεια, η συνάρτηση παίρνει το επιθυμητό στοιχείο του πίνακα ΤΤ και το επιστρέφει.
Dim X () Ως ακέραιος Dim μετρητής () Ως ακέραιος αριθμός Dim K ως ακέραιος αριθμός Dim N ως ακέραιος δημόσιος Sub Soch() Dim i As Integer N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Επόμενο txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c Ως ακέραιος) Dim i Ως ακέραιος Dim j Ως ακέραιος Dim n1 Ως ακέραιος αριθμός Dim Out() Ως ακέραιος αριθμός Dim X1() Ως ακέραιος αριθμός Αν c = K Τότε ReDim Out(K) X1 = X Για i = 1 σε K - 1 n1 = 0 Για j = 1 έως N Αν X1(j)<>0 Τότε n1 = n1 + 1 Αν n1 = Μετρητής(i) Τότε Out(i) = X1(j) X1(j) = 0 Έξοδος για Τέλος Αν Επόμενο txtOut.Text = txtOut.Text & CStr(Out(i)) Επόμενο txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
ΠΑΡΑΘΕΣΗ ΣΥΝΔΥΑΣΜΩΝ ΦΥΣΙΚΩΝ ΑΡΙΘΜΩΝ
Για την επίλυση πολλών πρακτικών προβλημάτων, είναι απαραίτητο να απαριθμήσουμε όλους τους συνδυασμούς σταθερής καρδιναικότητας που μπορούν να ληφθούν από τα στοιχεία ενός δεδομένου πεπερασμένου συνόλου και όχι απλώς να προσδιορίσουμε τον αριθμό τους. Λαμβάνοντας υπόψη την πάντα υπάρχουσα δυνατότητα ακέραιης αρίθμησης των στοιχείων οποιουδήποτε πεπερασμένου συνόλου, στις περισσότερες περιπτώσεις επιτρέπεται να περιοριστούμε στη χρήση αλγορίθμων για την απαρίθμηση συνδυασμών φυσικών αριθμών. Το πιο φυσικό και απλό από αυτά είναι ο αλγόριθμος για την καταχώριση συνδυασμών φυσικών αριθμών σε λεξιγραφική σειρά.
Για να περιγράψουμε επίσημα αυτόν τον αλγόριθμο, είναι βολικό να υποθέσουμε ότι το κύριο σύνολο, όλοι οι συνδυασμοί των m στοιχείων του οποίου πρέπει να παρατίθενται, σχηματίζουν διαδοχικούς φυσικούς αριθμούς από το 1 έως το n. Τότε οποιοσδήποτε συνδυασμός μ Ως αποτέλεσμα της παραγγελίας, η τιμή σε κάθε θέση ενός τέτοιου διανύσματος συνδυασμών αποδεικνύεται φυσικά ότι είναι περιορισμένη σε τιμή από πάνω και κάτω ως εξής: Ο λεξιγραφικός αλγόριθμος δημιουργεί διαδοχικά τέτοια διανύσματα συνδυασμού, ξεκινώντας από το λεξιγραφικά μικρότερο διάνυσμα, όπου όλες οι θέσεις περιέχουν τις ακόλουθες ελάχιστες δυνατές τιμές στοιχείων ίσες με τους δείκτες τους: Κάθε διαδοχικό διάνυσμα συνδυασμού σχηματίζεται από το τρέχον μετά από σάρωση των στοιχείων του από αριστερά προς τα δεξιά προκειμένου να βρεθεί το δεξιότερο στοιχείο που δεν έχει φτάσει ακόμη την οριακή του τιμή: Η τιμή ενός τέτοιου στοιχείου θα πρέπει να αυξηθεί κατά 1. Σε κάθε στοιχείο στα δεξιά του θα πρέπει να εκχωρηθεί η μικρότερη δυνατή τιμή, η οποία είναι 1 μεγαλύτερη από τον γείτονά του στα αριστερά. Μετά από αυτές τις αλλαγές, το επόμενο διάνυσμα συνδυασμών θα έχει την ακόλουθη στοιχειακή σύνθεση: Έτσι, το επόμενο διάνυσμα συνδυασμού θα είναι λεξιγραφικά μεγαλύτερο από το προηγούμενο, αφού οι τιμές των αρχικών (j1) στοιχείων τους είναι ίσες σε αξία και η τιμή του στοιχείου στη θέση j είναι 1 μεγαλύτερη από αυτή του προηγούμενου . Η καθορισμένη σχέση αυξανόμενης λεξιγραφικής σειράς είναι εγγυημένη ότι ικανοποιείται σε όλες τις επαναλήψεις του αλγορίθμου. Το αποτέλεσμα είναι μια αυξανόμενη λεξιγραφική ακολουθία, η οποία συμπληρώνεται από το λεξιγραφικά μεγαλύτερο διάνυσμα συνδυασμού, όπου τα στοιχεία σε όλες τις θέσεις έχουν τις ακόλουθες μέγιστες τιμές: Ο εξεταζόμενος λεξιγραφικός αλγόριθμος απεικονίζεται στο ακόλουθο παράδειγμα, όπου είναι απαραίτητο να παραθέσουμε με αυξανόμενη λεξιγραφική σειρά και τους 15 συνδυασμούς n=6 πρώτων φυσικών αριθμών με m=4 αριθμούς, δηλαδή όλα τα πιθανά υποσύνολα 4 στοιχείων της κύριας παραγωγής σύνολο (1, 2, 3, 4 , 5, 6) από 6 στοιχεία. Τα αποτελέσματα των υπολογισμών παρουσιάζονται στον παρακάτω πίνακα: Σε αυτό το παράδειγμα, οι μεγαλύτερες επιτρεπόμενες τιμές αριθμών στις θέσεις των διανυσμάτων συνδυασμού είναι, αντίστοιχα, 3, 4, 5 και 6. Για ευκολία στην ερμηνεία των αποτελεσμάτων, σε κάθε διάνυσμα συνδυασμού, το δεξιότερο στοιχείο, το οποίο έχει δεν έχει φτάσει ακόμη στη μέγιστη τιμή του, υπογραμμίζεται. Αριθμητικοί δείκτες συνδυαστικών διανυσμάτων καθορίζουν τους αριθμούς τους με λεξιγραφική σειρά. Στη γενική περίπτωση, ο λεξιγραφικός αριθμός N οποιουδήποτε συνδυασμού n στοιχείων κατά m μπορεί να υπολογιστεί χρησιμοποιώντας τον ακόλουθο τύπο, όπου, για κοσμητικούς λόγους, ο συμβολισμός Appel χρησιμοποιείται για να δηλώσει τους αριθμούς των συνδυασμών: Συγκεκριμένα, οι ακόλουθοι υπολογισμοί χρησιμοποιώντας αυτόν τον τύπο για τον αριθμό συνδυασμού (1, 3, 4, 6) n=6 στοιχείων του m=4 σε λεξιγραφική σειρά θα δώσουν το αποτέλεσμα N=8, το οποίο αντιστοιχεί στο παράδειγμα που συζητήθηκε παραπάνω: Στη γενική περίπτωση, χρησιμοποιώντας την ταυτότητα για το άθροισμα των αριθμών των συνδυασμών και για τους δύο δείκτες, είναι δυνατό να φανεί ότι ο αριθμός του λεξιγραφικά μικρότερου συνδυασμού (1, ... i, ... m) όταν υπολογίζεται χρησιμοποιώντας αυτό ο τύπος θα είναι πάντα ίσος με 1: Είναι επίσης προφανές ότι ο αριθμός του λεξιγραφικά μεγαλύτερου συνδυασμού (m, … nm+i, … n) όταν υπολογίζεται χρησιμοποιώντας αυτόν τον τύπο θα είναι ίσος με τον αριθμό των συνδυασμών n στοιχείων κατά m: Ο τύπος για τον υπολογισμό αριθμών λεξιγραφικών συνδυασμών μπορεί να χρησιμοποιηθεί για την επίλυση του αντιστρόφου προβλήματος, όπου πρέπει να προσδιορίσετε το διάνυσμα συνδυασμού με τον αριθμό του με λεξιγραφική σειρά. Για να λυθεί ένα τέτοιο αντίστροφο πρόβλημα, πρέπει να γραφτεί με τη μορφή εξίσωσης, όπου όλες οι άγνωστες τιμές των στοιχείων του διανύσματος του επιθυμητού συνδυασμού (C 1, ... C i, ... C m ) συγκεντρώνονται στους αριθμούς των συνδυασμών της δεξιάς πλευράς του και η γνωστή διαφορά L του αριθμού των συνδυασμών γράφεται στην αριστερή πλευρά n στοιχείων κάθε m και ο αριθμός του απαιτούμενου συνδυασμού N: Η λύση αυτής της εξίσωσης παρέχεται από τον ακόλουθο «άπληστο» αλγόριθμο, κατά τις επαναλήψεις του οποίου επιλέγονται διαδοχικά οι τιμές των στοιχείων του διανύσματος του επιθυμητού συνδυασμού. Στην αρχική επανάληψη, επιλέγεται η ελάχιστη δυνατή (εντός των περιορισμών της) τιμή του C 1, στην οποία ο πρώτος όρος στη δεξιά πλευρά θα έχει μέγιστη τιμή που δεν υπερβαίνει το L: Τώρα η αριστερή πλευρά του L θα πρέπει να μειωθεί κατά τον πρώτο αριθμό συνδυασμών στη δεξιά πλευρά με την επιλεγμένη τιμή C 1, και ομοίως να προσδιορίσετε την τιμή του C 2 στη δεύτερη επανάληψη: Ομοίως, όλες οι επόμενες επαναλήψεις θα πρέπει να εκτελεστούν για να επιλέξετε τις τιμές όλων των άλλων στοιχείων C i του επιθυμητού συνδυασμού, μέχρι το τελευταίο στοιχείο C m: Για προφανείς λόγους, η τιμή του τελευταίου στοιχείου C m μπορεί να προσδιοριστεί με βάση την ισότητα του αριθμού των συνδυασμών του με την υπολειμματική τιμή της αριστερής πλευράς του L: Πρέπει να σημειωθεί ότι η τιμή του τελευταίου στοιχείου του συνδυασμού C m μπορεί να βρεθεί ακόμα πιο απλά, χωρίς να απαριθμήσουμε τις πιθανές τιμές του: Η υλοποίηση των επαναλήψεων του εξεταζόμενου αλγορίθμου απεικονίζεται στο ακόλουθο παράδειγμα, όπου είναι απαραίτητο να προσδιοριστούν συνδυασμοί με τον αριθμό N=8 με λεξιγραφική σειρά, εάν n=6 και m=4: Η αλγοριθμική ικανότητα προσδιορισμού ενός συνδυασμού με έναν δεδομένο αριθμό σε λεξιγραφική σειρά μπορεί να χρησιμοποιηθεί σε διάφορες κατευθύνσεις. Ειδικότερα, κατά την απαρίθμηση συνδυασμών με λεξιγραφική σειρά, είναι απαραίτητο να διασφαλιστεί η επιστροφή σε οποιονδήποτε συνδυασμό που ελήφθη νωρίτερα, αρκεί να γνωρίζουμε μόνο τον αριθμό του. Επιπλέον, καθίσταται δυνατή η δημιουργία συνδυασμών με οποιαδήποτε σειρά, η οποία ρυθμίζεται από μια αυθαίρετα δεδομένη ακολουθία των λεξιγραφικών αριθμών τους. Τώρα παρουσιάζουμε έναν αλγόριθμο για τη δημιουργία συνδυασμών με λεξικογραφική σειρά: 2 για i:= 1 έως k κάνει A[i] := i; 5 αρχίζουν να γράφουν(A, …, A[k]); 6 αν A[k] = n τότε p:= p 1 άλλο p:= k; 8 για i:= k κάτω στο p κάνει A[i] := A[p] + i p + 1 ΣΥΝΔΥΑΣΜΟΙ ΜΕ ΕΠΑΝΑΛΗΠΤΙΚΑ ΣΤΟΙΧΕΙΑ Σε αντίθεση με έναν κλασικό συνδυασμό, όπου όλα τα στοιχεία είναι διαφορετικά, ένας συνδυασμός με επαναλήψεις σχηματίζει μια αδιάτακτη επιλογή στοιχείων ενός πεπερασμένου συνόλου, όπου οποιοδήποτε στοιχείο μπορεί να εμφανίζεται απεριόριστα συχνά και δεν υπάρχει απαραίτητα σε ένα μόνο αντίγραφο. Σε αυτή την περίπτωση, ο αριθμός των επαναλήψεων των στοιχείων συνήθως περιορίζεται μόνο από το μήκος του συνδυασμού και οι συνδυασμοί που διαφέρουν σε τουλάχιστον ένα στοιχείο θεωρούνται διαφορετικοί. Για παράδειγμα, επιλέγοντας 4 προαιρετικά διαφορετικούς αριθμούς από το σύνολο 1, 2 και 3, μπορείτε να δημιουργήσετε τους ακόλουθους 15 συνδυασμούς με επαναλήψεις: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
Γενικά, συνδυασμοί με επαναλήψεις μπορούν να σχηματιστούν επιλέγοντας n στοιχεία αυθαίρετων τύπων. Ωστόσο, μπορούν πάντα να συσχετιστούν με διαδοχικούς φυσικούς αριθμούς από το 1 έως το n. Στη συνέχεια, οποιοσδήποτε συνδυασμός m προαιρετικά διαφορετικών αριθμών σε αυτό το εύρος μπορεί να γραφτεί σε διανυσματική μορφή, ταξινομώντας τους με μη φθίνουσα σειρά από αριστερά προς τα δεξιά: Φυσικά, με αυτή τη μορφή σημειογραφίας, οποιαδήποτε γειτονικά στοιχεία μπορούν να είναι ίσα λόγω της δυνατότητας απεριόριστων επαναλήψεων. Ωστόσο, κάθε διάνυσμα συνδυασμού με επαναλήψεις n στοιχείων κατά m μπορεί να συσχετιστεί με ένα διάνυσμα συνδυασμού (n+m−1) στοιχείων κατά m, το οποίο κατασκευάζεται ως εξής: Είναι σαφές ότι για οποιεσδήποτε τιμές των στοιχείων του διανύσματος f, τα στοιχεία του διανύσματος C είναι εγγυημένα διαφορετικά και αυστηρά ταξινομημένα με αύξουσα σειρά των τιμών τους από το εύρος από 1 έως (n+m1) : Η παρουσία μιας αντιστοιχίας ένα προς ένα μεταξύ των στοιχείων των διανυσμάτων συνδυασμού f και C μας επιτρέπει να προτείνουμε την ακόλουθη απλή μέθοδο για συστηματική λίστα συνδυασμών με επαναλήψεις n στοιχείων κατά m. Είναι απαραίτητο μόνο να παραθέσουμε, για παράδειγμα, με λεξιγραφική σειρά, όλους τους συνδυασμούς C των (n+m1) στοιχείων του m, μετατρέποντας διαδοχικά τα στοιχεία καθενός από αυτά στα αντίστοιχα στοιχεία συνδυασμών με επαναλήψεις f χρησιμοποιώντας τον ακόλουθο τύπο: Ως αποτέλεσμα, σχηματίζεται μια ακολουθία διανυσμάτων συνδυασμών με επαναλήψεις στοιχείων, τα οποία είναι διατεταγμένα με τη σειρά που δημιουργείται με την παράθεση των αντίστοιχων συνδυασμών χωρίς επαναλήψεις στοιχείων. Ειδικότερα, για να ληφθεί η παραπάνω ακολουθία συνδυασμών 3 ψηφίων 1, 2 και 3 με επαναλήψεις 4 ψηφίων, είναι απαραίτητο να παραθέσουμε με λεξιγραφική σειρά όλους τους συνδυασμούς χωρίς επαναλήψεις 6 ψηφίων 1,2,3,4, 5 και 6 είναι 4 ψηφία το καθένα, μετατρέποντάς τα όπως υποδεικνύεται. Το παρακάτω παράδειγμα δείχνει μια τέτοια μετατροπή του συνδυασμού (1,3,4,6) με τον λεξικογραφικό αριθμό 8: Η θεωρούμενη αντιστοιχία ένα προς ένα μεταξύ συνδυασμών με και χωρίς επαναλήψεις στοιχείων σημαίνει ότι τα σύνολά τους είναι εξίσου ισχυρά. Επομένως, στη γενική περίπτωση, ο αριθμός των συνδυασμών με επαναλήψεις n στοιχείων κατά m είναι ίσος με τον αριθμό των συνδυασμών χωρίς επαναλήψεις (n+m1) στοιχείων κατά m. Χρησιμοποιώντας τον ίδιο συμβολισμό για να δηλώσουμε τους αριθμούς των συνδυασμών με επαναλήψεις f και χωρίς επαναλήψεις C, αυτή η ισότητα μπορεί να γραφτεί ως εξής: Είναι εύκολο να ελεγχθεί ότι για το παράδειγμα που εξετάστηκε παραπάνω, όπου n=3 και m=4, ο αριθμός των συνδυασμών επαναλήψεων θα είναι ίσος με 15, το οποίο συμπίπτει με το αποτέλεσμα της άμεσης καταχώρισής τους: Θα πρέπει να σημειωθεί ότι, σε αντίθεση με την κλασική έκδοση, οι τιμές των παραμέτρων συνδυασμού με επαναλήψεις n και m δεν σχετίζονται άμεσα μεταξύ τους, επομένως f(n,m)>0 για οποιονδήποτε συνδυασμό των θετικών τους τιμών. Οι αντίστοιχες οριακές συνθήκες καθορίζονται από την ισότητα μεταξύ των τιμών των (n+m1) και (n1) ή (n+m1) και m: Θα πρέπει επίσης να είναι αρκετά προφανές ότι εάν το m είναι ίσο με 1, τότε δεν είναι δυνατές επαναλήψεις στοιχείων και, επομένως, για οποιαδήποτε θετική τιμή n>0 θα ισχύει η ακόλουθη ισότητα: Επιπλέον, για αριθμούς συνδυασμών με επαναλήψεις για τυχόν θετικές τιμές n και m, ισχύει η ακόλουθη σχέση επανάληψης, η οποία είναι παρόμοια με την ταυτότητα πρόσθεσης για αριθμούς συνδυασμών χωρίς επαναλήψεις στοιχείων: Στην πραγματικότητα, μετατρέπεται στην υποδεικνυόμενη ταυτότητα προσθήκης κατά την επίσημη αντικατάσταση των αντίστοιχων αριθμών συνδυασμών χωρίς επαναλήψεις στην αριστερή και τη δεξιά πλευρά του: Η εξεταζόμενη σχέση επανάληψης μπορεί να χρησιμοποιηθεί για τον αποτελεσματικό προσδιορισμό του αριθμού των συνδυασμών με επαναλήψεις, όταν είναι σημαντικό να εξαλειφθούν οι πράξεις έντασης εργασίας του υπολογισμού των παραγοντικών προϊόντων και να αντικατασταθούν με απλούστερες πράξεις πρόσθεσης. Σε αυτήν την περίπτωση, για να υπολογίσετε την τιμή του f(n,m), χρειάζεται μόνο να εφαρμόσετε αυτήν τη σχέση επανάληψης μέχρι να λάβετε το άθροισμα των όρων της μορφής f(1,m) και f(i,1), όπου i παίρνει τιμές στην περιοχή από n έως 1. Εξ ορισμού της ποσότητας, οι όροι αυτοί είναι ίσοι με 1 και i, αντίστοιχα. Το ακόλουθο παράδειγμα επεξηγεί τη χρήση αυτής της τεχνικής μετασχηματισμού για την περίπτωση n=3 και m=4: ΚΑΤΑΛΟΓΗ ΔΥΑΔΙΚΩΝ ΣΥΝΔΥΑΣΜΩΝ Κατά την υλοποίηση συνδυασμών σε υλικό ή προγραμματισμό σε γλώσσα assembly, είναι σημαντικό να μπορείτε να επεξεργάζεστε εγγραφές συνδυασμού σε δυαδική μορφή. Σε αυτήν την περίπτωση, οποιοσδήποτε συνδυασμός n στοιχείων του m θα πρέπει να προσδιορίζεται με τη μορφή ενός δυαδικού αριθμού n-bit (B n,...B j,...B 1), όπου m ψηφία μονάδας δείχνουν τα στοιχεία του συνδυασμό και τα υπόλοιπα (nm) ψηφία έχουν μηδενικές τιμές. Προφανώς, με αυτή τη μορφή σημειογραφίας, διαφορετικοί συνδυασμοί πρέπει να διαφέρουν στη διάταξη των ψηφίων του 1, και υπάρχουν μόνο C(n,m) τρόποι να τακτοποιήσετε m one ή (nm) μηδενικά σε ένα δυαδικό σύνολο n-bit. Για παράδειγμα, ο παρακάτω πίνακας παραθέτει και τους 6 τέτοιους δυαδικούς συνδυασμούς, οι οποίοι παρέχουν δυαδικούς αριθμούς 4 bit για όλους τους συνδυασμούς 4 στοιχείων ενός αυθαίρετου συνόλου (E 1 , E 2 , E 3 , E 4 ) κατά 2: Στη γενική περίπτωση, το έργο της απαρίθμησης τέτοιων δυαδικών συνδυασμών καταλήγει σε μια συστηματική αναζήτηση όλων των δυαδικών συνόλων n-bit με διαφορετικές διατάξεις m ένα και (nm) μηδενικών bit. Στην απλούστερη μορφή, μια τέτοια αναζήτηση υλοποιείται με διάφορες μεθόδους μεταφοράς γειτονικών δυαδικών ψηφίων με μετατόπιση (αλγόριθμοι transpositive-shift). Αυτοί είναι επαναληπτικοί αλγόριθμοι και τα ονόματά τους αντικατοπτρίζουν τη φύση των λειτουργιών που εκτελούνται σε κάθε βήμα. Οι επαναληπτικές διαδικασίες των αλγορίθμων transpositive-shift σχηματίζουν ακολουθίες δυαδικών συνδυασμών που ξεκινούν με ένα δυαδικό σύνολο, όπου όλα συγκεντρώνονται στα ψηφία χαμηλής τάξης (στα δεξιά) και τελειώνουν όταν όλα τα 1 είναι στα ψηφία υψηλής τάξης ( στα αριστερά): Ενώ ταιριάζουν σε αρχικούς και τελικούς συνδυασμούς, αυτές οι ακολουθίες διαφέρουν ως προς τη σειρά με την οποία παρατίθενται τα ενδιάμεσα δυαδικά σύνολα. Ωστόσο, σε όλες τις περιπτώσεις, κάθε επόμενος δυαδικός συνδυασμός σχηματίζεται από τον προηγούμενο ως αποτέλεσμα της εκτέλεσης των αντίστοιχων πράξεων μεταφοράς και μετατόπισης. Ταυτόχρονα, διάφοροι αλγόριθμοι transpositive-shift διαφέρουν στον τρόπο με τον οποίο επιλέγουν ένα ζεύγος bit για μεταφορά και μια ομάδα bit για μετατόπιση. Αυτή η ειδικότητα συζητείται παρακάτω για αλγόριθμους μεταφοράς με μετατόπιση προς τα αριστερά και προς τα δεξιά. Στον αλγόριθμο μεταφοράς με αριστερή μετατόπιση, σε κάθε βήμα ο επόμενος δυαδικός συνδυασμός λαμβάνεται από τον τρέχοντα αντικαθιστώντας το αριστερό ζεύγος ψηφίων 01 με 10 (μεταφορά) και μετατοπίζοντας την ομάδα των αρχικών ψηφίων μονάδας, εάν υπάρχει, κοντά στο ζεύγος 10 που λαμβάνεται μετά τη μεταφορά (μετατόπιση). Εάν σε αυτήν την περίπτωση δεν υπάρχουν μονάδες στα πρώτα ψηφία στον τρέχοντα δυαδικό συνδυασμό, τότε η μετατόπιση δεν εκτελείται, ακόμη και όταν η κύρια μονάδα λαμβάνεται μετά τη μεταφορά σε αυτό το βήμα. Η μετατόπιση δεν εκτελείται επίσης όταν δεν υπάρχουν μηδενικά στα πιο σημαντικά bit πριν από το ζεύγος 10 που λαμβάνεται μετά τη μεταφορά. Οι εξεταζόμενες ενέργειες απεικονίζονται από το ακόλουθο παράδειγμα εκτέλεσης δύο διαδοχικών επαναλήψεων αυτού του αλγορίθμου, όπου στη μία επανάληψη (15) εκτελείται μόνο η μεταφορά (T") και στην άλλη επανάληψη (16) η μεταφορά συμπληρώνεται από μια μετατόπιση ( T"+S"): Στον αλγόριθμο μεταφοράς δεξιάς μετατόπισης, εκτελούνται εννοιολογικά παρόμοια βήματα σε κάθε βήμα. Μόνο η μεταφορά διασφαλίζει ότι τα πιο δεξιά bit του 01 αντικαθίστανται από 10 (αντί για τα πιο αριστερά), και στη συνέχεια όλα τα δεξιά από αυτό μετατοπίζονται στα λιγότερο σημαντικά bit. Όπως και πριν, η μετατόπιση εκτελείται μόνο εάν υπάρχουν μονάδες που μπορούν να μετακινηθούν προς τα δεξιά. Οι εξεταζόμενες ενέργειες απεικονίζονται από το ακόλουθο παράδειγμα εκτέλεσης δύο διαδοχικών επαναλήψεων αυτού του αλγορίθμου, όπου στη μία επανάληψη (3) εκτελείται μόνο η μεταφορά (T") και στην άλλη επανάληψη (4) η μεταφορά συμπληρώνεται από μια μετατόπιση ( T"+S"): Πρέπει να σημειωθεί ότι οι επαναλήψεις και των δύο αλγορίθμων μπορούν να γραφούν σε προσθετική μορφή εάν οι δυαδικοί συνδυασμοί ερμηνεύονται ως ακέραιοι στο σύστημα αριθμών βάσης 2. Ειδικότερα, για τον αλγόριθμο μεταφοράς με δεξιά μετατόπιση, κάθε επόμενος δυαδικός συνδυασμός (B" n ,…B" j , …B" 1), μπορεί πάντα να ληφθεί από τον τρέχοντα συνδυασμό (B n,…B j,…B 1) εκτελώντας τις πράξεις της πρόσθεσης ακεραίων χρησιμοποιώντας τον ακόλουθο τύπο πρόσθετου: Σε αυτόν τον αθροιστικό τύπο, οι εκθέτες των δυνάμεων των δύο f και t δηλώνουν, αντίστοιχα, τον αριθμό των μηδενικών ψηφίων χαμηλής τάξης του τρέχοντος δυαδικού συνδυασμού και τον αριθμό των μονάδων στη σειρά στα αριστερά τους. Για παράδειγμα, για τον 4ο δυαδικό συνδυασμό (001110) n=6 ψηφίων f =1 και t =3. Επομένως, ο υπολογισμός του επόμενου δυαδικού συνδυασμού χρησιμοποιώντας τον τύπο πρόσθετου στην επανάληψη 5 θα δώσει το ακόλουθο αποτέλεσμα, ισοδύναμο με την εκτέλεση των πράξεων μεταφοράς και μετατόπισης: Για μια συγκριτική ανάλυση των εξεταζόμενων αλγορίθμων μεταφοράς με μετατοπίσεις προς τα αριστερά και προς τα δεξιά, είναι σκόπιμο να συγκριθούν οι ακολουθίες δυαδικών συνδυασμών που δημιουργούν στις επαναλήψεις τους. Ο παρακάτω πίνακας δείχνει δύο τέτοιες ακολουθίες δυαδικών συνδυασμών 4 στοιχείων του 2, που λαμβάνονται από τον αλγόριθμο μετατόπισης αριστερά (TSL) και δεξιά (TSR), αντίστοιχα: Συγκρίνοντας αυτές τις 2 ακολουθίες, μπορείτε να δείτε ότι είναι αντίστροφος καθρέφτης. Αυτό σημαίνει ότι οποιοιδήποτε δύο δυαδικοί συνδυασμοί που βρίσκονται σε αυτούς στην ίδια απόσταση από τα αμοιβαία αντίθετα άκρα των ακολουθιών τους είναι κατοπτρική εικόνα ο ένας του άλλου, δηλαδή συμπίπτουν όταν αντιστρέφεται η ευρετηρίαση των bit σε οποιοδήποτε από αυτά. Για παράδειγμα, το δεύτερο δυαδικό μοτίβο από την αρχή της ακολουθίας TSL (0101) είναι μια κατοπτρική εικόνα του δυαδικού σχεδίου (1010) που είναι δεύτερο από το τέλος της ακολουθίας TSR. Γενικά, οποιοσδήποτε δυαδικός συνδυασμός με τον αριθμό i μιας ακολουθίας είναι μια κατοπτρική εικόνα ενός δυαδικού συνδυασμού με τον αριθμό (ni+1) μιας άλλης ακολουθίας. Αυτή η σχέση μεταξύ αυτών των ακολουθιών είναι συνέπεια της συμμετρικής φύσης των πράξεων μεταφοράς και μετατόπισης στους δύο εξεταζόμενους αλγόριθμους για την απαρίθμηση δυαδικών συνδυασμών. Θα πρέπει να σημειωθεί ότι η δυαδική μορφή μπορεί επίσης να χρησιμοποιηθεί για την εγγραφή συνδυασμών με επαναλήψεις στοιχείων. Για να γίνει αυτό, είναι απαραίτητο να δημιουργηθεί μια αντιστοιχία ένα προς ένα μεταξύ συνδυασμών με επαναλήψεις και δυαδικούς συνδυασμούς, οι οποίοι κατασκευάζονται ως εξής. Έστω ένας αυθαίρετος συνδυασμός με επαναλήψεις, ο οποίος προκύπτει επιλέγοντας m προαιρετικά διαφορετικά στοιχεία από τα n στοιχεία του συνόλου παραγωγής. Για να δημιουργήσετε την επιθυμητή αντιστοίχιση, πρέπει πρώτα να προσθέσετε όλα τα στοιχεία του συνόλου σχηματισμού (γάτα) στον συνδυασμό και, στη συνέχεια, να ταξινομήσετε την προκύπτουσα συνένωση (ταξινόμηση) έτσι ώστε όλα τα πανομοιότυπα στοιχεία να είναι δίπλα-δίπλα. Το αποτέλεσμα είναι μια ακολουθία (n+m) στοιχείων, όπου υπάρχουν n ομάδες πανομοιότυπων στοιχείων. Θα υπάρχουν συνολικά (n+m1) κενά μεταξύ των στοιχείων, μεταξύ των οποίων θα υπάρχουν (n1) κενά μεταξύ ομάδων πανομοιότυπων στοιχείων και m κενά μεταξύ στοιχείων εντός ομάδων. Για λόγους σαφήνειας, μπορείτε να τοποθετήσετε τα σύμβολα "|" στα υποδεικνυόμενα κενά. και αντίστοιχα. Αν τώρα αντιστοιχίσουμε το 1 στα κενά μεταξύ των ομάδων (|) και το 0 με όλα τα άλλα κενά (), παίρνουμε έναν δυαδικό συνδυασμό. Σχηματίζεται από ένα δυαδικό σύνολο (n+m1) bit, όπου (n1) είναι ένα και m μηδέν bit, η θέση των οποίων αντιστοιχεί μοναδικά στον αρχικό συνδυασμό με επαναλήψεις των στοιχείων n έως m. Η εξεταζόμενη τεχνική μετασχηματισμού απεικονίζεται από το ακόλουθο παράδειγμα κατασκευής ενός δυαδικού συνδυασμού (1001101) χρησιμοποιώντας έναν συνδυασμό με επαναλήψεις (BBD), τα στοιχεία του οποίου επιλέγονται από το σύνολο παραγωγής των πρώτων πέντε λατινικών γραμμάτων: Γενικά, ο αριθμός τέτοιων δυαδικών συνόλων καθορίζει τον αριθμό των τρόπων διάταξης (n1) μονάδων (ή m μηδενικών) σε (n+m1) δυαδικά ψηφία. Αυτή η τιμή είναι προφανώς ίση με τον αριθμό των συνδυασμών από (n+m1) κατά (n1) ή κατά m, δηλαδή C(n+m1,n1) ή C(n+m1,m), που είναι ίσος με το αριθμός συνδυασμών με επαναλήψεις f( n,m) n στοιχείων, m το καθένα. Έτσι, έχοντας μια αντιστοιχία ένα προς ένα μεταξύ συνδυασμών με επαναλήψεις και δυαδικούς συνδυασμούς, είναι θεμιτό να μειωθεί η απαρίθμηση συνδυασμών με επαναλήψεις σε απαρίθμηση δυαδικών συνδυασμών, για παράδειγμα, χρησιμοποιώντας αλγόριθμους μεταφοράς με μετατόπιση προς τα αριστερά ή προς τα δεξιά. Μετά από αυτό, χρειάζεται μόνο να επαναφέρετε τους απαιτούμενους συνδυασμούς με επαναλήψεις χρησιμοποιώντας τους προκύπτοντες δυαδικούς συνδυασμούς. Αυτό μπορεί πάντα να γίνει χρησιμοποιώντας την ακόλουθη τεχνική ανάκτησης. Αφήστε το κύριο σύνολο, από τα στοιχεία του οποίου σχηματίζονται συνδυασμοί με επαναλήψεις του m όχι απαραίτητα διαφορετικά στοιχεία, να ταξινομηθεί με αυθαίρετο τρόπο ώστε κάθε στοιχείο του να έχει έναν ορισμένο αύξοντα αριθμό από το 1 έως το n. Ας εφαρμόσουμε επίσης την απαρίθμηση δυαδικών συνδυασμών (n+m1) δυαδικών ψηφίων, όπου (n1) ένα και m μηδενικά ψηφία. Κάθε δυαδικός συνδυασμός που προκύπτει μπορεί να συμπληρωθεί στα αριστερά με ένα εικονικό ψηφίο μονάδας και όλα τα ψηφία μονάδας μπορούν να αριθμηθούν από αριστερά προς τα δεξιά με ακέραιους αριθμούς από το 1 έως το n. Τότε ο αριθμός των μηδενικών στη σειρά μετά από κάθε i-η μονάδα του δυαδικού συνδυασμού θα είναι ίσος με τον αριθμό των περιπτώσεων του i-ου στοιχείου του κύριου συνόλου στον αντίστοιχο συνδυασμό με επαναλήψεις. Η εξεταζόμενη τεχνική απεικονίζεται από το ακόλουθο παράδειγμα, όπου, χρησιμοποιώντας έναν δυαδικό συνδυασμό (1001101), αποκαθίσταται ένας συνδυασμός με επαναλήψεις του BBD, τα στοιχεία του οποίου επιλέγονται από το σύνολο παραγωγής των πρώτων πέντε λατινικών γραμμάτων, γραμμένα με αλφαβητική σειρά , και η υπεργραμμή υποδεικνύει στοιχεία που απουσιάζουν σε αυτόν τον συνδυασμό: Εκτελώντας παρόμοιες ενέργειες στις συνθήκες αυτού του παραδείγματος, μπορείτε να απαριθμήσετε και τους 35 δυαδικούς συνδυασμούς που σχηματίζουν δυαδικά σύνολα 7-bit, όπου υπάρχουν 4 ένα και 3 μηδενικά, και να επαναφέρετε τους αντίστοιχους συνδυασμούς με επαναλήψεις 5 στοιχείων του 3. Παράδειγμα // Συνδυασμοί 3 από 52 για (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Εδώ θα εξετάσουμε ένα πιο περίπλοκο πρόβλημα, τη λύση του οποίου δεν έχω βρει στο RuNet (ωστόσο, θα δώσω έναν σύνδεσμο, αλλά αυτός ο τύπος είναι σαφώς λανθασμένος) - με βάση τον ίδιο τον συνδυασμό (στην περίπτωση αυτή, ένα σύνολο τρεις αριθμοί) βρείτε το ευρετήριό του. Ας υποθέσουμε, για βεβαιότητα, αφού διατάξουμε i1 = 3, i2 = 7, i3 = 12. Ένας τυπικός αλγόριθμος παραγωγής είναι ότι δημιουργούμε συνδυασμούς 2 από 52 και για κάθε τέτοιο συνδυασμό σε ένθετο βρόχο δημιουργούμε συνδυασμούς 3 από 50 και ελέγχουμε ότι οι δείκτες (i3, i4, i5) στον ένθετο συνδυασμό κάνουν δεν συμπίπτουν με τους δείκτες (i1, i2) σε εξωτερικό συνδυασμό: Κωδικός C++ // ΕΞΩΤΕΡΙΚΟΣ ΣΥΝΔΥΑΣΜΟΣ για (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
Κωδικός C++ αν (i3 >= i1) --i3; αν (i3 >= i2) --i2; // παρόμοια για i4, i5 Παράδειγμα κώδικα για διαχωρισμό ευρετηρίου κατά 2, 3, 47 int get_split_2_3_47_index(int · i1, int i2, int i3, int i4, int i5) ( // Ευρετήριο του συνδυασμού 2 από 52, πολλαπλασιαζόμενο με C(3, 50) int offset = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // "Επαναριθμήστε" την εσωτερική ομάδα έτσι ώστε η αρίθμηση να είναι 0...49 εάν (i3 > = i1) --i3· εάν (i3 >= i2) --i3· εάν (i4 >= i1) --i4· εάν (i4 >= i2) --i4· εάν (i5 >= i1) --i5 ; αν (i5 >= i2) --i5; // Τώρα προσθέστε τον δείκτη του συνδυασμού κατά 3 // 0: // SUM για n = 0 κατά i3-1 ΣΥΝΔΥΑΣΜΟΙ (2, 49-n) // = SUM για m = 50-i3 επί 49 (m * (m-1) / 2) μετατόπιση += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) / 2); // 1: // SUM για n = i3+1 έως i4-1 ΣΥΝΔΥΑΣΜΟΙ (1, 49-n) μετατόπιση += (( (48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // SUM για n = i4+1 έως i5-1 (1) μετατόπιση + = (i5 - i4 - 1); μετατόπιση επιστροφής ; ) Γενικά, θα διαιρούσα τους συνδυαστικούς αλγόριθμους στις ακόλουθες κατηγορίες: Αριθμός συνδυασμών Συνδυασμόςαπό nΜε κονομάζεται σετ κστοιχεία που επιλέγονται από δεδομένα nστοιχεία. Τα σύνολα που διαφέρουν μόνο ως προς τη σειρά των στοιχείων (αλλά όχι στη σύνθεση) θεωρούνται πανομοιότυπα· γι' αυτό οι συνδυασμοί διαφέρουν από τις τοποθετήσεις. Αριθμός συνδυασμών των nΜε κ
ίσο με τον διωνυμικό συντελεστή Για σταθερή τιμή nσυνάρτηση παραγωγής αριθμών συνδυασμών με επαναλήψεις από nΜε κείναι: Η δισδιάστατη συνάρτηση δημιουργίας αριθμών συνδυασμών με επαναλήψεις είναι: Ίδρυμα Wikimedia. 2010. 70 εβδομήντα 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Παραγοντοποίηση: 2×5×7 Ρωμαϊκή σημείωση: LXX Δυαδική: 100 0110 ... Wikipedia Αριθμός φωτός, αριθμός υπό όρους που εκφράζει μοναδικά το εξωτερικό συνθήκες κατά τη φωτογράφιση (συνήθως η φωτεινότητα του θέματος και η φωτοευαισθησία του φωτογραφικού υλικού που χρησιμοποιείται). Οποιαδήποτε τιμή E. h. μπορεί να επιλεγεί πολλές φορές. συνδυασμοί αριθμός διαφράγματος... ... Μεγάλο Εγκυκλοπαιδικό Πολυτεχνικό Λεξικό Μια μορφή αριθμού που διακρίνει δύο αντικείμενα τόσο σε σχέση με ένα μόνο αντικείμενο όσο και σε σχέση με πολλά αντικείμενα. Αυτή η μορφή δεν υπάρχει στα σύγχρονα ρωσικά, αλλά παραμένουν απομεινάρια της επιρροής της. Έτσι, συνδυασμοί δύο πινάκων (πρβλ. πληθυντικός... ... Λεξικό γλωσσικών όρων Συνδυαστικά μαθηματικά, συνδυαστική, κλάδος των μαθηματικών αφιερωμένος στην επίλυση προβλημάτων επιλογής και διάταξης στοιχείων ενός συγκεκριμένου, συνήθως πεπερασμένου, συνόλου σύμφωνα με δεδομένους κανόνες. Κάθε τέτοιος κανόνας καθορίζει τη μέθοδο κατασκευής... ... Μαθηματική Εγκυκλοπαίδεια Στη συνδυαστική, ένας συνδυασμός by είναι ένα σύνολο στοιχείων που επιλέγονται από ένα δεδομένο σύνολο που περιέχει διαφορετικά στοιχεία. Σύνολα που διαφέρουν μόνο ως προς τη σειρά των στοιχείων (αλλά όχι στη σύνθεση) θεωρούνται πανομοιότυπα, αυτοί οι συνδυασμοί ... ... Wikipedia Ασχολείται με τη μελέτη γεγονότων η εμφάνιση των οποίων δεν είναι γνωστή με βεβαιότητα. Μας επιτρέπει να κρίνουμε το εύλογο να περιμένουμε την εμφάνιση κάποιων γεγονότων σε σύγκριση με άλλα, αν και η ανάθεση αριθμητικών τιμών στις πιθανότητες γεγονότων είναι συχνά περιττή... ... Εγκυκλοπαίδεια Collier 1) το ίδιο με τη μαθηματική συνδυαστική ανάλυση. 2) Ένα τμήμα στοιχειωδών μαθηματικών που σχετίζεται με τη μελέτη του αριθμού των συνδυασμών, υπό ορισμένες προϋποθέσεις, που μπορεί να συντεθεί από ένα δεδομένο πεπερασμένο σύνολο αντικειμένων... ... Μεγάλη Σοβιετική Εγκυκλοπαίδεια - (ελληνικά παράδοξα απροσδόκητα, περίεργα) με την ευρεία έννοια: μια δήλωση που αποκλίνει έντονα από τη γενικά αποδεκτή, καθιερωμένη άποψη, μια άρνηση αυτού που φαίνεται «άνευ όρων σωστό»· με στενότερη έννοια, δύο αντίθετες δηλώσεις, για... ... Φιλοσοφική Εγκυκλοπαίδεια - (ή η αρχή των εγκλεισμών και εξαιρέσεων) ένας συνδυαστικός τύπος που σας επιτρέπει να προσδιορίσετε την ιδιότητα της ένωσης ενός πεπερασμένου αριθμού πεπερασμένων συνόλων, τα οποία στη γενική περίπτωση μπορούν να τέμνονται μεταξύ τους ... Wikipedia Μια μαθηματική θεωρία που ασχολείται με τον προσδιορισμό του αριθμού των διαφορετικών τρόπων κατανομής δεδομένων αντικειμένων με μια γνωστή σειρά. είναι ιδιαίτερα σημαντικό στη θεωρία των εξισώσεων και στη θεωρία πιθανοτήτων. Οι απλούστερες εργασίες αυτού του είδους είναι... ... Εγκυκλοπαιδικό Λεξικό F.A. Brockhaus και I.A. Έφρων Η συνδυαστική είναι ένας κλάδος των μαθηματικών που μελετά ερωτήματα σχετικά με το πόσοι διαφορετικοί συνδυασμοί, υπό ορισμένες συνθήκες, μπορούν να γίνουν από δεδομένα αντικείμενα. Τα βασικά στοιχεία της συνδυαστικής είναι πολύ σημαντικά για την εκτίμηση των πιθανοτήτων τυχαίων γεγονότων, επειδή Είναι αυτοί που μας επιτρέπουν να υπολογίσουμε τον ουσιαστικά δυνατό αριθμό διαφορετικών σεναρίων για την εξέλιξη των γεγονότων. Έστω k ομάδες στοιχείων, και η i-η ομάδα αποτελείται από n i στοιχεία. Ας επιλέξουμε ένα στοιχείο από κάθε ομάδα. Τότε ο συνολικός αριθμός N των τρόπων με τους οποίους μπορεί να γίνει μια τέτοια επιλογή προσδιορίζεται από τη σχέση N=n 1 *n 2 *n 3 *...*n k . Παράδειγμα 1.Ας εξηγήσουμε αυτόν τον κανόνα με ένα απλό παράδειγμα. Έστω δύο ομάδες στοιχείων, και η πρώτη ομάδα αποτελείται από n 1 στοιχεία και η δεύτερη - από n 2 στοιχεία. Πόσα διαφορετικά ζεύγη στοιχείων μπορούν να γίνουν από αυτές τις δύο ομάδες, έτσι ώστε το ζεύγος να περιέχει ένα στοιχείο από κάθε ομάδα; Ας πούμε ότι πήραμε το πρώτο στοιχείο από την πρώτη ομάδα και, χωρίς να το αλλάξουμε, περάσαμε από όλα τα πιθανά ζεύγη, αλλάζοντας μόνο τα στοιχεία από τη δεύτερη ομάδα. Μπορεί να υπάρχουν n 2 τέτοια ζεύγη για αυτό το στοιχείο. Στη συνέχεια παίρνουμε το δεύτερο στοιχείο από την πρώτη ομάδα και φτιάχνουμε επίσης όλα τα πιθανά ζεύγη για αυτό. Θα υπάρχουν επίσης n 2 τέτοια ζευγάρια. Εφόσον υπάρχουν μόνο n 1 στοιχεία στην πρώτη ομάδα, οι συνολικές πιθανές επιλογές θα είναι n 1 *n 2 . Παράδειγμα 2.Πόσοι τριψήφιοι ζυγοί αριθμοί μπορούν να γίνουν από τα ψηφία 0, 1, 2, 3, 4, 5, 6, αν τα ψηφία μπορούν να επαναληφθούν; Στην περίπτωση που όλες οι ομάδες αποτελούνται από τον ίδιο αριθμό στοιχείων, δηλ. n 1 =n 2 =...n k =n μπορούμε να υποθέσουμε ότι κάθε επιλογή γίνεται από την ίδια ομάδα και το στοιχείο μετά την επιλογή επιστρέφεται στην ομάδα. Τότε ο αριθμός όλων των μεθόδων επιλογής είναι n k . Αυτή η μέθοδος επιλογής στη συνδυαστική ονομάζεται δείγματα με επιστροφή. Παράδειγμα 3.Πόσοι τετραψήφιοι αριθμοί μπορούν να γίνουν από τα ψηφία 1, 5, 6, 7, 8; Θεωρήστε ένα σύνολο που αποτελείται από n στοιχεία. Στη συνδυαστική αυτό το σύνολο ονομάζεται γενικός πληθυσμός. Ορισμός 1.Διαμονή από nστοιχεία από Μστη συνδυαστική οποιαδήποτε παραγγελθέν σεταπό Μδιάφορα στοιχεία επιλεγμένα από τον πληθυσμό σε nστοιχεία. Παράδειγμα 4.Διαφορετικές διατάξεις τριών στοιχείων (1, 2, 3) επί δύο θα είναι τα σύνολα (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3 , 2). Οι τοποθετήσεις μπορεί να διαφέρουν μεταξύ τους τόσο ως προς τα στοιχεία όσο και ως προς τη σειρά τους. Ο αριθμός των τοποθετήσεων στα συνδυαστικά συμβολίζεται με A n m και υπολογίζεται από τον τύπο: Σχόλιο: n!=1*2*3*...*n (διαβάστε: «en παραγοντικό»), επιπλέον, υποτίθεται ότι 0!=1. Παράδειγμα 5. Πόσοι διψήφιοι αριθμοί υπάρχουν στους οποίους το ψηφίο των δεκάδων και το ψηφίο των μονάδων είναι διαφορετικά και περιττά; Ορισμός 2. Συνδυασμόςαπό nστοιχεία από Μστη συνδυαστική οποιαδήποτε σετ χωρίς παραγγελίααπό Μδιάφορα στοιχεία επιλεγμένα από τον πληθυσμό σε nστοιχεία. Παράδειγμα 6. Για το σετ (1, 2, 3), οι συνδυασμοί είναι (1, 2), (1, 3), (2, 3). Ο αριθμός των συνδυασμών συμβολίζεται με C n m και υπολογίζεται με τον τύπο: Παράδειγμα 7.Με πόσους τρόπους μπορεί ένας αναγνώστης να επιλέξει δύο βιβλία από τα έξι διαθέσιμα; Λύση:Ο αριθμός των μεθόδων είναι ίσος με τον αριθμό των συνδυασμών έξι βιβλίων των δύο, δηλ. ισούται με: Ορισμός 3. Μετάθεσηαπό nτα στοιχεία ονομάζονται οποιαδήποτε παραγγελθέν σεταυτά τα στοιχεία. Παράδειγμα 7α.Όλες οι πιθανές μεταθέσεις ενός συνόλου που αποτελείται από τρία στοιχεία (1, 2, 3) είναι: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , ( 3, 2, 1), (3, 1, 2). Ο αριθμός των διαφορετικών μεταθέσεων n στοιχείων συμβολίζεται με P n και υπολογίζεται με τον τύπο P n =n!. Παράδειγμα 8.Με πόσους τρόπους μπορούν να τακτοποιηθούν επτά βιβλία διαφορετικών συγγραφέων σε μια σειρά σε ένα ράφι; Λύση:Αυτό το πρόβλημα αφορά τον αριθμό των μεταθέσεων επτά διαφορετικών βιβλίων. Υπάρχουν P 7 =7!=1*2*3*4*5*6*7=5040 τρόποι για να τακτοποιήσετε τα βιβλία. Συζήτηση.Βλέπουμε ότι ο αριθμός των πιθανών συνδυασμών μπορεί να υπολογιστεί σύμφωνα με διαφορετικούς κανόνες (μεταθέσεις, συνδυασμοί, τοποθετήσεις) και το αποτέλεσμα θα είναι διαφορετικό, γιατί Η αρχή υπολογισμού και οι ίδιοι οι τύποι είναι διαφορετικοί. Κοιτάζοντας προσεκτικά τους ορισμούς, θα παρατηρήσετε ότι το αποτέλεσμα εξαρτάται από πολλούς παράγοντες ταυτόχρονα. Πρώτον, από πόσα στοιχεία μπορούμε να συνδυάσουμε τα σύνολα τους (πόσο μεγάλο είναι το σύνολο των στοιχείων). Δεύτερον, το αποτέλεσμα εξαρτάται από το μέγεθος των συνόλων στοιχείων που χρειαζόμαστε. Τέλος, είναι σημαντικό να γνωρίζουμε αν η σειρά των στοιχείων στο σετ είναι σημαντική για εμάς. Ας εξηγήσουμε τον τελευταίο παράγοντα χρησιμοποιώντας το ακόλουθο παράδειγμα. Παράδειγμα 9.Υπάρχουν 20 άτομα παρόντα στη συνάντηση γονέων. Πόσες διαφορετικές επιλογές υπάρχουν για τη σύνθεση της γονικής επιτροπής εάν πρέπει να περιλαμβάνει 5 άτομα; Τα πράγματα θα είναι διαφορετικά εάν κάθε μέλος της επιτροπής είναι αρχικά υπεύθυνο για έναν συγκεκριμένο τομέα εργασίας. Έπειτα, με την ίδια σύνθεση λίστας της επιτροπής, είναι ενδεχομένως 5 εντός αυτής! επιλογές μεταθέσειςαυτό το θέμα. Ο αριθμός των διαφορετικών επιλογών (τόσο στη σύνθεση όσο και στην περιοχή ευθύνης) καθορίζεται σε αυτήν την περίπτωση από τον αριθμό τοποθετήσειςαπό 20 στοιχεία 5 το καθένα. Εργασίες αυτοδιαγνωστικού ελέγχου 2. Πόσοι πενταψήφιοι αριθμοί υπάρχουν που διαβάζονται το ίδιο από αριστερά προς τα δεξιά και από τα δεξιά προς τα αριστερά; 3. Υπάρχουν δέκα μαθήματα στην τάξη και πέντε μαθήματα την ημέρα. Με πόσους τρόπους μπορείτε να δημιουργήσετε ένα πρόγραμμα για μία ημέρα; 4. Με πόσους τρόπους μπορούν να επιλεγούν 4 εκπρόσωποι για ένα συνέδριο εάν υπάρχουν 20 άτομα στην ομάδα; 5. Με πόσους τρόπους μπορούν να τοποθετηθούν οκτώ διαφορετικά γράμματα σε οκτώ διαφορετικούς φακέλους, αν τοποθετηθεί μόνο ένα γράμμα σε κάθε φάκελο; 6. Μια επιτροπή αποτελούμενη από δύο μαθηματικούς και έξι οικονομολόγους θα πρέπει να αποτελείται από τρεις μαθηματικούς και δέκα οικονομολόγους. Με πόσους τρόπους μπορεί να γίνει αυτό;Δείκτης συνδυασμού
Κάθε συνδυασμός, μετάθεση, διάταξη και άλλα συνδυαστικά αντικείμενα μπορούν να συσχετιστούν με ένα ευρετήριο - αυτός είναι ο αριθμός στον οποίο εμφανίζεται κατά την επανάληψη μέσω αυτού του αλγόριθμου.
Υπάρχει μια επιλογή αναζήτησης "κατά μέτωπο". Ενεργοποιούμε τον μετρητή συνδυασμού, ακολουθούμε τον παραπάνω αλγόριθμο και δοκιμάζουμε τα πάντα μέχρι να φτάσουμε στην επιθυμητή επιλογή. Αυτή η επιλογή έχει πολύ μεγάλη χρονική πολυπλοκότητα, επομένως θα απορρίψουμε αυτήν την επιλογή.
Ας υποθέσουμε ότι η είσοδος περιέχει τους αριθμούς i1, i2, i3. Πρώτα απ 'όλα, πρέπει να τα ταξινομήσουμε σε αύξουσα σειρά (σημειώστε ότι ο ίδιος ο αλγόριθμος δημιουργίας, που δίνεται παραπάνω, τα παράγει πάντα σε διατεταγμένη μορφή, αν και η ίδια η έννοια του "συνδυασμού" συνεπάγεται μια αυθαίρετη σειρά).
Αυτό σημαίνει ότι «περάσαμε» όλους τους συνδυασμούς όπου το i1 ήταν ίσο με 0, 1 και 2.
Για i1 = 0, έχουμε περάσει από συνδυασμούς C(2, 51), αφού οι δείκτες i1, i2 περνούν από όλους τους συνδυασμούς 2 από τους 51 αριθμούς.
Για i1 = 1 περάσαμε από συνδυασμούς C(2, 50).
Για i1 = 2 περάσαμε από συνδυασμούς C(2, 49).
Συνολικά, περάσαμε από το SUM (από n = 0 σε n = i1-1) C(2, 51-n).
Για i1 = 3, ας εξετάσουμε αυτούς τους συνδυασμούς που περάσαμε κατά τη διάρκεια του δείκτη i2 (και για εμάς ξεκινά με i2 = i1+1 = 4).
Όταν i2 = 4, C(1, 47) συνδυασμοί πέρασαν, όταν i2 = 5, C(1, 46) συνδυασμοί πέρασαν, όταν i2 = 6, C(1, 45) συνδυασμοί πέρασαν.
Κατ' πλήρη αναλογία, για i2 = 7 θεωρούμε τους συνδυασμούς στους οποίους διεξήχθη ο δείκτης i3.
Παίρνουμε τον γενικό τύπο:
Ο απαιτούμενος δείκτης συνδυασμού = SUM (από n = 0 έως i1-1) C(2, 51-n) + SUM (από n = i1+1 έως i2-1) C(1, 51-n) + SUM (από η = i2+1 έως i3-1) C (0, 51-n).Ευρετήριο υποσυνόλου
Στη συνδυαστική υπάρχει ένα πιο σύνθετο αντικείμενο - χωρισμός σε υποσύνολα. Για παράδειγμα, ο διαχωρισμός ενός συνόλου 52 στοιχείων σε τρία υποσύνολα, για παράδειγμα, 2, 3 και 47 στοιχείων, αντίστοιχα, όπου η σειρά των στοιχείων σε κάθε υποσύνολο δεν είναι σημαντική. (Παρεμπιπτόντως, ένας συνδυασμός 2 από 52 είναι απλώς μια ειδική περίπτωση διαχωρισμού σε δύο υποσύνολα των 2 και 50 στοιχείων, αντίστοιχα).
Και πάλι, κάθε τέτοιο διαμέρισμα έχει το δικό του ευρετήριο.
Αποδεικνύεται ότι ο αλγόριθμός μας για την εύρεση του δείκτη συνδυασμού μπορεί να τροποποιηθεί για να βρεθεί ο δείκτης διαμερισμάτων.
Πρέπει να σημειωθεί ότι πρέπει να τακτοποιήσουμε τους δείκτες στον «εξωτερικό συνδυασμό» i1, i2 μεταξύ τους και οι δείκτες i3, i4, i5 μεταξύ τους, αλλά ανεξάρτητα από τους δύο πρώτους.
Θα πρέπει επίσης να ληφθεί υπόψη ότι σε έναν "φωλιασμένο συνδυασμό" ουσιαστικά εργαζόμαστε με ένα σύνολο 50 στοιχείων, αλλά οι δείκτες i3, i4, i5 πρέπει να "μετατοπιστούν" με συγκεκριμένο τρόπο, ώστε να μην αλλάζουν από το 0. έως 51, αλλά από 0 έως 49:
(έτσι, κόβουμε τους δείκτες i1, i2 από το σύνολο 52 στοιχείων μας και μετά μετατοπίζουμε το υπόλοιπο σύνολο για να κλείσουμε τις τρύπες, ενώ οι δείκτες i3-i5 μετατοπίζονται).
Θα πρέπει να ληφθεί υπόψη ότι μέσα σε κάθε «εξωτερικό» συνδυασμό έχουμε ακριβώς C(3, 50) «φωλιασμένους» συνδυασμούς.
Τότε ο αλγόριθμος θα μειωθεί στα εξής:
COMBINATION_INDEX (i1, i2 από 52) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX (i3, i4, i5 από 50 μετά τη μετατόπιση ευρετηρίου). Φέρνοντας τους αλγόριθμους σε σταθερή πολυπλοκότητα
Θα πρέπει να σημειώσω αμέσως ότι εμφανίζεται ένα "σφάλμα" στον τύπο εάν, για παράδειγμα, i1 = 0 (μετράμε το άθροισμα για n = από 0 έως -1) ή i2 = 1 (μετράμε το άθροισμα από 1 έως 0). Μάλιστα, σε τέτοιες περιπτώσεις το αντίστοιχο άθροισμα θα πρέπει να λαμβάνεται ίσο με το μηδέν και το αποτέλεσμα θα είναι σωστό.
Θα πρέπει επίσης να δώσω προσοχή στη χρονική πολυπλοκότητα των αλγορίθμων μας: έχουν γραμμική πολυπλοκότητα, με την προϋπόθεση ότι θεωρείτε ότι το C είναι σταθερός χρόνος. Αυτό είναι ήδη πολύ καλύτερο από την ωμή βία.
Αλλά στην πραγματικότητα (στην περίπτωσή μας 52) τίποτα δεν μας εμποδίζει να μειώσουμε τον αλγόριθμο σε σταθερή πολυπλοκότητα. Για να γίνει αυτό, θα εφαρμόσουμε γνώση των μαθηματικών και θα υπολογίσουμε αναλυτικά όλα τα ποσά.
Για παράδειγμα, ο αριθμός των συνδυασμών C(2, K), εάν τον «επεκτείνετε» με τη μορφή ενός τύπου K! / ((Κ-2)! * 2!), ανάγεται σε πολυώνυμο 2ου βαθμού. Και αφού το έχουμε κάτω από το πρόσημο του αθροίσματος, μπορούμε να εφαρμόσουμε τους τύπους για το άθροισμα των Ντων δυνάμεων των αριθμών στη φυσική σειρά (βλ. Wikipedia) και να πάρουμε ένα μόνο πολυώνυμο 3ου βαθμού. Το οποίο προφανώς έχει σταθερή χρονική πολυπλοκότητα. (Επιπλέον, το «λάθος» που ανέφερα στην αρχή του υπότιτλου δεν εκδηλώνεται με κανέναν τρόπο· ο τύπος παραμένει σωστός).
Επαναλαμβάνω, αυτό για μια σταθερή διάσταση του σετ βάσης. Ωστόσο, είμαι σίγουρος ότι με τη βοήθεια του μεταπρογραμματισμού μπορείτε να «διδάξετε» τον μεταγλωττιστή ώστε να κάνει αυτή τη δουλειά για εσάς. Επίλογος
Στον προσομοιωτή πόκερ μου (Texas Hold'em), ήθελα να υπολογίσω και να αποθηκεύσω τις πιθανότητες νίκης εκ των προτέρων για όλους τους πιθανούς συνδυασμούς των φύλλων χεριών μου (2 τεμάχια) και όλων των καρτών flop (3 φύλλα στο τραπέζι). Αυτό αντιστοιχεί στη διαίρεση το 52-σετ με 2, 3, 47 υποσύνολα.
Υπολογίστηκε και αποθηκεύτηκε.
Αλλά όταν ήρθε η ώρα να διαβάσω δεδομένα από ένα αρχείο για έναν συγκεκριμένο συνδυασμό, πραγματικά δεν ήθελα να υπολογίσω κάτι για μεγάλο χρονικό διάστημα ή να ψάξω σε ένα αρχείο gigabyte. Τώρα απλώς καθορίζω το offset στο αρχείο και διαβάζω απευθείας αυτό που χρειάζομαι.
Θα ήταν ενδιαφέρον να έχουμε ένα βιβλίο αναφοράς για συνδυαστικούς αλγόριθμους για όλα τα συνδυαστικά αντικείμενα, συμπεριλαμβανομένων των μεταθέσεων, συνδυασμών, τοποθετήσεων, υποσυνόλων, συνδυασμών με επαναλήψεις, τοποθετήσεων με επαναλήψεις. Σαφείς τύποι
Συνδέσεις
Δείτε τι είναι ο "Αριθμός συνδυασμών" σε άλλα λεξικά:
Βιβλία
Βασικός τύπος συνδυαστικής
Λύση: n 1 =6 (επειδή μπορείτε να πάρετε οποιονδήποτε αριθμό από το 1, 2, 3, 4, 5, 6 ως πρώτο ψηφίο), n 2 =7 (επειδή μπορείτε να πάρετε οποιοδήποτε αριθμό από το 0 ως δεύτερο ψηφίο , 1, 2 , 3, 4, 5, 6), n 3 =4 (καθώς οποιοσδήποτε αριθμός από 0, 2, 4, 6 μπορεί να ληφθεί ως τρίτο ψηφίο).
Άρα, N=n 1 *n 2 *n 3 =6*7*4=168.
Λύση.Για κάθε ψηφίο ενός τετραψήφιου αριθμού υπάρχουν πέντε πιθανότητες, που σημαίνει N=5*5*5*5=5 4 =625.Αριθμός τοποθετήσεων n στοιχείων κατά m
Λύση:επειδή Εάν υπάρχουν πέντε περιττά ψηφία, δηλαδή 1, 3, 5, 7, 9, τότε αυτή η εργασία καταλήγει στην επιλογή και την τοποθέτηση δύο από τα πέντε διαφορετικά ψηφία σε δύο διαφορετικές θέσεις, δηλ. οι αναγραφόμενοι αριθμοί θα είναι:
Αριθμός συνδυασμών n στοιχείων, m το καθένα
Μεταθέσεις n στοιχείων
Λύση:Σε αυτό το παράδειγμα, δεν μας ενδιαφέρει η σειρά των ονομάτων στη λίστα της επιτροπής. Εάν, ως αποτέλεσμα, οι ίδιοι άνθρωποι αποδειχθούν μέρος του, τότε στην έννοια για εμάς αυτή είναι η ίδια επιλογή. Επομένως, μπορούμε να χρησιμοποιήσουμε τον τύπο για να υπολογίσουμε τον αριθμό συνδυασμοίαπό 20 στοιχεία 5 το καθένα.
1. Πόσοι τριψήφιοι ζυγοί αριθμοί μπορούν να γίνουν από τα ψηφία 0, 1, 2, 3, 4, 5, 6, αν τα ψηφία μπορούν να επαναληφθούν;
Η έννοια και η προέλευση του επωνύμου Belyaev
Η τεχνική της Meshcheryakova "Αγγλικά για παιδιά"
Ήχος The Snow Queen The Snow Queen