4.2 Πολυωνυμικοί συντελεστές

Έχουμε δεί ότι αν θέλουμε να επιλέξουμε $k$ αντικείμενα από $n$, χωρίς επανάθεση, το πλήθος των τρόπων να γίνει αυτό είναι

$${n \choose k} = {n(n-1)\cdots(n-k+1) \over k!} = {n! \over k!(n-k)!}.$$

Τι γίνεται αν θέλουμε να επιλέξουμε, πάλι χωρίς επανάθεση, μια ομάδα στοιχείων του ${\left\{{1,\ldots,n}\right\}}$ μεγέθους $k_1$, μια ομάδα μεγέθους $k_2$, κλπ, και τέλος μια ομάδα μεγέθους $k_r$, όπου για $j=1,\ldots,r$ έχουμε $0 \le k_j \le n$ και επιπλέον ισχύει $k_1+\cdots +k_r = n$; Με πόσους τρόπους δηλ. μπορούμε να διαμερίσουμε το ${\left\{{1,\ldots,n}\right\}}$ σε ένα σύνολο μεγέθους $k_1$, σε ένα σύνολο μεγέθους $k_2$ και τέλος σε ένα σύνολο μεγέθους $k_r$;

Θεώρημα 4.3   Το πλήθος τρόπων να διαμερίσουμε ένα σύνολο με $n$ στοιχεία σε $r$ σύνολα με μεγέθη $k_1,\ldots,k_r$, με $k_1+\cdots +k_r = n$, όταν δε μας ενδιαφέρει η σειρά των στοιχείων μέσα στα σύνολα αυτά, είναι

$${n \choose k_1,\ldots, k_r} = {n! \over k_1! k_2! \cdots k_r!}.$$ (4.4)

Απόδειξη. Το πρώτο σύνολο μπορεί να επιλεγεί με

$${n \choose k_1} = {n! \over k_1!(n-k_1)!}$$

τρόπους. Μετά από την επιλογή του πρώτου συνόλου απομένουν $n-k_1$ στοιχεία αχρησιμοποίητα, άρα το δεύτερο σύνολο μπορεί να επιλεγεί με

$${n - k_1 \choose k_2} = {(n-k_1)! \over k_2!(n-k_1-k_2)!}$$

τρόπους. Συνεχίζονας κατ' αυτόν τον τρόπο παίρνουμε ότι η επιλογή του προτελευταίου συνόλου (με $k_{r-1}$ στοιχεία) μπορεί να γίνει με

$$\frac{(n-k_1-\cdots-k_{r-2})!}{k_{r-1}!(n-k_1-\cdots-k_{r-1})!} = \frac{(n-k_1-\cdots-k_{r-2})!}{k_{r-1}! k_r!}$$

τρόπους. Επίσης, αφού έχουν επιλεγεί τα $r-1$ πρώτα σύνολα δεν υπάρχει πλέον καμιά επιλογή να γίνει αφου τα υπόλοιπα $k_r$ στοιχεία που απομένουν ακόμη αχρησιμοποίητα αναγκαστικά πάνε στο τελευταίο σύνολο που πρέπει να επιλέξουμε.

Έτσι πολλαπλασιάζοντας τις δυνατότητες επιλογών μας για τα πρώτα $r-1$ σύνολα, και κάνοντας τις απλοποιήσεις παίρνουμε τον τύπο (4.4). $\qedsymbol$

Το σύμβολο ${n \choose k_1,\ldots, k_r}$ ονομάζεται πολυωνυμικός συντελεστής (κατ' αναλογία με τα ${n \choose k}$ που ονομάζονται διωνυμικοί συντελεστές). Παρατηρήστε επίσης ότι

$${n \choose k, n-k} = {n \choose k} = {n \choose n-k}.$$

Παρατήρηση 4.1   Ο πολυωνυμικός συντελεστής ${n \choose k_1,\ldots, k_r}$ δεν αλλάζει αν τα $k_1,\ldots,k_r$ αντικατασταθούν από μια μετάθεσή τους (αν αλλάξει δηλ. απλώς η σειρά τους).

Παρατήρηση 4.2   Πρέπει να τονίσουμε εδώ ότι, αν και δε μας ενδιαφέρει η εσωτερική σειρά των συνόλων των στοιχείων που επιλέγουμε, η σειρά των ίδιων των συνόλων είναι προκαθορισμένη. Αυτό είναι ίσως φανερό όταν όλα τα $k_1, k_2, \ldots, k_m$ είναι μεταξύ τους διαφορετικά αλλά δημιουργεί κάποια σύγχυση όταν μερικά από αυτά είναι μεταξύ τους ίσα. Μια ακραία περίπτωση αυτού είναι όταν όλα είναι ίδια. Για παράδειγμα, ο πολυωνυμικός συντελεστής

$${9 \choose 3, 3, 3}$$

μετράει με πόσους τρόπους μπορούμε να χωρίσουμε τους αριθμούς $1,2,\ldots,9$ σε τρείς ομάδες. Αν δύο τρόποι διαφέρουν μόνο ως προς τον εσωτερικό τρόπο γραφής της κάθε ομάδας τότε δε θεωρούνται διαφορετικοί. Έτσι οι τρόποι

$${\left\{{1,2,3}\right\}}, {\left\{{4,5,6}\right\}}, {\left\{{7,8,... ... {\left\{{3,2,1}\right\}}, {\left\{{4,5,6}\right\}}, {\left\{{7,8,9}\right\}}$$

θεωρούνται ίδιοι και μετράνε ως ένα. Αν όμως δύο τρόποι διαφέρουν ως προς τον τρόπο γραφής των ομάδων τότε μετράνε ως διαφορετικοί. Οι τρόποι, π.χ.,

$${\left\{{1,2,3}\right\}}, {\left\{{4,5,6}\right\}}, {\left\{{7,8,... ... {\left\{{4,5,6}\right\}}, {\left\{{1,2,3}\right\}}, {\left\{{7,8,9}\right\}}$$

μετράνε ως διαφορετικοί τρόποι.

Άσκηση 4.11   Έχουμε 10 αριθμημένες μπάλες και τρία κουτιά με χωρητικότητες 5, 3 και 2 μπάλες. Με πόσους τρόπους μπορούμε να βάλουμε τις μπάλες στα κουτιά; (Δεν υπάρχει εσωτερική σειρά στα κουτιά αλλά τα κουτιά είναι μεταξύ τους διακεκριμένα.)

Άσκηση 4.12   Με πόσους τρόπους μπορούμε να τοποθετήσουμε 12 αριθμημένες μπάλες σε 4 όμοια (μη αριθμημένα) κουτιά χωρητικότητας 3 το καθένα;

Άσκηση 4.13   Με πόσους τρόπους μπορούμε να διατάξουμε 5 γράμματα Α, 3 γράμματα Β και 4 γράμματα Γ; Εκφράστε την απάντησή σας σαν ένα πολυωνυμικό συντελεστή.