Βασικοί τύποι απαρίθμησης

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

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

1. Προκαταρκτικά

Το βασικό ερώτημα στο οποίο θα αναζητήσουμε την απάντηση είναι το εξής:

Εάν έχουμε ένα σύνολο από \(n\) αντικείμενα, με πόσους τρόπους μπορούμε να επιλέξουμε υποσύνολα από \(k\) αντικείμενα, δεδομένων κάποιων συνθηκών που τίθενται στον τρόπο επιλογής;

Οι συνθήκες που τίθενται στην επιλογή των υποσυνόλων είναι οι εξής:

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

Είτε πρόκειται για μεταθέσεις είτε για περιορισμούς, μπορούμε να θέσουμε και τις εξής συνθήκες:

• Κάθε στοιχείο που επιλέγουμε χρησιμοποιείται μόνο μια φορά. Σε αυτήν την περίπτωση έχουμε επιλογή χωρίς επανάληψη.
• Κάθε στοιχείο που επιλέγουμε μπορεί να χρησιμοποιηθεί παραπάνω από μια φορά. Σε αυτήν την περίπτωση έχουμε επιλογή με επανάληψη.

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

Παράδειγμα
Να καταγραφούν όλοι οι δυνατοί τρόποι επιλογής 3 γραμμάτων από τα 4 γράμματα \(A,B,C,D\), όταν:

1. επιλέγουμε μεταθέσεις με επανάληψη,
2. επιλέγουμε μεταθέσεις χωρίς επανάληψη,
3. επιλέγουμε συνδυασμούς με επανάληψη,
4. επιλέγουμε συνδυασμούς χωρίς επανάληψη.

Επίλυση του 1
Όλες οι ζητούμενες μεταθέσεις με επανάληψη καταγράφονται παρακάτω: \begin{eqnarray*} AAA,\ &AAB,\ &AAC,\ &AAD,\ &ABA,\ &ABB,\ &ABC,\ &ABD\\ ACA,\ &ACB,\ &ACC,\ &ACD,\ &ADA,\ &ADB,\ &ADC,\ &ADD\\ BAA,\ &BAB,\ &BAC,\ &BAD,\ &BBA,\ &BBB,\ &BBC,\ &BBD\\ BCA,\ &BCB,\ &BCC,\ &BCD,\ &BDA,\ &BDB,\ &BDC,\ &BDD\\ CAA,\ &CAB,\ &CAC,\ &CAD,\ &CBA,\ &CBB,\ &CBC,\ &CBD\\ CCA,\ &CCB,\ &CCC,\ &CCD,\ &CDA,\ &CDB,\ &CDC,\ &CDD\\ DAA,\ &DAB,\ &DAC,\ &DAD,\ &DBA,\ &DBB,\ &DBC,\ &DBD\\ DCA,\ &DCB,\ &DCC,\ &DCD,\ &DDA,\ &DDB,\ &DDC,\ &DDD\\ \end{eqnarray*} Επίλυση του 2
Όλες οι ζητούμενες μεταθέσεις χωρίς επανάληψη καταγράφονται παρακάτω: \begin{eqnarray*} ABC, \ &ABD, \ &ACB, \ &ACD, \ &ADB, \ &ADC\\ BAC, \ &BAD, \ &BCA, \ &BCD, \ &BDA, \ &BDC\\ CAB, \ &CAD, \ &CBA, \ &CBD, \ &CDA, \ &CDB\\ DAB, \ &DAC, \ &DBA, \ &DBC, \ &DCA, \ &DCB \end{eqnarray*} Επίλυση του 3
Όλοι οι ζητούμενοι συνδυασμοί με επανάληψη καταγράφονται παρακάτω: \begin{eqnarray*} AAA,\ &AAB,\ &AAC,\ &AAD,\ &ABB\\ ABC,\ &ABD,\ &ACC,\ &ACD,\ &ADD\\ BBB,\ &BBC,\ &BBD,\ &BCC,\ &BCD\\ BDD,\ &CCC,\ &CCD,\ &CDD,\ &DDD \end{eqnarray*} Επίλυση του 4
Όλοι οι ζητούμενοι συνδυασμοί χωρίς επανάληψη καταγράφονται παρακάτω: \[ABC \ ABD, \ ACD, \ BCD\]

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

Πρόβλημα 1 (κανόνας του γινομένου)
Εάν έχουμε 4 πουκάμισα και 3 παντελόνια, με πόσους τρόπους μπορούμε να ντυθούμε;

