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

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

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

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

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

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

${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}={\frac {n\cdot (n-1)\cdot \ldots \cdot 2\cdot 1}{(k\cdot (k-1)\cdot \ldots \cdot 1)\cdot ((n-k)\cdot (n-k-1)\cdot \ldots \cdot 1)}}$,

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

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

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

• Οι συνδυασμοί $3$ ανά $1$ είναι ${\tbinom {3}{1}}={\tfrac {3!}{1!\cdot 2!}}=3$: $\{{\color {red}\alpha }\}$, $\{{\color {green}\beta }\}$, $\{{\color {blue}\gamma }\}$.
• Οι συνδυασμοί $3$ ανά $2$ είναι ${\tbinom {3}{2}}={\tfrac {3!}{2!\cdot 1!}}=3$: $\{{\color {red}\alpha },{\color {green}\beta }\}$, $\{{\color {green}\beta },{\color {blue}\gamma }\}$, $\{{\color {red}\alpha },{\color {blue}\gamma }\}$.
• Οι συνδυασμοί $3$ ανά $3$ είναι ${\tbinom {3}{3}}={\tfrac {3!}{3!\cdot 0!}}=1$: $\{{\color {red}\alpha },{\color {green}\beta },{\color {blue}\gamma }\}$.

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

• Οι συνδυασμοί $4$ ανά $1$ είναι ${\tbinom {4}{1}}={\tfrac {4!}{1!\cdot 3!}}=4$: $\{{\color {red}\alpha }\}$, $\{{\color {green}\beta }\}$, $\{{\color {blue}\gamma }\}$, $\{{\color {orange}\delta }\}$.
• Οι συνδυασμοί $4$ ανά $2$ είναι ${\tbinom {4}{2}}={\tfrac {4!}{2!\cdot 2!}}=6$: $\{{\color {red}\alpha },{\color {green}\beta }\}$, $\{{\color {green}\beta },{\color {blue}\gamma }\}$, $\{{\color {red}\alpha },{\color {blue}\gamma }\}$, $\{{\color {red}\alpha },{\color {orange}\delta }\}$, $\{{\color {red}\beta }.{\color {orange}\delta }\}$, $\{{\color {orange}\delta },{\color {blue}\gamma }\}$.
• Οι συνδυασμοί $4$ ανά $3$ είναι ${\tbinom {4}{3}}={\tfrac {4!}{3!\cdot 1!}}=4$: $\{{\color {green}\beta },{\color {blue}\gamma },{\color {orange}\delta }\}$, $\{{\color {red}\alpha },{\color {blue}\gamma },{\color {orange}\delta }\}$, $\{{\color {red}\alpha },{\color {green}\beta },{\color {orange}\delta }\}$, $\{{\color {red}\alpha },{\color {green}\beta },{\color {blue}\gamma }\}$.
• Οι συνδυασμοί $4$ ανά $4$ είναι ${\tbinom {4}{4}}={\tfrac {4!}{4!\cdot 0!}}=1$: $\{{\color {red}\alpha },{\color {green}\beta },{\color {blue}\gamma },{\color {orange}\delta }\}$.

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

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

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

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

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

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

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

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

συνδυασμοί.

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

