Kombinatoryka - Wszystko o Permutacjach, Wariacjach i Kombinacjach

Podstawowe rodzaje układów w kombinatoryce

Kombinatoryka zajmuje się różnymi sposobami wyboru i uporządkowania elementów. Pierwszym ważnym typem są permutacje - określają liczbę sposobów, na jakie możemy poukładać wszystkie elementy n-elementowego zbioru, gdy elementy nie mogą się powtarzać, a kolejność ma znaczenie.

Kolejnym typem są wariacje bez powtórzeń - dotyczą sytuacji, gdy wybieramy k elementów z n-elementowego zbioru (gdzie n ≥ k). Tutaj również elementy nie mogą się powtarzać, a kolejność ma znaczenie, ale w przeciwieństwie do permutacji nie wykorzystujemy wszystkich elementów.

Wariacje z powtórzeniami to układy, w których elementy mogą się powtarzać, kolejność ma znaczenie, ale nie wykorzystujemy wszystkich elementów ze zbioru. Ten typ układów jest szczególnie przydatny w zadaniach, gdzie ten sam element może wystąpić wielokrotnie.

💡 Kluczem do rozwiązywania zadań kombinatorycznych jest określenie, czy elementy mogą się powtarzać i czy kolejność ma znaczenie!

Kombinacje i ich właściwości

Kombinacje to podzbiory k-elementowe wybrane z n-elementowego zbioru. W kombinacjach elementy nie mogą się powtarzać, a kolejność nie ma znaczenia. Zapisujemy je jako $C_n^k$ lub ${n \choose k}$, gdzie zawsze n > k.

Wzór na liczbę kombinacji to: ${n \choose k} = \frac{n!}{k! \cdot (n-k)!}$. Zapamiętaj kilka szczególnych przypadków: ${n \choose 1}=n$ (wybieramy 1 element z n), ${n \choose 0}=1$ (pusty zbiór), ${n \choose n}=1$ (cały zbiór).

Kombinacje mają ciekawe właściwości, które przyspieszają obliczenia. Na przykład ${n \choose k}={n \choose n-k}$, co oznacza, że wybór k elementów z n jest równoważny wyborowi n-k elementów. Również warto pamiętać o wzorze ${n \choose k}+{n \choose k+1}={n+1 \choose k+1}$.

🔍 Różnica między wariację a kombinacją: w wariacji liczy się kolejność elementów, w kombinacji - tylko sam wybór elementów!

Zastosowanie kombinatoryki w loterii LOTTO

Ile kuponów LOTTO trzeba kupić, aby mieć pewność wygranej? Musimy wybrać 6 liczb z 49 możliwych. Ponieważ w LOTTO nie liczy się kolejność wybranych liczb, używamy kombinacji.

Możemy rozwiązać to zadanie na dwa sposoby. W pierwszym obliczamy liczbę wszystkich możliwych układów 6 liczb z 49 możliwych, a następnie dzielimy przez 6!, ponieważ kolejność nie ma znaczenia (nie interesują nas powtórzenia tego samego zestawu liczb w innej kolejności).

W drugim sposobie stosujemy bezpośrednio wzór na kombinacje: $C_{49}^6 = {49 \choose 6} = \frac{49!}{6! \cdot 43!}$. Po rozwinięciu i uproszczeniu otrzymujemy około 14 milionów możliwości.

🎲 Dlaczego dzielimy przez permutacje? Aby nie uwzględniać tych samych zestawów liczb zapisanych w różnej kolejności - w LOTTO liczy się tylko to, które liczby wybrałeś, nie w jakiej kolejności!

Zadanie: liczby 6-cyfrowe z określonymi cyframi

Spróbujmy obliczyć, ile jest liczb 6-cyfrowych, w których występują dokładnie trzy cyfy 2 i dwie cyfry 5. Oznacza to, że jedna pozycja zostaje na inną cyfrę, która nie może być ani 2, ani 5.

Najpierw musimy zdecydować, na których pozycjach umieścimy cyfry 2, 5 i tę jedną pozostałą cyfrę. Mamy 6 miejsc, z których wybieramy 3 miejsca dla cyfry 2, 2 miejsca dla cyfry 5, i 1 miejsce dla innej cyfry.

Używamy wzoru na kombinacje: ${6 \choose 3} \cdot {3 \choose 2} \cdot 8$. Gdzie ${6 \choose 3}$ to liczba sposobów wyboru 3 miejsc dla cyfry 2, ${3 \choose 2}$ to liczba sposobów wyboru 2 miejsc dla cyfry 5 z pozostałych 3 miejsc, a 8 to liczba możliwych cyfr na ostatnie miejsce $0-9 bez 2 i 5$.

Po obliczeniu otrzymujemy wynik: 420 różnych liczb 6-cyfrowych spełniających warunki zadania.

📊 Kluczem do rozwiązania jest zauważenie, że mamy do czynienia z rozmieszeniem określonej liczby cyfr, a potem obliczenie liczby możliwych kombinacji!

Zastosowanie kombinacji w tworzeniu drużyn

Zastanówmy się, na ile sposobów można utworzyć 6-osobową drużynę z grupy 10 osób. Ponieważ kolejność osób w drużynie nie ma znaczenia, używamy kombinacji:

$C_{10}^6 = {10 \choose 6} = \frac{10!}{6! \cdot 4!} = 210$ sposobów

A co jeśli chcemy utworzyć dwie 5-osobowe drużyny z 10-osobowej grupy? To ciekawsze zadanie, bo po wybraniu pierwszej drużyny, druga jest już automatycznie ustalona. Moglibyśmy policzyć: ${10 \choose 5} \cdot {5 \choose 5} = 252$, ale to nie jest poprawny wynik!

Problem polega na tym, że nie rozróżniamy drużyn (np. drużyna A i drużyna B składające się z tych samych osób są traktowane jako to samo przyporządkowanie). Dlatego musimy podzielić wynik przez 2, bo każdy układ drużyn policzyliśmy dwukrotnie. Poprawny wynik to:

$\frac{{10 \choose 5} \cdot {5 \choose 5}}{2} = \frac{252}{2} = 126$ sposobów

⚽ Uwaga! Gdy tworzysz dwie drużyny i nie ma znaczenia, która jest "pierwsza" a która "druga", musisz uwzględnić to w obliczeniach, dzieląc wynik przez liczbę możliwych permutacji tych drużyn!