Επίλυση
Για κάθε πουκάμισο έχουμε 3 επιλογές από παντελόνια. Άρα, συνολικά έχουμε \(4\cdot 3\) τρόπους.

Παρακάτω μπορούμε να διαπιστώσουμε σχηματικά το αποτέλεσμα.

\[\Pi\kappa_1\begin{cases} \Pi\nu_1 \\ \Pi\nu_2 \\ \Pi\nu_3 \\ \end{cases}\ \ \ \ \ \ \ \ \ \ \ \ \Pi\kappa_2\begin{cases} \Pi\nu_1 \\ \Pi\nu_2 \\ \Pi\nu_3 \\ \end{cases}\ \ \ \ \ \ \ \ \ \ \ \ \Pi\kappa_3\begin{cases} \Pi\nu_1 \\ \Pi\nu_2 \\ \Pi\nu_3 \\ \end{cases}\ \ \ \ \ \ \ \ \ \ \ \ \Pi\kappa_4\begin{cases} \Pi\nu_1 \\ \Pi\nu_2 \\ \Pi\nu_3 \\ \end{cases}\]

Γενικά, εάν έχουμε \(k\) σύνολα ανεξάρτητων επιλογών όπου τα σύνολα αυτά έχουν αντιστοίχους τρόπους επιλογών \(n_1 ,n_2 ,n_3\ldots, n_k ,\) τότε το πλήθος των τρόπων επιλογής ισούται με: \[n_1\cdot n_2\cdot n_3\cdots n_k.\]

Ως ένα παράδειγμα ακόμη, οι πινακίδες των αυτοκινήτων αποτελούνται από τρία γράμματα και τέσσερα ψηφία, όπου στο πρώτο ψηφίο δεν χρησιμοποιείται το 0. Όλες οι πινακίδες που μπορούν να υπάρξουν είναι: \[24\cdot 24\cdot 24 \cdot9 \cdot 10\cdot10 \cdot10=124.416.000.\]

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

Πρόβλημα 2 (πλήρεις μεταθέσεις)
Με πόσους τρόπους μπορούμε να τοποθετήσουμε στη σειρά 5 αντικείμενα;

Επίλυση
Το πρώτο στη σειρά αντικείμενο μπορεί να επιλεγεί με 5 τρόπους. Το δεύτερο αντικείμενο στη σειρά μπορεί να επιλεγεί με 4 τρόπους, διότι αφού το πρώτο αντικείμενο έχει ήδη επιλεγεί έχουν απομείνει 4 αντικείμενα που μπορούν να παίξουν τον ρόλο του δευτέρου αντικειμένου. Με το ίδιο σκεπτικό, το τρίτο στη σειρά αντικείμενο μπορεί να επιλεγεί με 3 τρόπους, το τέταρτο στη σειρά αντικείμενο μπορεί να επιλεγεί με 2 τρόπους και το πέμπτο στη σειρά αντικείμενο με έναν τρόπο. Δεδομένου ότι οι επιλογές αυτές είναι ανεξάρτητες, το πλήθος των δυνατών επιλογών των τοποθετήσεων ισούται τελικά με \(5\cdot 4\cdot 3\cdot 2\cdot 1\).

Γενικεύοντας το παραπάνω πρόβλημα, το πλήθος όλων των τρόπων τοποθέτησης στη σειρά \(n\) αντικειμένων (δηλαδή των μεταθέσεων) ισούται με \(1\cdot 2\cdot 3\cdots (n-1)\cdot n\). Τον αριθμό αυτόν τον συμβολίζουμε με \(n!\) (παραγοντικό του \(n\)). Δηλαδή, \[n!=1\cdot 2\cdot 3\cdots (n-1)\cdot n.\]

Ως ένα παράδειγμα ακόμη, όλες οι πιθανές διατάξεις των χαρτίων μιας τράπουλας όταν ανακατευτεί ισουται με \(52!\).

2. Μεταθέσεις με επανάληψη

Πρόβλημα 3
Ποιο είναι το πλήθος των επταψήφιων συνθηματικών κωδικών που αποτελούνται μόνο από πεζά λατινικά γράμματα και ψηφία;

