Kombinacje

Zbiór k-elementowych podzbiorów zbioru n-elementowego. Liczba jego elementów, czyli liczba k-elementowych podzbiorów zbioru n-elementowego (zwanych kombinacjami n po k) oznaczana jest symbolem C_n^k i wyraża się wzorem:

C_n^k = $$\binom{n}{k}$$ = $${\frac{{n!}}{{k! (n-k)!}}}$$ = $${\frac{{n (n-1) \ldots (n-k+1)}}{{k!}}}$$

W szczególności dla k > n liczba kombinacji C_n^k jest równa 0. Ważne jest, że zliczamy podzbiory, czyli kolejność elementów w zliczanych obiektach jest nieistotna. Rzeczywiście, jeśli n = 0 lub n = 1 to łatwo sprawdzić, ze liczby: $\binom{0}{0}$ = 1, $\binom{1}{0}$ = 1 i $\binom{1}{1}$ = 1 są równe liczbom C₀⁰ pustych podzbiorów zbioru pustego, C₁⁰ pustych podzbiorów zbioru jednoelementowego i C₁¹ jednoelementowych podzbiorów zbioru jednoelementowego. Załóżmy, ze wzór na liczbę kombinacji jest słuszny dla pewnej liczby n i wszystkich k $\in$ {0, 1,..., n}. Policzymy podzbiory k-elementowe zbioru, mającego n + 1 elementów. Wyróżnijmy w tym zbiorze jeden element - nazwijmy go (n + 1)-szym elementem. Pozostałe elementy tworzą zbiór n-elementowy. Zbiór wszystkich k-elementowych podzbiorów można teraz podzielić na dwa rozłączne podzbiory:

• pierwszy składa się z tych podzbiorów k-elementowych, do których (n + 1)-szy element nie należy; są więc one k-elementowymi podzbiorami zbioru n-elementowego i jest ich $\binom{n}{k}$
• drugi składa się z tych podzbiorów k-elementowych, do których (n + 1)-szy element należy; każdy z nich powstaje z jednoznacznie określonego (k - 1)-elementowego podzbioru zbioru n-elementowego przez dołączenie (n + 1)-szego elementu; zatem takich podzbiorów jest tyle, co (k - 1)-elementowych podzbiorów zbioru n-elementowego - jest ich $\binom{n}{k-1}$

Łącznie zbiór kombinacji n + 1 po k ma

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

elementów. Na zasadzie indukcji matematycznej wzór na liczbę kombinacji jest prawdziwy dla każdej liczby naturalnej n.