Def.: Kombinacją \(k\)-elementową zbioru \(n\)-elementowego nazywamy każdy \(k\)-elementowy podzbiór tego zbioru.
Przypomnijmy, że ilość elementów zbioru (moc zbioru) dotyczy jedynie różnych elementów tego zbioru, to znaczy zbiór \(\left \{ 1,1,1 \right \}\) traktujemy tak samo jak zbiór \(\left \{ 1 \right \}\).
Twierdzenie: Ilość kombinacji \(k\)-elementowych zbioru \(n\)-elementowego równa jest \({n \choose k}\), tzn.
\(C_n^k = \frac{n!}{k!(n-k)!}\)
Przykład:
Dla zbioru \(\left \{ 1,2,3,4 \right \}\) przykładowymi trzyelementowymi kombinacjami są \(\left \{ 1,2,3 \right \}\), \(\left \{ 2,3,4 \right \}\) lub \(\left \{ 1,3,4 \right \}\).
Ilość takich kombinacji jest równa \(\frac {4!}{3!(4-3)!}=\frac{4!}{3!\cdot1}=4\).
Wypiszmy więc dla porządku ostatnią z nich: \(\left \{ 1,2,4 \right \}\).
W praktyce liczenie kombinacji sprowadza się do operowania symbolem Newtona. Można także posłużyć się trójkątem Pascala i odczytać wynik z odpowiedniego wiersza.
Zadania:
Ile jest wszystkich kombinacji zbioru \(\left \{ 1,2,3,4,5,6 \right \}\)?
Odpowiedzi:
\(63\).