Επίλυση
Έχουμε 26 πεζά λατινικά γράμματα και 10 ψηφία επομένως σχηματιζουμε τον κωδικό επιλέγοντας από 36 χαρακτήρες. Η επιλογή του πρώτου χαρακτήρα του κωδικού μπορεί να γίνει με 36 τρόπους. Η επιλογή του δεύτερου χαρακτήρα, η οποία είναι ανεξάρτητη της πρώτης, γίνεται επίσης με 36 τρόπους κ. ο. κ.. Από τον κανόνα του γινομένου, το συνολικό πλήθος των επιλγών είναι \[36\cdot 36\cdot 36\cdot 36\cdot 36\cdot 36\cdot 36=36^{7}.\]

Γενικεύοντας το παραπάνω πρόβλημα, το πλήθος των μεταθέσεων \(k\) αντικειμένων από \(n\) όταν επιτρέπονται επαναλήψεις, ισούται με \[n^k.\]

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

Πρόβλημα 4
Εάν ρίξουμε ένα νόμισμα 5 φορές πόσες είναι οι δυνατές πεντάδες εκβάσεων των ρίψεων;

Επίλυση
Για κάθε ρίψη έχουμε 2 δυνατά αποτελέσματα, κεφαλή ή γράμματα. Επειδή έχουμε 5 (ανεξάρτητες) ρίψεις, σύμφωνα με τον κανόνα του γινομένου έχουμε συνολικά \[2\cdot 2\cdot 2\cdot 2\cdot 2=2^5\] δυνατές πεντάδες εκβάσεων.

Ένα αφηρημένο πλαίσιο προβλήματων στο οποίο εφαρμόζεται ο παραπάνω τύπος στη γενικότητά του (όπου καλύπτονται και οι μεταθέσεις με επανάληψη) είναι το εξής: εάν έχουμε \(n\) κατηγορίες αντικειμένων απεριόριστου πλήθους, τότε το πλήθος των τρόπων με τους οποίους μπορούμε να τα τοποθετήσουμε σε \(k\) θέσεις ισούται με \(n^k\).

3. Μεταθέσεις χωρίς επανάληψη

Πρόβλημα 5
Με πόσους τρόπους μπορούμε να σχηματίσουμε λέξεις 3 γραμμάτων (ασχέτως νοήματος) επιλέγοντας από 5 γράμματα, χρησιμοποιώντας κάθε γράμμα μόνο μια φορά;

Επίλυση
Το πρώτο στη σειρά γράμμα μπορεί να επιλεγεί με 5 τρόπους. Το δεύτερο στη σειρά γράμμα μπορεί να επιλεγεί με 4 τρόπους, διότι αφού το πρώτο γράμμα έχει ήδη επιλεγεί έχουν απομείνει 4 γράμματα που μπορούν να παίξουν τον ρόλο του δευτέρου στη σειρά γράμματος. Με το ίδιο σκεπτικό, το τρίτο στη σειρά αντικείμενο μπορεί να επιλεγεί με 3 τρόπους. Δεδομένου ότι οι επιλογές αυτές είναι ανεξάρτητες, το πλήθος των δυνατών επιλογών των τοποθετήσεων ισούται με το γινόμενο του πλήθους των επιμέρους επιλογών, δηλαδη \(5\cdot 4\cdot 3\).

Θα διαμορφώσουμε λίγο καλύτερα το αποτέλεσμα αυτό:

\begin{eqnarray*} 5\cdot 4\cdot 3 = \frac{5\cdot 4\cdot 3\cdot 2\cdot 1}{2\cdot 1} =\frac{5!}{2!}=\frac{5!}{(5-3)!} \end{eqnarray*}

Γενικεύοντας το παραπάνω πρόβλημα, καταλήγουμε στο ότι το πλήθος των μεταθέσεων χωρίς επανάληψη \(n\) αντικειμένων ανά \(k\) ισούται με \[\frac{n!}{(n-k)!}.\]

Τον αριθμό αυτόν συμβολίζουμε με \(P(n,k)\) (ή και με \({}_{n}P_{k}\)).

Ως ένα παράδειγμα ακόμη, σε ένα τμήμα 19 μαθητών, τα πλήθος των δυνατών πενταμελών προεδρείων που μπορούν να εκλεγούν ισούται με \(P(19,5)\).

4. Συνδυασμοί χωρίς επανάληψη

Πρόβλημα 6
Με πόσους διαφορετικούς τρόπους μπορούμε να μοιράσουμε 5 αντίτυπα του ίδιου βιβλίου σε 8 ανθρώπους;

