Συνδυασμός (μαθηματικά)

Στα μαθηματικά, συνδυασμός των $n$ στοιχείων ενός συνόλου $A$ ανά $k$ ονομάζεται κάθε υποσύνολο του συνόλου $A$ με $k$ στοιχεία.Πρότυπο:RpΠρότυπο:Rp

Για παράδειγμα, για το σύνολο $A=\{\alpha ,\beta ,\gamma ,\delta \}$, τα υποσύνολα με τρία στοιχεία είναι τα εξής:

$\{\alpha ,\beta ,\gamma \}$, $\{\alpha ,\beta ,\delta \}$, $\{\alpha ,\gamma ,\delta \}$ και $\{\beta ,\gamma ,\delta \}$.

Κάθε ένα από αυτά τα τέσσερα υποσύνολα είναι ένας συνδυασμός των 4 στοιχείων του $A$ ανά 3.

Το πλήθος των συνδυασμών $n$ στοιχείων ανά $k$ δίνονται από τον διωνυμικό συντελεστή

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}=\frac{n\cdot (n-1)\cdot \dots \cdot 2\cdot 1}{(k\cdot (k-1)\cdot \dots \cdot 1)\cdot ((n-k)\cdot (n-k-1)\cdot \dots \cdot 1)}$,

και διαβάζεται ως «συνδυασμοί των $n$ ανά $k$».

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

Για ένα σύνολο $A=\{\alpha ,\beta ,\gamma \}$ με τρία στοιχεία:

• Οι συνδυασμοί $3$ ανά $1$ είναι $(\genfrac{}{}{0ex}{}{3}{1})=\frac{3!}{1!\cdot 2!}=3$: $\{\alpha \}$, $\{\beta \}$, $\{\gamma \}$.
• Οι συνδυασμοί $3$ ανά $2$ είναι $(\genfrac{}{}{0ex}{}{3}{2})=\frac{3!}{2!\cdot 1!}=3$: $\{\alpha ,\beta \}$, $\{\beta ,\gamma \}$, $\{\alpha ,\gamma \}$.
• Οι συνδυασμοί $3$ ανά $3$ είναι $(\genfrac{}{}{0ex}{}{3}{3})=\frac{3!}{3!\cdot 0!}=1$: $\{\alpha ,\beta ,\gamma \}$.

Για ένα σύνολο $A=\{\alpha ,\beta ,\gamma ,\delta \}$ με τέσσερα στοιχεία:

• Οι συνδυασμοί $4$ ανά $1$ είναι $(\genfrac{}{}{0ex}{}{4}{1})=\frac{4!}{1!\cdot 3!}=4$: $\{\alpha \}$, $\{\beta \}$, $\{\gamma \}$, $\{\delta \}$.
• Οι συνδυασμοί $4$ ανά $2$ είναι $(\genfrac{}{}{0ex}{}{4}{2})=\frac{4!}{2!\cdot 2!}=6$: $\{\alpha ,\beta \}$, $\{\beta ,\gamma \}$, $\{\alpha ,\gamma \}$, $\{\alpha ,\delta \}$, $\{\beta .\delta \}$, $\{\delta ,\gamma \}$.
• Οι συνδυασμοί $4$ ανά $3$ είναι $(\genfrac{}{}{0ex}{}{4}{3})=\frac{4!}{3!\cdot 1!}=4$: $\{\beta ,\gamma ,\delta \}$, $\{\alpha ,\gamma ,\delta \}$, $\{\alpha ,\beta ,\delta \}$, $\{\alpha ,\beta ,\gamma \}$.
• Οι συνδυασμοί $4$ ανά $4$ είναι $(\genfrac{}{}{0ex}{}{4}{4})=\frac{4!}{4!\cdot 0!}=1$: $\{\alpha ,\beta ,\gamma ,\delta \}$.

Πλήθος των συνδυασμών

Το πλήθος των συνδυασμών $n$ στοιχείων ανά $k$ (για $n\ge k$) είναι:

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}$,

όπου $n!=n\cdot (n-1)\cdot \dots \cdot 2\cdot 1$ είναι το παραγοντικό του $n$.

Απόδειξη με πλήθος διατάξεων

Υπενθυμίζουμε ότι μία διάταξη $n$ στοιχείων του συνόλου $A$ ανά $k$ είναι οποιαδήποτε $k$-άδα διαφορετικών στοιχείων του $A$. Σε αντίθεση με τους συνδυασμούς η $(\alpha ,\beta ,\gamma )$ είναι διαφορετική διάταξη από την $(\beta ,\alpha ,\gamma )$.

Το πλήθος των διατάξεων $n$ στοιχείων ανά $k$ είναι $(n{)}_k=\frac{n}{(n-k)!}$. Κάθε συνδυασμός αντιστοιχεί σε ακριβώς $k!$ διατάξεις, τις δυνατές μεταθέσεις των στοιχείων του. Επομένως, υπάρχουν συνολικά

