Permutacje, wariacje, kombinacje

Co się właśnie stało?

O tym, czym liczymy, decydują dwa pytania: czy kolejność ma znaczenie? oraz czy elementy mogą się powtarzać? Zmiana jednego toggla przełącza model i liczbę wyników.

Kombinacje — kolejność nieważna:

Wybieramy podzbiór k elementów spośród n. $\{A,B\}$ i $\{B,A\}$ to ten sam wybór, więc dzielimy przez $k!$ ustawień:

Wariacje — kolejność ważna:

Uporządkowany ciąg k elementów. Bez powtórzeń każdy element bierzemy raz, z powtórzeniami — dowolnie wiele razy:

Permutacje — ustawienie wszystkich n:

Szczególny przypadek wariacji bez powtórzeń dla $k=n$ — porządkujemy wszystkie elementy:

Drzewo decyzyjne — którego modelu użyć?

Kolejność nieważna ⇒ kombinacje $C_n^k$ (bez powt.) lub $C_{n+k-1}^{k}$ (z powt.). Kolejność ważna ⇒ wariacje: $\tfrac{n!}{(n-k)!}$ (bez powt.) lub $n^k$ (z powt.); a gdy bierzemy wszystkie ($k=n$) — permutacje $n!$.

Po co Ci to na maturze:

Zadania kombinatoryczne prawie zawsze sprowadzają się do zadania sobie tych dwóch pytań. Losowanie z urny bez zwracania, w którym kolejność nie gra roli, to kombinacje; kod PIN (kolejność ważna, cyfry mogą się powtarzać) to $10^4$ wariacji z powtórzeniami.

Zapamiętaj: najpierw pytaj o kolejność, potem o powtórzenia. Kolejność nieważna ⇒ kombinacje. To one dwa pytania rozstrzygają cały wybór modelu.