Επίλυση
Ουσιαστικά πρέπει να επιλέξουμε συνδυασμούς 5 ανθρώπων από τους 8, χωρίς επανάληψη. Ας συμβολίσουμε προσωρινά με \(Α\) το πλήθος των δυνατών τρόπων επιλογής.

Αρχικά, για κάθε επιλογή πεντάδας ανθρώπων, μπορούμε να τους τοποθετήσουμε στη σειρά με \(5!\) τρόπους. Άρα το πλήθος των μεταθέσεων των πεντάδων ισούται, σύμφωνα με τον κανόνα γινομένου, με \(5!Α\).

Από την άλλη πλευρά, το πλήθος των μεταθέσεων των πεντάδων ισούται, όπως έχουμε ήδη συναντήσει, με \(P(8,5)=\frac{8!}{3!}=\frac{8!}{(8-5)!}\).

Συγκρίνοντας τις δύο εκφράσεις, καταλήγουμε εύκολα ότι

\[A=\frac{8!}{3!}=\frac{8!}{5!(8-5)!}.\] (Ας σημειώσουμε ότι εάν είχαμε διαφορετικά βιβλία, η απάντηση θα ήταν \(P(8,5)\).)

Ο αριθμός που αναζητήσαμε στο προηγούμενο πρόβλημα συμβολίζεται με \(\binom{8}{5}\). Γενικεύοντας τα παραπάνω, συμβολίζουμε με \(\binom{n}{k}\) το πλήθος των συνδυασμών \(n\) αντικειμένων ανά \(k\) ομάδες, χωρίς επαναλήψεις. Ο αριθμός αυτός ονομάζεται και διωνυμικός συντελεστής, για λόγους που θα εξεταστούν σε μελλοντική ανάρτηση. Συμβολίζεται επίσης και με \(C(n,k)\). Σύμφωνα με τα παραπάνω, υπολογίζεται από τον τύπο: \[\binom{n}{k}=\frac{n!}{k!(n-k)!}.\]

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

Παράδειγμα
Θα καταγράψουμε έναν προς έναν όλους τους συνδυασμούς 3 γραμμάτων από τα 5 γράμματα \(A,B,C,D,E\). Το αναμενόμενο πλήθος τους είναι ίσο με: \[\binom{5}{3}=\frac{5!}{3!(5-3)!}=\frac{5!}{3!2!}=\frac{5\cdot 4\cdot 3\cdot 2\cdot 1}{(3\cdot 2\cdot 1)\cdot (2\cdot 1)}=\frac{5\cdot 4}{2}=10.\] Οι συνδυασμοί καταγράφονται παρακάτω: \begin{eqnarray*} ABC,\ & ABD,\ & ABE,\ & ACD,\ & ACE,\ & ADE,\\ BCD,\ & BCE,\ & BDE,\\ CDE,\ \end{eqnarray*}

Θα καταγράψουμε τώρα όλες τις δυνατές μεταθέσεις 3 γραμμάτων από τα \(A,B,C,D,E\). Η καταγραφή θα γίνει με τον εξής τρόπο: Για κάθε συνδυασμό που έχουμε βρεί, θα καταγράψουμε και όλες τις δυνατές τοποθετήσεις στη σειρά. Αυτό καθιστά τη λίστα πλήρη, και είναι η βασική ιδέα που κρύβεται πίσω από τον τύπο υπολογισμού του διωνυμικού συντελεστή.

Το αναμενόμενο πλήθος των μεταθέσεων είναι:

\[P(5,3)=\frac{5!}{(5-3)!}=\frac{5!}{3!}=\frac{5\cdot 4\cdot 3\cdot 2\cdot 1}{2\cdot 1}=5\cdot 4\cdot 3=60.\] Η πλήρης λίστα δίνεται παρακάτω: \begin{eqnarray*} ABC,& ACB,&BAC,&BCA,&CAB,&CBA\\ ABD,&ADB,&BAD,&BDA,&DAB,&DBA\\ ABE,&AEB,&BAE,&BEA,&EAB,&EBA\\ ACD,&ADC,&CAD,&CDA,&DAC,&DCA\\ ACE,&AEC,&CAE,&CEA,&EAC,&ECA\\ ADE,& AED,&DAE,&DEA,&EAD,&EDA\\ BCD,&BDC,&CBD,&CDB,&DBC,&DCB\\ BCE,&BEC,&CBE,&CEB,&EBC,&ECB\\ BDE,& BED,&DBE,&DEB,&EBD,&EDB\\ CDE,& CED,& DCE,& DEC,& ECD,& EDC \end{eqnarray*} Η πρώτη στήλη αποτελείται από τους συνδυασμούς που κατεγράφησαν στην πρώτη λίστα. Κάθε γραμμή αποτελείται από τις μεταθέσεις του πρώτου στοιχείου της.

