Συνδυασμοί

Χρησιμοποιούμε τους συνδυασμούς όταν από ένα σύνολο αντικειμένων επιλέγουμε έναν ορισμένο αριθμό αντικειμένων και δεν έχει σημασία η σειρά με την οποία τα επιλέγουμε. Χαρακτηριστικό πρόβλημα είναι το Λόττο – στο δοχείο έχουμε 49 αριθμούς και τραβάμε από αυτούς 6, χωρίς να έχει σημασία με ποια σειρά τους τραβάμε.

Εξαγωγή του τύπου

Έστω ένα σύνολο M, για παράδειγμα M = {a, b, c, d, e}. Τότε ένας συνδυασμός των στοιχείων του M ανά κ είναι ένα υποσύνολο K ⊆ M που περιέχει ακριβώς κ στοιχεία. Επειδή το K είναι σύνολο, φυσικά δεν έχει σημασία η σειρά. Άρα ένας συνδυασμός ανά τρία των στοιχείων του M θα μπορούσε να είναι το {a, b, d} ή το {b, c, d}.

Η διαφορά από τις διατάξεις είναι ότι στις διατάξεις είχε σημασία η σειρά, άρα οι (a, b, e) και (e, b, a) είναι διαφορετικές διατάξεις, αλλά είναι ο ίδιος συνδυασμός, γιατί και η (a, b, e) και η (e, b, a) περιέχουν τα ίδια στοιχεία· ότι είναι σε διαφορετική σειρά δεν μας ενδιαφέρει στους συνδυασμούς.

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

$${\mathrm{\Delta }}_{\nu }^{\kappa }=\frac{\nu !}{(\nu -\kappa )!}.$$

Αν λοιπόν υπολογίζαμε το πλήθος όλων των διατάξεων ανά τρία του προηγούμενου συνόλου M = {a, b, c, d, e}, θα παίρναμε ${\mathrm{\Delta }}_5^3=60$ διαφορετικές διατάξεις. Όμως για κάθε τριάδα θα είχαμε εκεί και όλες τις μεταθέσεις της. Δηλαδή θα είχαμε την τριάδα abc, αλλά και τις τριάδες acb, bac, bca, cab και cba. Αυτές είναι έξι διαφορετικές διατάξεις, αλλά είναι ένας συνδυασμός, γιατί έχουν όλες τα ίδια στοιχεία.

Αν λοιπόν έχουμε μια τριάδα, πόσες διαφορετικές μεταθέσεις της τριάδας υπάρχουν; Ακριβώς 3!. Με άλλα λόγια, υπάρχουν ακριβώς 3! φορές περισσότερες διατάξεις ανά τρία από συνδυασμούς ανά τρία. Αντί να μετράμε έναν συνδυασμό, μετράμε 3! φορές περισσότερες διατάξεις, με κάθε μετάθεση της δοσμένης τριάδας. Άρα αν διαιρέσουμε το πλήθος των διατάξεων με το 3!, παίρνουμε το πλήθος των συνδυασμών.

Την προηγούμενη διαδικασία μπορούμε να τη γενικεύσουμε και να πούμε ότι αν ψάχνουμε το πλήθος όλων των διαφορετικών συνδυασμών ανά κ από ένα σύνολο μεγέθους ν, τότε αυτό το πλήθος, που το συμβολίζουμε ${\mathrm{\Sigma }}_{\nu }^{\kappa }$, είναι ίσο με

$${\mathrm{\Sigma }}_{\nu }^{\kappa }=\frac{{\mathrm{\Delta }}_{\nu }^{\kappa }}{\kappa !},$$

δηλαδή το πλήθος των διατάξεων διά κ!, που είναι το πλήθος των μεταθέσεων κάθε κ-άδας. Τον τύπο μπορούμε να τον επεξεργαστούμε γράφοντας αναλυτικά τον τύπο για τον υπολογισμό των διατάξεων:

$${\mathrm{\Sigma }}_{\nu }^{\kappa }=\frac{{\mathrm{\Delta }}_{\nu }^{\kappa }}{\kappa !}=\frac{\nu !}{(\nu -\kappa )!}\cdot \frac{1}{\kappa !}=\frac{\nu !}{(\nu -\kappa )!\cdot \kappa !}.$$

Παράδειγμα: το πλήθος των συνδυασμών ανά δύο από το σύνολο {a, b, c} είναι

$${\mathrm{\Sigma }}_3^2=\frac{3!}{1!\cdot 2!}=3$$

και είναι οι εξής συνδυασμοί: {a, b}, {a, c} και {b, c}. Για τους συνδυασμούς ανά τρία από το αρχικό σύνολο M = {a, b, c, d, e} θα παίρναμε πλήθος

