Συνδυαστική

Εισαγωγή στη Συνδυαστική

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

Θεμελιώδεις Αρχές Απαρίθμησης

Αρχή Πρόσθεσης

Αν μια εργασία μπορεί να γίνει με έναν από $n_1$ τρόπους Ή με έναν από $n_2$ τρόπους (αμοιβαία αποκλειόμενους), τότε η εργασία μπορεί να γίνει συνολικά με:

$$n_1 + n_2 \text{ τρόπους}$$

Παράδειγμα: Αν έχουμε 3 κόκκινα και 5 μπλε μολύβια, μπορούμε να επιλέξουμε ένα μολύβι με $3 + 5 = 8$ τρόπους.

Αρχή Πολλαπλασιασμού

Αν μια εργασία αποτελείται από δύο διαδοχικά βήματα, το πρώτο μπορεί να γίνει με $n_1$ τρόπους ΚΑΙ το δεύτερο με $n_2$ τρόπους, τότε η συνολική εργασία μπορεί να γίνει με:

$$n_1 \times n_2 \text{ τρόπους}$$

Παράδειγμα: Αν έχουμε 4 πουκάμισα και 3 παντελόνια, μπορούμε να δημιουργήσουμε $4 \times 3 = 12$ διαφορετικούς συνδυασμούς ντυσίματος.

Παραγοντικό (Factorial)

Το παραγοντικό ενός μη αρνητικού ακεραίου $n$ ορίζεται:

$$n! = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 2 \cdot 1$$

Ειδικές περιπτώσεις:

• $0! = 1$ (εξ ορισμού)
• $1! = 1$

Παραδείγματα:

• $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$
• $7! = 5040$
• $10! = 3628800$

Χρήσιμη ιδιότητα:

$$n! = n \cdot (n-1)!$$

Διατάξεις (Permutations)

Διατάξεις χωρίς Επανάληψη

Ο αριθμός των τρόπων για να διατάξουμε $k$ αντικείμενα από σύνολο $n$ διαφορετικών αντικειμένων (η σειρά μετράει):

$$P(n,k) = \frac{n!}{(n-k)!} = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1)$$

Ειδική περίπτωση: Όταν $k = n$:

$$P(n,n) = n!$$

Αυτός είναι ο αριθμός των μεταθέσεων $n$ αντικειμένων.

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

$$P(5,5) = 5! = 120 \text{ τρόποι}$$

Παράδειγμα 2: Σε αγώνα με 8 αθλητές, με πόσους τρόπους μπορούν να δοθούν τα 3 μετάλλια (χρυσό, ασημένιο, χάλκινο);

$$P(8,3) = 8 \cdot 7 \cdot 6 = 336 \text{ τρόποι}$$

Διατάξεις με Επανάληψη

Αν επιτρέπεται η επανάληψη, ο αριθμός διατάξεων $k$ θέσεων από $n$ αντικείμενα είναι:

$$n^k$$

Παράδειγμα 3: Πόσοι τετραψήφιοι κωδικοί PIN υπάρχουν (ψηφία 0-9);

$$10^4 = 10000 \text{ κωδικοί}$$

Παράδειγμα 4: Πόσες λέξεις 3 γραμμάτων μπορούμε να σχηματίσουμε από το ελληνικό αλφάβητο (24 γράμματα);

$$24^3 = 13824 \text{ λέξεις}$$

Συνδυασμοί (Combinations)

Ο αριθμός των τρόπων για να επιλέξουμε $k$ αντικείμενα από σύνολο $n$ διαφορετικών αντικειμένων (η σειρά ΔΕΝ μετράει):