Το επόμενο πρόβλημα σχετίζεται με τα προηγούμενα.

Πρόβλημα 7
Έχουμε 4 ίδια βιβλία επιστημονικής φαντασίας, 3 ίδια βιβλία ποίησης και 2 ίδια βιβλία ιστορίας. Με πόσους τρόπους μπορούμε να τα μοιράσουμε σε 9 ανθρώπους;

Επίλυση
Αρχικά μοιράζουμε τα 4 βιβλία επιστημονικής φαντασίας, επιλέγοντας έναν συνδυασμό 4 ανθρώπων. Αυτό γίνεται με \(\binom{9}{4}\) τρόπους. Στους εναπομείναντες 5 ανθρώπους μοιράζουμε τα 3 βιβλία ποίησης. Αυτό γίνεται με \(\binom{5}{3}\). Τέλος, στους 2 ανθρώπους που απομένουν μοιράζουμε τα 2 βιβλία ιστορίας με έναν τρόπο, προφανώς. Από τον κανόνα του γινομένου, το πλήθος των δυνατών τρόπων διαμοιρασμού των βιβλίων ισούται με \(\binom{9}{4}\cdot\binom{5}{3}\).

Ας δούμε με τι ισούται αυτή η παράσταση:

\[\binom{9}{4}\cdot\binom{5}{3}=\frac{9!}{4!(9-4)!}\cdot\frac{5!}{3!(5-3)!}=\frac{9!}{4!5!}\cdot\frac{5!}{3!2!}=\frac{9!}{4!3!2!}.\]

Ο παραπάνω αριθμός συμβολίζεται με \(\binom{9}{4\ 3\ 2}\). Γενικότερα, το πλήθος των τρόπων διαμοιρασμού \(n\) αντικειμένων σε \(r\) κατηγορίες μεγέθους \(k_1,k_2,\ldots,k_r\) με \(k_1+k_2+\ldots+k_r=n\) ισούται με \[\frac{n!}{k_{1}!k_{2}!\ldots k_{r}!}\] και συμβολίζεται με \(\binom{n}{k_{1}\ \ k_{2}\ \cdots\ k_{r}}\). Ονομάζεται πολυωνυμικός συντελεστής για λόγους που θα αναλύσουμε σε μελλοντική ανάρτηση.

5. Συνδυασμοί με επανάληψη

Το επόμενο πρόβλημα παρουσιάζει μεγαλύτερη δυσκολία.

Πρόβλημα 8
Να βρεθεί το πλήθος των συνδυασμών των τριάδων που μπορούμε να σχηματίσουμε από τα γράμματα \(A,B,C,D,E\), όταν επιτρέπονται επαναλήψεις.

Επίλυση
Θέτουμε \(n=5\) και \(k=3\). Για την κατανόηση και επίλυση του προβλήματος, θα παραθέσουμε αρχικά όλους τους ζητούμενους συνδυασμούς. \begin{eqnarray*} AAA\ \ &AAB\ \ &AAC\ \ &AAD\ \ &AAE\ \ &ABB\ \ &ABC\\ ABD\ \ &ABE\ \ &ACC\ \ &ACD\ \ &ACE\ \ &ADD\ \ &ADE\\ AEE\ \ &BBB\ \ &BBC\ \ &BBD\ \ &BBE\ \ &BCC\ \ &BCD\\ BCE\ \ &BDD\ \ &BDE\ \ &BEE\ \ &CCC\ \ &CCD\ \ &CCE\\ CDD\ \ &CDE\ \ &CEE\ \ &DDD\ \ &DDE\ \ &DEE\ \ &EEE \end{eqnarray*} Το πλήθος των ζητούμενων συνδυασμών είναι 35.

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

Θεωρούμε την παρακάτω σχηματική διάταξη \[|\ \ \ \ |\ \ \ \ |\ \ \ \ |\] που αποτελείται από \(n-1=4\) καθέτους. Οι κάθετοι αυτές δημιουργούν \(n=5\) κενά: ένα αριστερά της πρώτης καθέτου, ένα δεξιά της τελευταίας καθέτου και τρία ενδιάμεσα. Κάθε κενό (από αριστερά προς δεξιά) αντιστοιχεί στα αρχικά αντικείμενα που διαθέτουμε, στην περίπτωσή μας τα γράμματα \(Α,Β,C,D,E\).

