Υπολογιστής Διατάξεων και Συνδυασμών

Χρησιμοποιήστε διατάξεις όταν η σειρά ή η διευθέτηση των επιλεγμένων στοιχείων έχει σημασία:

• ανάθεση καταταγμένων θέσεων (1η, 2η, 3η θέση)
• τακτοποίηση βιβλίων σε ράφι
• δημιουργία κωδικών πρόσβασης ή PIN
• διευθέτηση καθισμάτων
• αριθμοί τηλεφώνου

Χρησιμοποιήστε συνδυασμούς όταν απλώς επιλέγετε ένα υποσύνολο και η σειρά είναι αδιάφορη:

• επιλογή μελών ομάδας
• επιλογή αριθμών λαχείου
• επιλογή πιάτων από μενού
• συγκρότηση επιτροπών

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

Οι αριθμοί του λαχείου το αποδεικνύουν περίφημα — η κλήρωση του Mega Millions επιλέγει 5 αριθμούς από το 70 συν 1 από το 25: C(70,5) × 25 = 302.575.350 πιθανά δελτία. Αν η σειρά είχε σημασία, θα υπήρχαν P(70,5) × 25 = 36.309.042.000 δυνατότητες — 120 φορές περισσότερες.

Βασικές διατάξεις: P(n,r) = n!/(n-r)!. P(10,3) = 10!/7! = 10×9×8 = 720.

Βασικοί συνδυασμοί: C(n,r) = n!/[r!(n-r)!]. C(10,3) = 10!/(3!×7!) = 720/6 = 120.

Με επιτρεπόμενη επανάληψη: διατάξεις = n^r (π.χ. ένα 4ψήφιο PIN από ψηφία 0-9 έχει 10⁴ = 10.000 δυνατότητες).

Συνδυασμοί με επανάληψη: C(n+r-1, r) — η επιλογή 3 μπάλες από 5 γεύσεις παγωτού με επιτρεπόμενες επαναλήψεις δίνει C(7,3) = 35.

Για μεγάλες τιμές, χρησιμοποιήστε τον πολλαπλασιαστικό τύπο για να αποφύγετε τον υπολογισμό τεράστιων παραγοντικών: C(52,5) = (52×51×50×49×48)/(5×4×3×2×1) = 2.598.960 — ο αριθμός των πιθανών χεριών πόκερ 5 καρτών.

Ασφάλεια κωδικών πρόσβασης: ένας κωδικός πρόσβασης 8 χαρακτήρων που χρησιμοποιεί κεφαλαία, πεζά, ψηφία και 10 σύμβολα (72 χαρακτήρες) έχει 72⁸ = 722 τρισεκατομμύρια διατάξεις με επανάληψη — απαιτώντας για μια επίθεση εξαντλητικής δοκιμής (brute-force) περίπου 22.800 χρόνια με ρυθμό 1 δισεκατομμυρίου δοκιμών ανά δευτερόλεπτο. Η προσθήκη μόλις 2 επιπλέον χαρακτήρων (κωδικός 10 χαρακτήρων) το αυξάνει σε 3,7 τετράκις εκατομμύρια — 5.140 φορές πιο δύσκολο να παραβιαστεί.

• Στη γενετική, ο αριθμός των τρόπων επιλογής 23 ζευγών χρωμοσωμάτων από τα 46 χρωμοσώματα ενός γονέα είναι C(46,23) ≈ 8,2 δισεκατομμύρια, εξηγώντας τη γενετική ποικιλομορφία.
• Στον έλεγχο ποιότητας, η επιλογή 5 στοιχείων από μια παρτίδα 100 για δοκιμή περιλαμβάνει C(100,5) = 75.287.520 πιθανά δείγματα.
• Στα διαγράμματα τουρνουά, ο αριθμός των πιθανών διαγραμμάτων NCAA March Madness είναι 2⁶³ ≈ 9,2 εξάκις εκατομμύρια — γι' αυτό και κανείς δεν έχει προβλέψει ποτέ με ακρίβεια ένα τέλειο διάγραμμα.

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

Αν επιλέξετε τα γράμματα A, B και C, οι διευθετήσεις ABC και CAB είναι δύο διαφορετικές διατάξεις αλλά ο ίδιος συνδυασμός, επειδή ένας συνδυασμός ενδιαφέρεται μόνο για το ποια στοιχεία επιλέχθηκαν και όχι για τη σειρά τους. Όπως εξηγεί η Encyclopaedia Britannica, η συνδυαστική είναι ο κλάδος των μαθηματικών που είναι αφοσιωμένος στην καταμέτρηση τέτοιων διευθετήσεων και επιλογών.

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

