Συνδυασμοί χωρίς Επανάθεση

Ας επιστρέψουμε στο πρόβλημα στο οποίο τοποθετούμε k μπάλες σε n διαφορετικά αριθμημένα κουτιά. Αυτή τη φορά θα υποθέσουμε ότι όλες οι μπάλες είναι ίδιες. Όπως γνωρίζουμε οι διαφορετικές διατάξεις για k διαφορετικές μπάλες είναι:

Υπάρχουν k! μεταθέσεις των k αντικειμένων στις k θέσεις. Αφού όμως τα k αντικείμενα είναι ίδια στην ουσία κάθε k! διατάξεις αποτελούν μία διάταξη. Συνεπώς τον παραπάνω αριθμό θα πρέπει να τον διαιρέσουμε με k! Άρα υπάρχουν

τρόποι για να τοποθετήσουμε k ίδιες μπάλες σε n διαφορετικά αριθμημένα κουτιά. Η ποσότητα αυτή συμβολίζεται και C(n, k).

Παράδειγμα : Έστω ότι θέλουμε να έχουμε ψάρια για φαγητό τις τρεις από τις επτά ημέρες της εβδομάδας. Με πόσους τρόπους μπορούμε να προγραμματίσουμε το εβδομαδιαίο μενού;

Υπάρχουν C(7, 3)=7!/(3!4!) =35 τρόποι για να τοποθετήσουμε 3 ίδια φαγητά (ίδιες μπάλες) σε 7 διαφορετικές μέρες (αριθμημένα κουτιά).

Ένα ισοδύναμο πρόβλημα με το να τοποθετήσουμε k ίδιες μπάλες σε n διαφορετικά αριθμημένα κουτιά είναι αυτό της επιλογής (χωρίς διάταξη) k από n διαφορετικά αντικείμενα. Μπορούμε να θεωρήσουμε τα n διαφορετικά αντικείμενα ως κουτιά και να σημειώσουμε τα k επιλεγμένα αντικείμενα με το ίδιο σημάδι (να τοποθετήσουμε την ίδια μπάλα).

Άρα ο αριθμός των τρόπων για να επιλέξουμε k από n διαφορετικά αντικείμενα είναι επίσης C(n, k). Με άλλα λόγια σε ένα σύνολο με πληθικό αριθμό n υπάρχουν C(n, k) υποσύνολα μεγέθους k.

Παράδειγμα: Με πόσους τρόπους μπορούμε να επιλέξουμε μία 5μελή επιτροπή από 11 άτομα;

Μπορούμε να θεωρήσουμε τα 11 άτομα ως κουτιά και να σημειώσουμε τα 5 επιλεγμένα άτομα με το ίδιο σημάδι (να τοποθετήσουμε την ίδια μπάλα).

Ένας από τους πιθανούς συνδυασμούς είναι ο παρακάτω:

Σύμφωνα με τα παραπάνω υπάρχουν C(n, k) τρόποι για να επιλέγουμε k από n αντικείμενα, δηλαδή υπάρχουν C(11,5)=462 τρόποι να επιλέξουμε μία πενταμελή επιτροπή από 11 άτομα.

 

Παράδειγμα: Σε μία τάξη 100 φοιτητών υπάρχουν 40 αγόρια.

α) Με πόσους τρόπους μπορεί να σχηματιστεί μία 10μελής επιτροπή;

Αυτό είναι ένα πρόβλημα επιλογής 10 από 100 αντικείμενα. Συνεπώς η λύση είναι C(100,10)=100!/(10!90!)= 17.310.309.456.440

β) Επαναλάβατε το (α) αν πρέπει να υπάρχουν ίσοι αριθμοί αγοριών και κοριτσιών στην επιτροπή.

Πρέπει να επιλέξουμε 5 αγόρια από τα 40 και 5 κορίτσια από τα 60. Υπάρχουν C(40,5) τρόποι να επιλέξουμε τα αγόρια και C(60,5) τρόποι να επιλέξουμε τα κορίτσια. Εφόσον θα πραγματοποιήσουμε και τα δύο πειράματα, εφαρμόζουμε τον κανόνα του γινομένου. Άρα ο συνολικός αριθμός των τρόπων για να σχηματίσουμε την επιτροπή είναι: C(40,5)xC(60,5)=40!/(5!35!)x60!/(5!55!)= 658.008x 5.461.512= 3.593.718.588.096

γ) Επαναλάβατε το (α) αν η επιτροπή πρέπει να αποτελείται είτε από 6 αγόρια και 4 κορίτσια, είτε από 4 αγόρια και 6 κορίτσια.

Ας ονομάσουμε ως πρώτο πείραμα το σχηματισμό της επιτροπής από 6 αγόρια και 4 κορίτσια. Πρέπει να επιλέξουμε 6 αγόρια από τα 40 και 4 κορίτσια από τα 60. Άρα ο συνολικός αριθμός των τρόπων για να σχηματίσουμε την επιτροπή είναι: C(40,6)xC(60,4)=40!/(6!34!)x60!/(4!56!)= 3.838.380x487.635= 1.871.728.431.300