$$C(n,k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$$

Διαβάζεται: "$n$ ανά $k$" ή "$n$ choose $k$"

Ιδιότητες Συνδυασμών

1. $\binom{n}{0} = \binom{n}{n} = 1$
2. $\binom{n}{1} = \binom{n}{n-1} = n$
3. Συμμετρία: $\binom{n}{k} = \binom{n}{n-k}$
4. Αναδρομικός τύπος (Ταυτότητα Pascal): $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$
5. Άθροισμα: $\sum_{k=0}^{n} \binom{n}{k} = 2^n$

Παραδείγματα Συνδυασμών

Παράδειγμα 5: Από ομάδα 10 ατόμων, με πόσους τρόπους μπορούμε να επιλέξουμε επιτροπή 3 ατόμων;

$$\binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = \frac{720}{6} = 120 \text{ τρόποι}$$

Παράδειγμα 6: Πόσα διαφορετικά χέρια 5 φύλλων μπορούμε να πάρουμε από τράπουλα 52 φύλλων;

$$\binom{52}{5} = \frac{52!}{5! \cdot 47!} = \frac{52 \cdot 51 \cdot 50 \cdot 49 \cdot 48}{120} = 2598960$$

Παράδειγμα 7: Από 6 άνδρες και 4 γυναίκες, με πόσους τρόπους μπορούμε να επιλέξουμε επιτροπή 4 ατόμων με ακριβώς 2 γυναίκες;

$$\binom{6}{2} \cdot \binom{4}{2} = 15 \cdot 6 = 90 \text{ τρόποι}$$

Εφαρμογές στις Πιθανότητες

Παράδειγμα 8: Λοταρία

Σε λαχείο επιλέγουμε 6 αριθμούς από 49. Ποια η πιθανότητα να κερδίσουμε (να βρούμε και τους 6);

Λύση:

• Δυνατές επιλογές: $\binom{49}{6} = 13983816$
• Ευνοϊκές: 1 (η σωστή επιλογή)
• $P = \frac{1}{13983816} \approx 0.0000000715 \approx 7.15 \times 10^{-8}$

Παράδειγμα 9: Δύο Ζάρια

Ρίχνουμε δύο ζάρια. Ποια η πιθανότητα να φέρουμε διπλό (ίδιο αριθμό και στα δύο);

Λύση:

• Συνολικά αποτελέσματα: $6^2 = 36$
• Διπλά: $\{(1,1), (2,2), (3,3), (4,4), (5,5), (6,6)\}$ = 6
• $P = \frac{6}{36} = \frac{1}{6}$

Παράδειγμα 10: Γενέθλια

Σε ομάδα 23 ατόμων, ποια η πιθανότητα τουλάχιστον 2 να έχουν τα ίδια γενέθλια;

Λύση:

• Υπολογίζουμε το συμπλήρωμα: κανείς δεν έχει τα ίδια γενέθλια
• $P(\text{όλοι διαφορετικά}) = \frac{365 \cdot 364 \cdot 363 \cdot ... \cdot 343}{365^{23}} = \frac{P(365,23)}{365^{23}}$
• $P(\text{τουλάχιστον 2 ίδια}) = 1 - P(\text{όλοι διαφορετικά}) \approx 1 - 0.493 = 0.507$

Με μόλις 23 άτομα, η πιθανότητα κοινών γενεθλίων ξεπερνά το 50%!

Διατάξεις με Επαναλαμβανόμενα Στοιχεία

Αν έχουμε $n$ αντικείμενα με $n_1$ όμοια του πρώτου είδους, $n_2$ όμοια του δεύτερου, κλπ., ο αριθμός των διατάξεων είναι:

$$\frac{n!}{n_1! \cdot n_2! \cdot ... \cdot n_k!}$$

Παράδειγμα 11: Πόσες αναγραμματισμοί έχει η λέξη "ΜΑΜΑ";

• 4 γράμματα: 2 Μ και 2 Α
• $\frac{4!}{2! \cdot 2!} = \frac{24}{4} = 6$ αναγραμματισμοί

Τρίγωνο του Pascal

Οι συνδυασμοί σχηματίζουν το τρίγωνο του Pascal:

$$\begin{array}{ccccccc} & & & 1 & & & \\ & & 1 & & 1 & & \\ & 1 & & 2 & & 1 & \\ 1 & & 3 & & 3 & & 1 \\ \end{array}$$

Κάθε αριθμός είναι το άθροισμα των δύο από πάνω του: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$