$${\mathrm{\Sigma }}_5^3=\frac{5!}{(5-3)!\cdot 3!}=10$$

και είναι οι εξής συνδυασμοί: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

Διωνυμικός συντελεστής

Ο προηγούμενος συμβολισμός του τύπου με το ${\mathrm{\Sigma }}_{\nu }^{\kappa }$ δεν είναι ο πιο διαδεδομένος, και αντί γι' αυτόν χρησιμοποιείται ο λεγόμενος διωνυμικός συντελεστής. Ο διωνυμικός συντελεστής έχει αυτήν τη μορφή

$$(\genfrac{}{}{0ex}{}{\nu }{\kappa })$$

είναι ένα είδος κλάσματος χωρίς κλασματική γραμμή (που εσύ από συνήθεια θα τη γράφεις έτσι κι αλλιώς), αλλά με παρενθέσεις (που δεν είναι προαιρετικές, πρέπει να υπάρχουν). Τον διωνυμικό συντελεστή τον διαβάζουμε «ν ανά κ». Η τιμή του διωνυμικού συντελεστή είναι τότε ίδια με το ${\mathrm{\Sigma }}_{\nu }^{\kappa }$.

$$(\genfrac{}{}{0ex}{}{\nu }{\kappa })=\frac{\nu !}{(\nu -\kappa )!\cdot \kappa !}$$

Αν λοιπόν έχουμε ένα σύνολο με 5 στοιχεία και επιλέγουμε από αυτό τετράδες, το συνολικό πλήθος τους θα είναι

$$(\genfrac{}{}{0ex}{}{5}{4})=\frac{5!}{1!\cdot 4!}=5.$$

Βασικές σχέσεις

Για τον διωνυμικό συντελεστή και ν ∈ ℕ^∗ ισχύει:

$$\begin{array}{rcl}(\genfrac{}{}{0ex}{}{\nu }{0})=(\genfrac{}{}{0ex}{}{\nu }{\nu })=(\genfrac{}{}{0ex}{}{0}{0})& =& 1\\ (\genfrac{}{}{0ex}{}{\nu }{1})& =& \nu \end{array}$$

Επίσης, για ν, κ ∈ ℕ και κ ≤ ν ισχύει

$$\begin{array}{rcl}(\genfrac{}{}{0ex}{}{\nu }{\nu -\kappa })& =& (\genfrac{}{}{0ex}{}{\nu }{\kappa }).\end{array}$$

Και για ν, κ ∈ ℕ και κ < ν ισχύει

$$\begin{array}{rcl}(\genfrac{}{}{0ex}{}{\nu }{\kappa })+(\genfrac{}{}{0ex}{}{\nu }{\kappa +1})& =& (\genfrac{}{}{0ex}{}{\nu +1}{\kappa +1}).\end{array}$$

Αριθμομηχανή

Η παρακάτω αριθμομηχανή υπολογίζει τον διωνυμικό συντελεστή $(\genfrac{}{}{0ex}{}{\nu }{\kappa })$.

Λυμένα παραδείγματα

1. Θα ξεκινήσουμε με το Λόττο που αναφέραμε ήδη. Σε αυτό τραβάμε από ένα δοχείο, στο οποίο υπάρχουν 49 μπάλες, συνολικά 6 μπάλες. Πόσα διαφορετικά αποτελέσματα μπορεί να έχει η κλήρωση;

   Πρώτα απ' όλα – έχει σημασία η σειρά με την οποία τραβιούνται οι αριθμοί; Δεν έχει, στοιχηματίζουμε μόνο στους αριθμούς, όχι στη σειρά τους. Θα χρησιμοποιήσουμε συνδυασμούς. Έχουμε συνολικά 49 μπάλες, τραβάμε 6 μπάλες, και παίρνουμε τον διωνυμικό συντελεστή

   $$(\genfrac{}{}{0ex}{}{49}{6})=\frac{49!}{(49-6)!\cdot 6!}=\frac{49!}{43!\cdot 6!}=13.983.816$$

   Υπάρχουν συνολικά 13.983.816 δυνατά αποτελέσματα της κλήρωσης. Αυτό μας δίνει, παρεμπιπτόντως, την πιθανότητα να κερδίσουμε με ένα δελτίο 1/13.983.816, που είναι 0,00000715112 %.