Ας ονομάσουμε ως δεύτερο πείραμα το σχηματισμό της επιτροπής από 4 αγόρια και 6 κορίτσια. Πρέπει να επιλέξουμε 4 αγόρια από τα 40 και 6 κορίτσια από τα 60. Άρα ο συνολικός αριθμός των τρόπων για να σχηματίσουμε την επιτροπή είναι: C(40,4)xC(60,6)=40!/(4!36!)x60!/(6!54!)= 91.390x 50.063.860= 4.575.336.165.400

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

1.871.728.431.300+4.575.336.165.400=6.447.064.596.700

 

Παράδειγμα: Έστω ότι σε ένα διαγώνισμα πρέπει να απαντήσουμε σε 8 από τις 10 ερωτήσεις.

α) Πόσες επιλογές έχουμε;

Πρέπει να επιλέξουμε 8 από 10 αντικείμενα (χωρίς διάταξη, χωρίς επανάληψη). Ο συνολικός αριθμός των τρόπων είναι:

C(10, 8)=10!/(8!2!)= 3.628.800/(40320x2)=45

β) Πόσες επιλογές έχουμε αν πρέπει να απαντήσουμε υποχρεωτικά στις τρεις πρώτες ερωτήσεις;

Για να απαντήσουμε σε 8 ερωτήσεις συνολικά, πρέπει να απαντήσουμε τις τρεις πρώτες ερωτήσεις και άλλες 5 από τις υπόλοιπες 7. Δηλαδή, έχουμε να επιλέξουμε 5 από 7 αντικείμενα. Άρα C(7, 5)=7!/(5!2!)= 5.040/(120x2)=21.

γ) Πόσες επιλογές έχουμε αν πρέπει να απαντήσουμε τουλάχιστον στις 4 από τις 5 πρώτες ερωτήσεις;

Υπάρχουν δύο τρόποι να απαντήσουμε: Ο πρώτος τρόπος είναι να απαντήσουμε ακριβώς 4 ερωτήσεις από τις 5 πρώτες και 4 από τις 5 τελευταίες ερωτήσεις. Ο δεύτερος τρόπος είναι να απαντήσουμε και τις 5 πρώτες ερωτήσεις και άλλες 3 από τις 5 τελευταίες.

Με το πρώτο τρόπο έχουμε C(5,4)xC(5,4) επιλογές. Με το δεύτερο τρόπο έχουμε C(5,5)xC(5,3) επιλογές. Το πείραμα μπορεί να υλοποιηθεί μόνο με έναν από τους δύο παραπάνω τρόπους. Συνεπώς εφαρμόζουμε το κανόνα του αθροίσματος:

C(5,4)xC(5,4)+C(5,5)xC(5,3)=5x5+1x10=35

 

Παράδειγμα: Έστω ότι από 12 φοιτητές πρέπει να επιλεγεί μία αντιπροσωπεία 4 ατόμων.

α) Με πόσους τρόπους μπορεί να επιλεγεί η αντιπροσωπεία;

Έχουμε να επιλέξουμε 4 από 12 αντικείμενα. Άρα υπάρχουν C(12,4)=12!/(4!x8!)= 479.001.600/(40.320x24)=495

β) Επαναλάβετε το (α) αν υπάρχουν δύο φοιτητές που αρνούνται να είναι στην αντιπροσωπεία μαζί.

Έστω Α το σύνολο που περιέχει όλους τους πιθανούς συνδυασμούς. Από το ερώτημα (α) γνωρίζουμε το πληθικό αριθμό του συνόλου Α. Έστω Β είναι το σύνολο που περιέχει τις αντιπροσωπείες στις οποίες δεν συμπεριλαμβάνονται και οι δύο φοιτητές ταυτόχρονα. Έστω Γ το σύνολο των αντιπροσωπειών στις οποίες οι δύο φοιτητές συμπεριλαμβάνονται ταυτόχρονα. Προφανώς το σύνολο Γ είναι το συμπλήρωμα του Β ως προς το Α.

Ο πληθικός αριθμός του Γ είναι C(10,2)=10!/(2!x8!)= 3.628.800/(40.320x2)=45.

Άρα ο πληθικός αριθμός του συνόλου Β είναι 495-45=450.

Ένας δεύτερος τρόπος για να λύσουμε το πρόβλημα θα ήταν ο εξής:

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

Το συνολικό αποτέλεσμα είναι C(10,3) +C(10,3) +C(10,4)=450

γ) Επαναλάβετε το (α) αν υπάρχουν δύο φοιτητές που δέχονται να είναι στην αντιπροσωπεία μόνο αν είναι μαζί.

Η αντιπροσωπεία ή θα πρέπει να περιέχει και τους δύο φοιτητές ή κανένα από αυτούς.

Το συνολικό αποτέλεσμα είναι C(10,2) +C(10,4) =45+210=255.