Podstawy kombinatoryki

Kombinatoryka pomaga odpowiedzieć na pytanie: "Na ile sposobów mogę to zrobić?". Wszystko zależy od dwóch kluczowych pytań: czy ważna jest kolejność elementów oraz czy elementy mogą się powtarzać?

Gdy wybierasz elementy bez zwracania uwagi na ich kolejność, masz do czynienia z kombinacjami. Przykładowo, wybór 3 owoców z koszyka 10 różnych owoców to kombinacja. Nie ma znaczenia, czy najpierw weźmiesz jabłko, czy banan.

Jeśli kolejność jest istotna, mówisz o wariacjach (np. kod PIN) lub permutacjach (gdy używasz wszystkich elementów, np. ustawianie książek na półce).

Wskazówka: Żeby łatwo zapamiętać różnicę, pomyśl: kombinacje to jak zakupy (ważne co wybierasz, nieważna kolejność), wariacje to jak kod PIN (ważne co i w jakiej kolejności), a permutacje to jak ustawianie wszystkich książek na półce (używasz wszystkich elementów).

Wzory w kombinatoryce

Kombinacje bez powtórzeń to wybór k elementów z n-elementowego zbioru, bez znaczenia kolejności. Wzór to: $C^k_n = \frac{n!}{k!(n-k)!}$

Kombinacje z powtórzeniami pozwalają na wielokrotny wybór tego samego elementu. Wzór: $C^k_n = \frac{(n+k-1)!}{k!(n-1)!}$

Wariacje bez powtórzeń to uporządkowane ciągi k elementów wybranych z n-elementowego zbioru. Wzór: $V^k_n = \frac{n!}{(n-k)!}$

Wariacje z powtórzeniami pozwalają na wielokrotne użycie tych samych elementów. Wzór: $W^k_n = n^k$

Permutacje bez powtórzeń to wszystkie możliwe uporządkowania n elementów. Wzór: $P_n = n!$

Permutacje z powtórzeniami to uporządkowania, gdy niektóre elementy się powtarzają. Wzór: $P'^k_n = \frac{n!}{n_1!n_2!...n_k!}$, gdzie n₁, n₂, ... to liczby powtórzeń elementów.