Συνδυασμοί (μη διατεταγμένα δείγματα)

Υπάρχουν περιπτώσεις (πειράματα τύχης) στις οποίες η σειρά των στοιχείων ενός δείγματος δεν ενδιαφέρει. Π.χ., στο πόκερ. Ένα χέρι του πόκερ αποτελείται από 5 χαρτιά τα οποία επιλέγονται τυχαία από μια συνηθισμένη τράπουλα με 52 χαρτιά. Είδαμε ότι για ένα τέτοιο σύνολο υπάρχουν $(52)_5$ δυνατές διατάξεις (χωρίς επανατοποθέτηση) 5 χαρτιών. Αν όμως κάνουμε έτσι τον υπολογισμό, διαφορετικές διατάξεις των ίδιων 5 χαρτιών θεωρούνται διαφορετικά χέρια. Όμως στο πόκερ η πεντάδα 2,3,4,5,6 σπαθιά (με αυτή τη διάταξη) είναι ίδια με την πεντάδα 3,2,4,5,6 σπαθιά (με αυτή τη διάταξη). Για την ακρίβεια, όλες οι 5! μεταθέσεις των 5 χαρτιών είναι ισοδύναμες στο πόκερ. Έτσι, από τα $(52)_5$ δυνατά χέρια, τα 5! από αυτά είναι απλώς μεταθέσεις αυτών των ίδιων 5 χαρτιών. Άρα το συνολικό πλήθος των χεριών του πόκερ, αν αγνοήσουμε τη σειρά με την οποία εμφανίζονται τα χαρτιά, είναι $(52)_5 / 5!$.

Γενικά, από ένα σύνολο $S$ που περιέχει $s$ διακεκριμένα αντικείμενα, μπορούμε να επιλέξουμε $(s)_n$ διαφορετικά δείγματα μεγέθους $n$ χωρίς επανατοποθέτηση. Κάθε διακεκριμένο υποσύνολο $\{x_1,x_2,...,x_n \}$ από $n$ στοιχεία του $S$ μπορεί να διαταχθεί με $n!$ διαφορετικούς τρόπους. Αν αποφασίσουμε να αγνοήσουμε τη σειρά με την οποία τα αντικείμενα εμφανίζονται στο δείγμα, τότε αυτές οι $n!$ αναδιατάξεις ή μεταθέσεις πρέπει να θεωρηθούν ταυτόσημες. Υπάρχουν λοιπόν $(s)_n / n!$ διαφορετικά δείγματα μεγέθους $n$ που μπορούμε να επιλέξουμε χωρίς επανατοποθέτηση και χωρίς να μας ενδιαφέρει η διάταξη από ένα σύνολο $S$ που περιέχει $s$ διακεκριμένα αντικείμενα. Τα δείγματα αυτά λέγονται συνδυασμοί των $s$ στοιχείων ανά $n$.

Η ποσότητα $(s)_n / n!$ γράφεται συνήθως με τη βοήθεια του συμβόλου του λεγόμενου διωνυμικού συντελεστή

$$\frac{(s)_n}{n!} = \left( \begin{array}{rr} s \\ n \end{array} \right)$$

και μπορούμε να δούμε ότι ισούται με $s! / (s-n)! n!$

$$\left( \begin{array}{r} s \\ n \end{array} \right) = \fra... ...s (s-1)s]} { [1\cdot2\cdots(s-n)]n!} = \frac{s!}{(s-n)! n!} .$$

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

$$(x+y)^s = \sum_{n=0}^s \left( \begin{array}{r} s \\ n \en... ...ots + \left( \begin{array}{r} s \\ s \end{array} \right) y^s ,$$

όπου το πλήθος των συνδυασμών $\left( \begin{array}{r} s \\ n \end{array} \right)$ εμφανίζεται στους συντελεστές του αναπτύγματος. Οι συντελεστές αυτοί έχουν πολλές ενδιαφέρουσες ιδιότητες, όπως για παράδειγμα

1)

$$\left( \begin{array}{r} n \\ j \end{array} \right) = \left( \begin{array}{r} n \\ j-1 \end{array} \right) ,$$

2)