Ο τύπος των διατάξεων είναι nPr = n! / (n − r)! και ο τύπος των συνδυασμών είναι nCr = n! / [r! × (n − r)!], όπου n! (n παραγοντικό) είναι το γινόμενο κάθε ακέραιου από το 1 έως το n.

Για να βρείτε το P(10,3), υπολογίστε το 10! / 7!, το οποίο απλοποιείται σε 10 × 9 × 8 = 720. Για να βρείτε το C(10,3), διαιρέστε αυτό το αποτέλεσμα με το 3! = 6, δίνοντας 120. Το ίδιο το παραγοντικό αυξάνεται ταχύτατα: 5! = 120 και 10! = 3.628.800.

Το Wolfram MathWorld ορίζει τον διωνυμικό συντελεστή C(n,r) ακριβώς με αυτόν τον τρόπο. Επειδή το nCr διαιρεί τις r! διατάξεις που οι διατάξεις μετρούν ξεχωριστά, το nCr είναι πάντα μικρότερο ή ίσο με το nPr για τα ίδια n και r.

Για να υπολογίσετε το C(52,5) — τον αριθμό των χεριών πόκερ πέντε καρτών — ξεκινήστε με την πολλαπλασιαστική μορφή αντί για τα πλήρη παραγοντικά, ώστε να κρατήσετε τους αριθμούς διαχειρίσιμους. Γράψτε τον αριθμητή ως τους πέντε μεγαλύτερους φθίνοντες παράγοντες, 52 × 51 × 50 × 49 × 48, και τον παρονομαστή ως 5! = 120. Ο αριθμητής ισούται με 311.875.200· η διαίρεση με το 120 δίνει ακριβώς 2.598.960 πιθανά χέρια.

Για έναν μικρότερο έλεγχο, C(5,2) = (5 × 4) / (2 × 1) = 10, και C(8,3) = (8 × 7 × 6) / (3 × 2 × 1) = 56.

Το Khan Academy διδάσκει αυτή τη συντόμευση απλοποίησης επειδή αποφεύγει τον απευθείας υπολογισμό τεράστιων παραγοντικών. Η Digital Library of Mathematical Functions (DLMF) του NIST δίνει τον ίδιο ορισμό διωνυμικού συντελεστή που χρησιμοποιείται εδώ.

Όταν επιτρέπεται η επανάληψη, οι τύποι αλλάζουν επειδή τα στοιχεία μπορούν να επαναχρησιμοποιηθούν.

• Για διατάξεις με επανάληψη, το πλήθος είναι απλά n^r: ένα 4ψήφιο PIN που σχηματίζεται από τα ψηφία 0–9 έχει 10^4 = 10.000 δυνατότητες, καθώς κάθε μία από τις τέσσερις θέσεις έχει ανεξάρτητα δέκα επιλογές.
• Για συνδυασμούς με επανάληψη, το πλήθος είναι C(n + r − 1, r). Η επιλογή 3 μπάλες από 5 γεύσεις παγωτού όταν επιτρέπονται οι επαναλήψεις δίνει C(5 + 3 − 1, 3) = C(7,3) = 35.

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

Οι διατάξεις και οι συνδυασμοί εμφανίζονται οπουδήποτε μετράτε διευθετήσεις ή επιλογές.

• Τα λαχεία χρησιμοποιούν συνδυασμούς: η επιλογή 6 αριθμών από 49 δίνει C(49,6) = 13.983.816 πιθανά δελτία, γεγονός που καθορίζει τις πιθανότητες του τζακ ποτ.
• Τα παιχνίδια με τράπουλα βασίζονται επίσης σε αυτούς — υπάρχουν 2.598.960 πιθανά χέρια πόκερ πέντε καρτών από μια τράπουλα 52 καρτών.
• Η κυβερνοασφάλεια χρησιμοποιεί διατάξεις με επανάληψη για να μετρήσει πόσοι κωδικοί πρόσβασης ή κλειδιά είναι πιθανά, επηρεάζοντας άμεσα την αντοχή σε επιθέσεις εξαντλητικής δοκιμής.
• Η στατιστική και οι πιθανότητες χρησιμοποιούν τον διωνυμικό συντελεστή C(n,r) εντός της διωνυμικής κατανομής και του τριγώνου του Πασκάλ.
• Ο προγραμματισμός εργασιών, η κατάταξη τουρνουά, η ανάλυση αλληλουχιών DNA και η δειγματοληψία ελέγχου ποιότητας βασίζονται όλα σε αυτούς τους υπολογισμούς.

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