$\{{\color {green}\beta },{\color {blue}\gamma },{\color {orange}\delta }\}$	$\{{\color {red}\alpha },{\color {blue}\gamma },{\color {orange}\delta }\}$	$\{{\color {red}\alpha },{\color {green}\beta },{\color {orange}\delta }\}$	$\{{\color {red}\alpha },{\color {green}\beta },{\color {blue}\gamma }\}$
$({\color {green}\beta },{\color {blue}\gamma },{\color {orange}\delta })$	$({\color {red}\alpha },{\color {blue}\gamma },{\color {orange}\delta })$	$({\color {red}\alpha },{\color {green}\beta },{\color {orange}\delta })$	$({\color {red}\alpha },{\color {green}\beta },{\color {blue}\gamma })$
$({\color {green}\beta },{\color {orange}\delta },{\color {blue}\gamma })$	$({\color {red}\alpha },{\color {orange}\delta },{\color {blue}\gamma })$	$({\color {red}\alpha },{\color {orange}\delta },{\color {green}\beta })$	$({\color {red}\alpha },{\color {blue}\gamma },{\color {green}\beta })$
$({\color {blue}\gamma },{\color {green}\beta },{\color {orange}\delta })$	$({\color {blue}\gamma },{\color {red}\alpha },{\color {orange}\delta })$	$({\color {green}\beta },{\color {red}\alpha },{\color {orange}\delta })$	$({\color {green}\beta },{\color {red}\alpha },{\color {blue}\gamma })$
$({\color {blue}\gamma },{\color {orange}\delta },{\color {green}\beta })$	$({\color {blue}\gamma },{\color {orange}\delta },{\color {red}\alpha })$	$({\color {green}\beta },{\color {orange}\delta },{\color {red}\alpha })$	$({\color {green}\beta },{\color {blue}\gamma },{\color {red}\alpha })$
$({\color {orange}\delta },{\color {green}\beta },{\color {blue}\gamma })$	$({\color {orange}\delta },{\color {red}\alpha },{\color {blue}\gamma })$	$({\color {orange}\delta },{\color {red}\alpha },{\color {green}\beta })$	$({\color {blue}\gamma },{\color {red}\alpha },{\color {green}\beta })$
$({\color {orange}\delta },{\color {blue}\gamma },{\color {green}\beta })$	$({\color {orange}\delta },{\color {blue}\gamma },{\color {red}\alpha })$	$({\color {orange}\delta },{\color {red}\alpha },{\color {green}\beta })$	$({\color {blue}\gamma },{\color {green}\beta },{\color {red}\alpha })$

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

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

Υπάρχουν δύο τρόποι να φτιάξουμε ένα συνδυασμό $n$ στοιχείων $a_{1},\ldots ,a_{n}$ ανά $k$:

• Να διαλέξουμε $k-1$ στοιχεία από τα $a_{1},\ldots ,a_{n-1}$ και το στοιχείο $a_{n}$ (με συνολικά $C_{n-1,k-1}$ τρόπους).
• Ή να διαλέξουμε $k$ στοιχεία από τα $a_{1},\ldots ,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}={\tbinom {n}{k}}$.

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

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

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

Απάντηση

${9 \choose 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;

Απάντηση

${52 \choose 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 μαθητές;

Απάντηση

${\binom {27}{9}}\cdot {\binom {18}{6}}=87.006.219.300$

Υπολογισμός

Λεξικογραφική κατασκευή

Λεξικογραφικοί συνδυασμοί (5 ανά 3)
${\texttt {[1,2,3]}}$
${\texttt {[1,2,4]}}$
${\texttt {[1,2,5]}}$
${\texttt {[1,3,4]}}$
${\texttt {[1,3,5]}}$
${\texttt {[1,4,5]}}$
${\texttt {[2,3,4]}}$
${\texttt {[2,3,5]}}$
${\texttt {[2,4,5]}}$
${\texttt {[3,4,5]}}$

def next_combination(a, k, n):
  # Βρίσκουμε το μεγαλύτερο suffix ίσο με 
  # .., n-2, n-1, n]
  j = k
  while j >= 0 and a[j-1] == n - (k - j):
    j -= 1
  # Αν η ακολουθία είναι [n-k+1,n-k+2,...,n]
  # τότε τελειώσαμε.
  if j == 0: 
    return
  # Διαφορετικά αυξάνουμε το προηγούμενο στοιχείο
  j -= 1
  a[j] += 1
  # και βάζουμε τα επόμενα ίσα με a_j+1, a_j+2, ...
  for ell in range(0, k - j):
    a[j + ell] = a[j] + ell

N = 5
K = 3
ls = [x for x in range(1, K + 1)]
for i in range(0, 10):
  print(ls)
  next_combination(ls, K, N)

Δείτε επίσης

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