Συνδυασμοί με Επανάθεση

Παράδειγμα: Με πόσους τρόπους μπορούμε να τοποθετήσουμε 4 ίδιες μπάλες σε 5 διαφορετικά κουτιά, υπό την προϋπόθεση ότι σε κάθε κουτί μπορούμε να βάλουμε όσες μπάλες θέλουμε;

Έστω η παρακάτω τοποθέτηση:

Αν αντιστοιχίσουμε τις μπάλες με μηδενικά και τα διαχωριστικά με μονάδες τότε η παραπάνω τοποθέτηση είναι ισοδύναμη με τη διάταξη 00110101

Αντίστοιχα η παρακάτω τοποθέτηση:

είναι ισοδύναμη με τη διάταξη 00111100.

Βλέπουμε ότι κάθε πιθανή τοποθέτηση (με επανάθεση) 4 μπαλών σε 5 κουτιά είναι ισοδύναμη με μία διάταξη 4 μηδενικών και 4 (δηλ. 5-1) μονάδων.

Θυμίζουμε ότι ο αριθμός των μεταθέσεων n αντικειμένων, όπου q1 από αυτά είναι ενός είδους και q2 από αυτά είναι ενός δεύτερου είδους είναι:

n! / q1!q2!

Συνεπώς ο συνολικός τρόπος των μεταθέσεων 4 μηδενικών και 4 μονάδων είναι 8!/(4!x4!)=40320/(24x24) =70

Γενικότερα ο αριθμός των τρόπων με τους οποίους μπορούμε να τοποθετήσουμε k ίδιες μπάλες σε n διαφορετικά αριθμημένα κουτιά υπό την προϋπόθεση ότι σε κάθε κουτί μπορούμε να βάλουμε όσες μπάλες θέλουμε μπορεί να αντιμετωπιστεί ως εξής:

Ένα σύμπλεγμα από n κουτιά μπορούμε να το θεωρήσουμε ως ένα μεγάλο κουτί που έχει n-1 διαχωριστικά. Το παραπάνω πρόβλημα είναι ισοδύναμο με το πρόβλημα με το πρόβλημα διάταξης n-1 ίδιων διαχωριστικών και k ίδιων μπαλών. Άρα ο αριθμός των τρόπων είναι:

Παράδειγμα: Ποιος είναι ο αριθμός των διαφορετικών αποτελεσμάτων όταν ρίχνουμε ένα ζάρι τρεις φορές και ποιος όταν ρίχνουμε τρία ζάρια μαζί;

Όταν ρίχνουμε ένα ζάρι τρεις φορές σε κάθε ρίψη έχουμε 6 πιθανά αποτελέσματα. Το αποτέλεσμα των τριών ρίψεων είναι μία διατεταγμένη τριάδα {x, y, z}, όπου τα x, y, και z μπορούν να πάρουν οποιαδήποτε από τις τιμές 1,2,3,4,5 και 6. Συνεπώς ο συνολικός τρόπος των πιθανών αποτελεσμάτων είναι 63=216.

Όταν ρίχνουμε τρία ζάρια μαζί δεν μας ενδιαφέρει τι έφερε το κάθε ζάρι (άλλωστε δεν μπορούμε να τα ξεχωρίσουμε). Μας ενδιαφέρει το αποτέλεσμα που έφεραν και τα τρία ζάρια μαζί. Το πρόβλημα αυτό είναι ένα πρόβλημα επιλογής (χωρίς διάταξη) 3 αντικειμένων από 6 με δυνατότητα επανάληψης. Άρα ο συνολικός αριθμός αποτελεσμάτων είναι:

 

Παράδειγμα: Με πόσους τρόπους μπορούν να καθίσουν 5 φοιτητές σε 12 καρέκλες;

Το παραπάνω πρόβλημα μπορεί να λυθεί με το τύπο P(12,7)=12!/7!= 95040.

Μία διαφορετική προσέγγιση στο πρόβλημα θα ήταν η παρακάτω:

Έστω ότι πρώτα διατάσσουμε τους 5 φοιτητές. Υπάρχουν 5! τρόποι να το κάνουμε αυτό. Στη συνέχεια τοποθετούμε τις άδειες καρέκλες αυθαίρετα είτε ανάμεσα σε δύο οποιουσδήποτε φοιτητές, είτε στα δύο άκρα. Το πρόβλημα της τοποθέτησης των 7 άδειων καρεκλών είναι ισοδύναμο με το πρόβλημα της τοποθέτησης 7 ίδιων μπαλών σε 6 κουτιά. Άρα ο συνολικός αριθμός των τρόπων με τους οποίους μπορούμε να τοποθετήσουμε τις καρέκλες είναι:

Εφόσον θα πρέπει να πραγματοποιηθούν και τα δύο παραπάνω πειράματα (τοποθέτηση φοιτητών και τοποθέτηση καρεκλών), εφαρμόζουμε το κανόνα του γινομένου και το τελικό αποτέλεσμα είναι:

 

Παράδειγμα: Έστω ότι έχουμε ένα μεγάλο πλήθος από νομίσματα των 5, 10, 20 και 50 λεπτών. Με πόσους τρόπους μπορούμε να επιλέξουμε 5 νομίσματα;

Το πρόβλημα απαιτεί την επιλογή (χωρίς διάταξη) 5 από 4 αντικείμενα (με επανάληψη). Συνεπώς θα εφαρμόσουμε το τύπο C(k+n-1,k) για k=5 και n=4: C(5+4-1,5)=C(8,5)=8!/(5!x3!)=56

Παράδειγμα:

α) Με πόσους τρόπους μπορούμε να τοποθετήσουμε k ίδιες μπάλες σε n κουτιά υπό τον όρο να μην μείνει άδειο κανένα κουτί;

Προφανώς το πλήθος των μπαλών θα είναι ίσο ή μεγαλύτερο από το πλήθος των κουτιών. Εφόσον δεν πρέπει να αφήσουμε κανένα κουτί άδειο, αρχικά τοποθετούμε μία μπάλα σε κάθε κουτί. Άρα μας μένουν k-n μπάλες να τις τοποθετήσουμε σε n κουτιά. Συνεπώς μπορούμε να εφαρμόσουμε το τύπο C(k+n-1, k) όπου στη θέση του k θα χρησιμοποιήσουμε το k-n. Έτσι ο τύπος γίνεται:

C(k-n+n-1, k-n)=C(k-1,k-n)

β) Με πόσους τρόπους μπορούμε να προγραμματίσουμε 15 ώρες μελέτης σε πέντε μέρες έτσι ώστε να μελετούμε τουλάχιστον μία ώρα την ημέρα;

Έχουμε να τοποθετήσουμε 15 ώρες (μπάλες) σε 5 μέρες (κουτιά) υπό την προϋπόθεση να μη μείνει κανένα κουτί άδειο. Σύμφωνα με τα παραπάνω η λύση προκύπτει από τον τύπο: C(15-1, 15-5)=C(14,10)=1001