Podstawy kombinatoryki: definicje, wzory i przykłady

Reguła mnożenia

Reguła mnożenia mówi, że jeśli wybór przebiega w dwóch etapach, gdzie w pierwszym mamy $k_1$ możliwości, a w drugim $k_2$ możliwości, to wszystkich możliwych wyborów jest $k_1 \cdot k_2$. Zasada ta jest podstawą wielu zagadnień kombinatorycznych.

Wyobraź sobie, że tworzysz liczby dwucyfrowe. Jeśli cyfra dziesiątek może być wybrana ze zbioru {1, 2, 3, 4}, a cyfra jedności ze zbioru {6, 7, 8, 9}, to masz $4 \cdot 4 = 16$ różnych liczb do utworzenia. Możesz to sobie wyobrazić jako drzewo możliwości.

Podobnie, jeśli tworzysz liczby dwucyfrowe z cyfr zbioru {1, 2, 3, 4, 5} i cyfry mogą się powtarzać, masz $5 \cdot 5 = 25$ możliwości. Każdą cyfrę dziesiątek możesz połączyć z każdą cyfrą jedności.

Wskazówka: Zawsze rysuj drzewo możliwości dla skomplikowanych problemów - to pomoże Ci zobaczyć wszystkie opcje i nie popełnić błędu w obliczeniach.

Permutacje i wariacje

Permutacja to uporządkowany układ wszystkich elementów danego zbioru. Liczbę permutacji n-elementowego zbioru obliczamy ze wzoru: $P = n!$ (czyli $n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 1$). Pamiętaj, że $0! = 1$ i $1! = 1$.

Kombinacja to wybór k elementów z n-elementowego zbioru bez względu na kolejność. Obliczamy ją wzorem: $C = \binom{n}{k} = \frac{n!}{k!(n-k)!}$. W kombinacji nie ma znaczenia, w jakiej kolejności wybieramy elementy.

Wariacje to uporządkowane układy k-elementowe wybrane z n elementów. Rozróżniamy wariacje bez powtórzeń: $V = \frac{n!}{(n-k)!}$ oraz wariacje z powtórzeniami: $V = n^k$.

Kluczowa różnica: w permutacji i wariacji kolejność elementów ma znaczenie, natomiast w kombinacji nie jest ważna. To rozróżnienie pomoże Ci dobrać właściwy wzór do zadania.

Zapamiętaj: Permutacja = wszystkie elementy w określonej kolejności, Kombinacja = wybór bez znaczenia kolejności, Wariacja = wybór z uwzględnieniem kolejności.