$\frac{(n{)}_k}{k!}=\frac{n!}{k!(n-k)!}=(\genfrac{}{}{0ex}{}{n}{k})$

συνδυασμοί.

Για παράδειγμα, για κάθε έναν από τους τέσσερις συνδυασμούς $4$ ανά $3$, αντιστοιχούν οι παρακάτω $3!=6$ διατάξεις:

$\{\beta ,\gamma ,\delta \}$	$\{\alpha ,\gamma ,\delta \}$	$\{\alpha ,\beta ,\delta \}$	$\{\alpha ,\beta ,\gamma \}$
$(\beta ,\gamma ,\delta )$	$(\alpha ,\gamma ,\delta )$	$(\alpha ,\beta ,\delta )$	$(\alpha ,\beta ,\gamma )$
$(\beta ,\delta ,\gamma )$	$(\alpha ,\delta ,\gamma )$	$(\alpha ,\delta ,\beta )$	$(\alpha ,\gamma ,\beta )$
$(\gamma ,\beta ,\delta )$	$(\gamma ,\alpha ,\delta )$	$(\beta ,\alpha ,\delta )$	$(\beta ,\alpha ,\gamma )$
$(\gamma ,\delta ,\beta )$	$(\gamma ,\delta ,\alpha )$	$(\beta ,\delta ,\alpha )$	$(\beta ,\gamma ,\alpha )$
$(\delta ,\beta ,\gamma )$	$(\delta ,\alpha ,\gamma )$	$(\delta ,\alpha ,\beta )$	$(\gamma ,\alpha ,\beta )$
$(\delta ,\gamma ,\beta )$	$(\delta ,\gamma ,\alpha )$	$(\delta ,\alpha ,\beta )$	$(\gamma ,\beta ,\alpha )$

Απόδειξη με αναδρομικό ορισμό

Έστω $C_{n,k}$ το πλήθος των $n$ ανά $k$ συνδυασμών. Θέλουμε να δείξουμε ότι $C_{n,k}=(\genfrac{}{}{0ex}{}{n}{k})$.

Υπάρχουν δύο τρόποι να φτιάξουμε ένα συνδυασμό $n$ στοιχείων $a_1,\dots ,a_n$ ανά $k$:

• Να διαλέξουμε $k-1$ στοιχεία από τα $a_1,\dots ,a_{n-1}$ και το στοιχείο $a_n$ (με συνολικά $C_{n-1,k-1}$ τρόπους).
• Ή να διαλέξουμε $k$ στοιχεία από τα $a_1,\dots ,a_{n-1}$ (με συνολικά $C_{n-1,k}$ τρόπους).

Επομένως, το συνολικό πλήθος συνδυασμών $n$ ανά $k$ ικανοποιούν:

$C_{n,k}=C_{n-1,k}+C_{n-1,k-1}$

και $C_{n,0}=C_{0,k}=1$. Επομένως, τα πλήθη των συνδυασμών ικανοποιούν τον αναδρομικό ορισμό των διωνυμικών συντελεστών και επομένως έχουμε ότι $C_{n,k}=(\genfrac{}{}{0ex}{}{n}{k})$.

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

Παράδειγμα 1ο

Στις γραπτές εξετάσεις οι μαθητές πρέπει από το σύνολο των 9 ερωτήσεων που τους δίνονται να απαντήσουν στις 6. Με πόσους τρόπους μπορεί ένας μαθητής να επιλέξει τις ερωτήσεις στις οποίες θα απαντήσει;

Απάντηση

$(\genfrac{}{}{0ex}{}{9}{6})=\frac{9!}{6!(9-6)!}=\frac{9!}{6!\cdot 3!}=\frac{7\cdot 8\cdot 9}{1\cdot 2\cdot 3}=84$

Παράδειγμα 2ο

Με πόσους τρόπους μπορεί ένας παίχτης από μια τράπουλα με 52 χαρτιά να επιλέξει 5;

Απάντηση

$(\genfrac{}{}{0ex}{}{52}{5})=\frac{52!}{5!(52-5)!}=\frac{52!}{5!\cdot 47!}=\frac{48\cdot 49\cdot 50\cdot 51\cdot 52}{1\cdot 2\cdot 3\cdot 4\cdot 5}=2.598.960$

Παράδειγμα 3ο

Ένα σχολείο έχει $27$ μαθήτριες και $18$ μαθητές. Με πόσους τρόπους μπορούμε να διαλέξουμε ένα 15μελές με 9 μαθήτριες και 6 μαθητές;

Απάντηση

$(\genfrac{}{}{0ex}{}{27}{9})\cdot (\genfrac{}{}{0ex}{}{18}{6})=87.006.219.300$

Δείτε επίσης

• Διωνυμικός συντελεστής
• Διάταξη
• Διάταξη με επανάληψη
• Μετάθεση (μαθηματικά)