Συνδυασμοί

Εισαγωγή στους Συνδυασμούς

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

Ορισμός Συνδυασμού

Συνδυασμός $n$ ανά $k$ είναι κάθε επιλογή $k$ αντικειμένων από σύνολο $n$ διαφορετικών αντικειμένων, χωρίς να λαμβάνεται υπόψη η σειρά.

Ο αριθμός των συνδυασμών $n$ ανά $k$ συμβολίζεται:

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

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

Σχέση με Διατάξεις

Κάθε συνδυασμός $k$ αντικειμένων μπορεί να διαταχθεί με $k!$ τρόπους, επομένως:

$P(n,k) = \binom{n}{k} \cdot k!$

ή ισοδύναμα:

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

Βασικές Ιδιότητες

1. Ακραίες Τιμές

$\binom{n}{0} = \binom{n}{n} = 1$

$\binom{n}{1} = \binom{n}{n-1} = n$

2. Συμμετρία

$\binom{n}{k} = \binom{n}{n-k}$

Η επιλογή $k$ αντικειμένων είναι ισοδύναμη με την απόρριψη $n-k$ αντικειμένων.

3. Αναδρομικός Τύπος (Ταυτότητα Pascal)

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

Αυτή η ιδιότητα είναι η βάση του τριγώνου του Pascal.

4. Άθροισμα Συνδυασμών

$\sum_{k=0}^{n} \binom{n}{k} = 2^n$

Αυτό εκφράζει το πλήθος όλων των υποσυνόλων ενός συνόλου $n$ στοιχείων.

5. Εναλλασσόμενο Άθροισμα

$\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$

Υπολογισμός Συνδυασμών

Πρακτικός Υπολογισμός

Για τον υπολογισμό του $\binom{n}{k}$ , χρησιμοποιούμε:

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

Παράδειγμα: $\binom{10}{3} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = \frac{720}{6} = 120$

Συμβουλή Υπολογισμού

Για μεγάλο $k$ , χρησιμοποιούμε τη συμμετρία: αν $k > n/2$ , υπολογίζουμε $\binom{n}{n-k}$