Θεωρούμε επίσης ότι έχουμε και \(k=3\) σύμβολα, για παράδειγμα άστρα (\(\star\)), τα οποία τοποθετούμε σε κάποια από τα πέντε κενά που σχηματίζονται από τις καθέτους. Σημειώνουμε ότι μπορούμε να τοποθετήσουμε περισσότερα από ένα άστρα σε κάποιο κενό. Παραδείγματος χάρη, μια τέτοια διάταξη είναι η

\[|\star |\ \ \ \ |\star\star|\]

Η διάταξη αυτή μπορεί να ερμηνευτεί ως κάποιος από τους συνδυασμούς που αναζητούμε και συγκεκριμένα ο συνδυασμός \(ΒDD\). Αυτό γίνεται ως εξής: κάθε κενό αντιστοιχεί όπως προείπαμε σε ένα γράμμα και το πλήθος των άστρων σε συγκεκριμένο κενό δηλώνει πόσες φορές χρησιμοποιούμε το αντίστοιχο γράμμα.

Ας δούμε μερικά ακόμη παραδείγματα αντιστοιχιών:

Συνδυασμός \(ABC\) \(BDE\) \(CCD\) \(EEE\)

Διάταξη \(\star|\star |\star |\ \ \ \ |\) \(|\star|\ \ \ \ |\star|\star\) \(|\ \ \ \ |\star\star|\star|\) \(|\ \ \ \ |\ \ \ \ |\ \ \ \ |\star\star\star\)

Με αυτήν την τεχνική, το αρχικό μας πρόβλημα έχει λοιπόν μετασχηματιστεί στο εξής ισοδύναμο πρόβλημα: πόσες διατάξεις καθέτων και άστρων όπως οι παραπάνω υπάρχουν;

Εκ πρώτης όψεως, το νέο πρόβλημα δείχνει πιο δύσκολο. Για να το επιλύσουμε ακολουθούμε την εξής μέθοδο: οι κάθετοι μαζί με τα άστρα είναι στο σύνολο \(7\) αντικείμενα (το \(7\) προκύπτει από το άθροισμα \(4+3=(n-1)+k=n+k-1\)). Από τα αντικείμενα αυτά πρέπει να αποφασίσουμε ποια είναι τα 3 (δηλαδή \(k\)) άστρα. Όλοι οι δυνατοί τρόποι με τους οποίους μπορούμε να επιλέξουμε 3 από τα 7 αντικείμενα δίνονται από τον διωνυμικό συντελεστή \(\binom{7}{3}\). Αυτή ακριβώς είναι η απάντηση στο πρόβλημα. Επαληθεύοντας:

\[\binom{7}{3}=\frac{7!}{3!(7-3)!}=\frac{7!}{3!4!}=\frac{7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{(3\cdot 2\cdot 1)\cdot(4\cdot 3\cdot 2\cdot 1)}=\frac{7\cdot 6\cdot 5}{3\cdot 2}=35,\] το οποίο αναμέναμε.

Γενικεύοντας το παραπάνω πρόβλημα, με το σύμβολο \(\left(\binom{n}{k}\right)\) δηλώνεται το πλήθος των συνδυασμών \(n\) αντικειμένων ανά \(k\), με την υπόθεση ότι επιτρέπονται επαναλήψεις επιλογών. Ο τρόπος υπολογισμού του πλήθους αυτού δίνεται από τον τύπο

\[\left(\binom{n}{k}\right)=\binom{n+k-1}{k}.\]

Ως ένα παράδειγμα ακόμη, εάν έχουμε 7 γεύσεις παγωτού και θέλουμε ένα χωνάκι με 3 μπάλες, μπορούμε να επιλέξουμε με \(\left(\binom{7}{3}\right)\) τρόπους.

6. Επίλογος

Παρακάτω συνοψίζονται οι τέσσερις βασικοί τύποι που συναντήσαμε.

	μεταθέσεις	συνδυασμοί
χωρίς επανάληψη	\(P(n,k)\)	\(\binom{n}{k}\)
με επανάληψη	\(n^k\)	\(\left(\binom{n}{k}\right)\)

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