Διατάξεις Ομάδων Όμοιων Αντικειμένων

Ας επιστρέψουμε στο πρόβλημα στο οποίο τοποθετούμε k μπάλες σε n αριθμημένα κουτιά (με την προϋπόθεση ότι κάθε κουτί χωράει μία μπάλα). Πόσες διαφορετικές διατάξεις υπάρχουν δεδομένου ότι κάποιες από τις μπάλες είναι όμοιες;

Παράδειγμα: Με πόσους τρόπους μπορούμε να τοποθετήσουμε 2 κόκκινες, μία μπλε και μία πράσινη μπάλα σε 10 κουτιά;

Ας υποθέσουμε ότι με κάποιο τρόπο μπορούμε να ξεχωρίσουμε τη μία κόκκινη μπάλα από την άλλη, π.χ. έστω ότι οι δύο κόκκινες μπάλες έχουν δύο αποχρώσεις του κόκκινου, η μία ανοιχτό και η άλλη σκούρο. Σε αυτή τη περίπτωση και οι τέσσερις μπάλες θα ήταν διαφορετικές και τότε οι διαφορετικές διατάξεις θα ήταν P(10,4)=10x9x8x7=5040.

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

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

Συνεπώς ο συνολικός αριθμός των τρόπων που μπορούμε να τοποθετήσουμε 2 κόκκινες, μία μπλε και μία πράσινη μπάλα σε 10 κουτιά είναι 5040/2 = 2520.

Παράδειγμα: Με πόσους τρόπους μπορούμε να τοποθετήσουμε 3 κόκκινες, μία μπλε και μία πράσινη μπάλα σε 10 κουτιά;

Ας υποθέσουμε ότι με κάποιο τρόπο μπορούμε να ξεχωρίσουμε τη μία κόκκινη μπάλα από την άλλη, π.χ. έστω ότι οι τρεις κόκκινες μπάλες έχουν τρεις αποχρώσεις του κόκκινου. Σε αυτή τη περίπτωση και οι πέντε μπάλες θα ήταν διαφορετικές και τότε οι διαφορετικές διατάξεις θα ήταν P(10,5)=10x9x8x7x6=30240.

Για κάθε συγκεκριμένη διάταξη της μπλε και της πράσινης μπάλας μπορούμε να διατάξουμε τις τρεις κόκκινες μπάλες με 3x2x1=6 τρόπους.

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

Συνεπώς ο συνολικός αριθμός των τρόπων που μπορούμε να τοποθετήσουμε 3 κόκκινες, μία μπλε και μία πράσινη μπάλα σε 10 κουτιά είναι 30240/6 = 5040.

Γενικότερα μπορούμε να τοποθετήσουμε k έγχρωμες μπάλες σε n αριθμημένα κουτιά, όπου q1 από αυτές είναι ενός χρώματος, q2 από αυτές είναι ενός δεύτερου χρώματος, …, και qt είναι ενός χρώματος t με

P(n, k)/q1!q2!…qt !

Ο παραπάνω τύπος προκύπτει από τις εξής παρατηρήσεις:

Αν τοποθετούσαμε k διαφορετικά βαμμένες μπάλες σε n αριθμημένα κουτιά θα είχαμε P(n, k) διαφορετικές διατάξεις. Παρατηρούμε όμως ότι μία τοποθέτηση που έχουμε κάνει στις k μπάλες δεν αλλάζει με το να αναδιατάξουμε τις q1 μπάλες του ενός χρώματος, ή με το να αναδιατάξουμε τις q2 μπάλες του δεύτερου χρώματος, …, ή με το να αναδιατάξουμε τις qt μπάλες του χρώματος t.

Παράδειγμα: Με πόσους τρόπους μπορούμε να βάψουμε 12 γραφεία, έτσι ώστε 3 από αυτά να είναι κόκκινα, 2 από αυτά μπλε, και 4 από αυτά πράσινα;

Υπάρχουν P(12, 9)=12!/3! τρόποι να βάψουμε με διαφορετικό χρώμα 9 από τα 12 γραφεία. Επειδή 3 από αυτά θα είναι κόκκινα, 2 από αυτά μπλε, και 4 από αυτά πράσινα, ο συνολικός αριθμός των τρόπων με τους οποίους μπορούμε να βάψουμε τα γραφεία είναι:

12!/3!3!2!4!= 479.001.600/6x6x2x24= 479.001.600/864=554.400

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

Υπάρχουν 5! τρόποι να δημιουργήσουμε συμβολοσειρές με 5 διαφορετικά σύμβολα. Επειδή 3 από αυτά θα είναι παύλες και 2 από αυτά τελείες, ο συνολικός αριθμός των είναι: 5!/3!2!= 120/6x2=10.