Κάθε καταχώριση στο Τρίγωνο του Πασκάλ είναι ένας διωνυμικός συντελεστής nCr, επομένως το αποτέλεσμα των συνδυασμών του υπολογιστή διαβάζει κυριολεκτικά μια τιμή από αυτό το τρίγωνο. Η γραμμή 6 του τριγώνου του Πασκάλ είναι 1, 6, 15, 20, 15, 6, 1 — ακριβώς από C(6,0) έως C(6,6).

Αυτοί οι αριθμοί είναι οι συντελεστές στο διωνυμικό ανάπτυγμα (a + b)^n, γι' αυτό το C(n,r) ονομάζεται διωνυμικός συντελεστής.

Δύο ταυτότητες προκύπτουν άμεσα:

• ο κανόνας συμμετρίας C(n,r) = C(n, n−r), οπότε C(15,4) = C(15,11) = 1.365
• ο κανόνας αθροίσματος ότι όλοι οι συντελεστές στη γραμμή n αθροίζονται σε 2^n, αφού C(4,0)+C(4,1)+C(4,2)+C(4,3)+C(4,4) = 1+4+6+4+1 = 16 = 2^4

Το Wolfram MathWorld και η OEIS καταγράφουν το τρίγωνο του Πασκάλ ως ακολουθία A007318.

• Το πιο συχνό σφάλμα είναι η επιλογή λάθος εργαλείου: η χρήση διάταξης όταν η σειρά δεν έχει σημασία διογκώνει την απάντηση κατά έναν παράγοντα r!, επειδή το nPr μετρά κάθε μη διατεταγμένη ομάδα r! ξεχωριστές φορές. Για παράδειγμα, η αντιμετώπιση μιας 3μελούς επιτροπής από 10 άτομα ως διατεταγμένης δίνει P(10,3) = 720 αντί για το σωστό C(10,3) = 120.
• Ένα δεύτερο σφάλμα είναι ότι ξεχνάτε αν επιτρέπεται η επανάληψη — ένα PIN επαναχρησιμοποιεί ψηφία (n^r), αλλά ένα λαχείο όχι.
• Ένα τρίτο είναι η σύγχυση μεταξύ n και r, καθώς οι τύποι δεν είναι συμμετρικοί ως προς αυτούς.
• Τέλος, αποφύγετε τον πλήρη υπολογισμό τεράστιων παραγοντικών και στη συνέχεια τη διαίρεση· χρησιμοποιήστε τη μέθοδο απλοποίησης ώστε οι ενδιάμεσες τιμές να παραμένουν μικρές και να αποφύγετε σφάλματα υπερχείλισης ή στρογγυλοποίησης.

Για κάθε σταθερό n και r, οι διατάξεις είναι πάντα ίσες ή μεγαλύτερες από τους συνδυασμούς επειδή nPr = nCr × r!, με τον πρόσθετο παράγοντα να λαμβάνει υπόψη κάθε διάταξη των επιλεγμένων στοιχείων.\n\nΌταν r = 1 είναι ίσες, καθώς ένα μόνο στοιχείο έχει μόνο μία διάταξη: P(20,1) = C(20,1) = 20. Καθώς το r αυξάνεται, το χάσμα διευρύνεται γρήγορα. Με n = 10 και r = 3, P(10,3) = 720 ενώ C(10,3) = 120 — το πλήθος των διατάξεων είναι ακριβώς 3! = 6 φορές μεγαλύτερο. Επιλέγοντας όλα τα στοιχεία, P(5,5) = 5! = 120 ενώ C(5,5) = 1.\n\nΓι' αυτό τα αποτελέσματα με σειρά κατάταξης αυξάνονται πολύ ταχύτερα από τις επιλογές χωρίς σειρά, και γι' αυτό τα λαχεία (συνδυασμοί) έχουν πολύ καλύτερες πιθανότητες από ό,τι αν μετρούσε η σειρά κλήρωσης. Η κατανόηση αυτής της αναλογίας σάς βοηθά να επαληθεύετε κάθε αποτέλεσμα που επιστρέφει ο υπολογιστής.