$$\left( \begin{array}{r} n \\ j \end{array} \right) = \left(... ...t) + \left( \begin{array}{r} n-1 \\ j-1 \end{array} \right) ,$$

3)

$$\left( \begin{array}{r} n \\ 0 \end{array} \right) + \left(... ...left( \begin{array}{r} n \\ n \end{array} \right) = 2^n,\ \ \$$

κ. ά.,

οι οποίες αποδεικνύονται πολύ εύκολα. Σημειώστε ότι το σύμβολο $\left( \begin{array}{r} α \\ n \end{array} \right)$ είναι καλά ορισμένο για κάθε πραγματικό αριθμό $α$ και μη αρνητικό $n$, και ότι τα $0!$ και $(α)_0$ είναι εξ ορισμού ίσα με 1.

Παράδειγμα 7: Πόσα είναι τα δυνατά μη διατεταγμένα ζεύγη που μπορούμε να φτιάξουμε από τα γράμματα $a, b, c ;$

Τα ζεύγη αυτά είναι οι δυνατοί συνδυασμοί των τριών αριθμών ανά δύο, άρα $\left( \begin{array}{r} 3 \\ 2 \end{array} \right)$ $=3!/2! 1!=3$ (είναι τα $(a,b),(a,c),(b,c)$).

Παράδειγμα 8: Σύνθεση επιτροπής.
Το τμήμα Υλικών έχει 3 καθηγητές πρώτης βαθμίδας, 6 αναπληρωτές καθηγητές, και 8 επίκουρους καθηγητές. Μια τριμέλής επιτροπή εκλέγεται τυχαία από τα παραπάνω μέλη ΔΕΠ. Βρείτε την πιθανότητα όλα τα μέλη της επιτροπής να είναι επίκουροι καθηγητές.

Αν ορίσουμε ως $Α$ το γεγονός ``και τα τρία μέλη της επιτροπής είναι επίκουροι'', τότε η πιθανότητα του $Α$ δίνεται από το πλήθος των στοιχείων του $Α$ προς το συνολικό πλήθος των δειγματοσημείων του πειράματος (που το πλήθος των δυνατών μη διατεταγμένων τριάδων που μπορούμε να φτιάξουμε από τα υπάρχοντα μέλη ΔΕΠ). Συνολικά, το τμήμα έχει 17 μέλη ΔΕΠ. Η επιτροπή των τριών μπορεί να εκλεγεί από τους 17 με $\left( \begin{array}{r} 17 \\ 3 \end{array} \right)$ τρόπους. Υπάρχουν 8 επίκουροι καθηγητές, και οι 3 της επιτροπής μπορούν να επιλεγούν από αυτούς με $\left( \begin{array}{r} 8 \\ 3 \end{array} \right)$ τρόπους. $'$Αρα η ζητούμενη πιθανότητα είναι

$$P = \left( \begin{array}{r} 8 \\ 3 \end{array} \right) / \left( \begin{array}{r} 17 \\ 3 \end{array} \right) \simeq 0.082 .$$

Σε πολλές περιπτώσεις οδηγούμαστε στον υπολογισμό παραγοντικών. Όταν όμως ο αριθμός, έστω $n$, είναι ακόμα και μέτριου μεγέθους (για παράδειγμα $n=15$), τότε το $n!$ είναι πάρα πολύ μεγάλος αριθμός. Στις περιπτώσεις αυτές, μια προσεγγιστική τιμή του $n!$ δίνεται από τον τύπο του Stirling, σύμφωνα με τον οποίο

$$n! \simeq \left( \frac{n}{e} \right)^n \sqrt{2\pi n} ,$$

όπου $e$ είναι η βάση των νεπέρειων λογαρίθμων (σταθερά του Euler), $e=2.71828...$. Μια τελευταία παρατήρηση που αφορά τον συμβολισμό: Οι ποσότητες $(s)_n$ και $(s)_n / n!$ συμβολίζονται επίσης με $\ _s P_n$ ($P$ από το Permutations (μεταθέσεις) ) και $\ _s C_n$ ($C$ από το Combinations (συνδυασμοί) ), αντίστοιχα