2. Ο Στάθης είναι σε ένα πανηγύρι στο χωριό, όπου βρίσκονται συνολικά 13 όμορφες κοπέλες με τις οποίες θα ήθελε να χορέψει. Ο Στάθης ξέρει ότι μπορεί να χορέψει σε μια βραδιά με 4 διαφορετικές κοπέλες. Από πόσες διαφορετικές τετράδες μπορεί να διαλέξει ο Στάθης;

   Πάλι ένα απλό παράδειγμα συνδυασμών, η σειρά δεν έχει σημασία, ο Στάθης θα περάσει το ίδιο καλά με την πρώτη κοπέλα όσο και με την τελευταία. Έχουμε λοιπόν ένα σύνολο 13 κοπελών, από τις οποίες επιλέγουμε κάθε φορά 4 κοπέλες. Αυτό οδηγεί στον διωνυμικό συντελεστή

   $$(\genfrac{}{}{0ex}{}{13}{4})=715.$$

3. Έχεις μια ομάδα πενήντα ανθρώπων – οι μισοί άνδρες και οι μισοί γυναίκες. Πόσες διαφορετικές τριάδες ανθρώπων υπάρχουν, αν δεν επιτρέπεται να αποτελούνται μόνο από ένα φύλο (δηλαδή στην τριάδα δεν επιτρέπεται να υπάρχουν τρεις άνδρες ή τρεις γυναίκες);

   Αυτός είναι λίγο πιο σύνθετος συνδυασμός. Αν αποκλείσουμε τις τριάδες ενός φύλου, μένουν μόνο δύο δυνατότητες για τη σύνθεση της τριάδας – δύο άνδρες και μία γυναίκα ή ένας άνδρας και δύο γυναίκες, και το πλήθος των συνδυασμών της πρώτης ομάδας (δύο άνδρες και μία γυναίκα) θα είναι το ίδιο με το πλήθος των συνδυασμών της δεύτερης ομάδας. Μας αρκεί λοιπόν να υπολογίσουμε το πλήθος των συνδυασμών της πρώτης ομάδας και μετά να το πολλαπλασιάσουμε επί δύο. Τώρα είναι πάλι παιχνιδάκι. Προσδιορίζουμε το πλήθος των συνδυασμών των διαφορετικών ζευγών ανδρών, που είναι είκοσι πέντε ανά δύο, και το πολλαπλασιάζουμε με το πλήθος των συνδυασμών μίας γυναίκας (που κάνει είκοσι πέντε, δες τις βασικές σχέσεις παραπάνω, συγκεκριμένα τη δεύτερη γραμμή). Αυτό το αποτέλεσμα το πολλαπλασιάζουμε μόνο επί δύο και έχουμε το τελικό αποτέλεσμα.

   $$2\cdot (\genfrac{}{}{0ex}{}{25}{2})\cdot (\genfrac{}{}{0ex}{}{25}{1})=15000.$$

4. Σε ένα κουτί υπάρχουν 15 προϊόντα, από τα οποία τα 4 είναι ελαττωματικά. Με πόσους τρόπους μπορούμε να επιλέξουμε 6 προϊόντα ώστε

   • κανένα να μην είναι ελαττωματικό; Σε αυτήν την περίπτωση επιλέγουμε 6 προϊόντα από τα 15 − 4 = 11 προϊόντα που δεν είναι ελαττωματικά. Παίρνουμε έτσι τον διωνυμικό συντελεστή

     $$(\genfrac{}{}{0ex}{}{11}{6})=462.$$

   • να είναι ελαττωματικό ακριβώς ένα προϊόν; Επιλέγουμε έτσι ένα σύνολο που περιέχει 5 καλά προϊόντα και 1 ελαττωματικό. Καλά προϊόντα έχουμε συνολικά 11, ελαττωματικά έχουμε 4. Χρησιμοποιούμε την πολλαπλασιαστική αρχή και παίρνουμε το αποτέλεσμα:

     $$(\genfrac{}{}{0ex}{}{11}{5})\cdot (\genfrac{}{}{0ex}{}{4}{1})=1848$$

   • να είναι το πολύ ένα ελαττωματικό; Για τη λύση θα χρησιμοποιήσουμε τα προηγούμενα αποτελέσματα. Ξέρουμε ότι έχουμε συνολικά 462 δυνατότητες να επιλέξουμε ακριβώς 6 καλά προϊόντα και έχουμε 1848 δυνατότητες να επιλέξουμε πέντε καλά και ένα ελαττωματικό προϊόν. Χρησιμοποιούμε λοιπόν την αθροιστική αρχή, προσθέτουμε αυτά τα αποτελέσματα και έχουμε το αποτέλεσμα που θέλουμε, δηλαδή το πολύ ένα ελαττωματικό προϊόν (= είτε κανένα ελαττωματικό προϊόν είτε ακριβώς ένα). Το αποτέλεσμα είναι λοιπόν: 462 + 1848 = 2310.