Kombinatoryka: Kluczowe Wzory i Przykłady

Wprowadzenie do kombinatoryki

Kombinatoryka to dział matematyki zajmujący się liczeniem różnych układów, jakie można utworzyć z elementów skończonego zbioru. Stanowi ona fundament wielu dziedzin matematyki, informatyki, a także znajduje zastosowanie w genetyce, kryptografii czy statystyce. W tym artykule poznamy kluczowe wzory kombinatoryczne oraz nauczymy się rozwiązywać typowe zadania.

Zanim przejdziemy do szczegółów, warto zrozumieć, czym kombinatoryka różni się od prawdopodobieństwa. Choć te dziedziny są ze sobą ściśle powiązane, kombinatoryka skupia się na liczeniu możliwych układów elementów, natomiast prawdopodobieństwo określa szansę wystąpienia konkretnego zdarzenia. Innymi słowy, kombinatoryka dostarcza narzędzi do obliczania liczby możliwych wyników, które następnie wykorzystujemy w rachunku prawdopodobieństwa.

Reguła mnożenia i reguła dodawania

Zacznijmy od dwóch podstawowych zasad kombinatorycznych, które stanowią fundament tej dziedziny.

Reguła mnożenia

Jeśli pewną czynność można wykonać na \(n\) sposobów, a po niej inną czynność na \(m\) sposobów, to obie czynności można wykonać w określonej kolejności na \(n \cdot m\) sposobów.

Przykład 1: Mamy 3 koszulki (czerwoną, niebieską i zieloną) oraz 2 pary spodni (czarne i brązowe). Na ile sposobów możemy wybrać strój składający się z koszulki i spodni?

Rozwiązanie: Koszulkę możemy wybrać na 3 sposoby, a spodnie na 2 sposoby. Zgodnie z regułą mnożenia, liczbę możliwych strojów obliczamy jako \(3 \cdot 2 = 6\).

Możliwe stroje to:

• czerwona koszulka + czarne spodnie
• czerwona koszulka + brązowe spodnie
• niebieska koszulka + czarne spodnie
• niebieska koszulka + brązowe spodnie
• zielona koszulka + czarne spodnie
• zielona koszulka + brązowe spodnie

Reguła dodawania

Jeśli pewną czynność można wykonać na \(n\) sposobów, a inną, wykluczającą się z pierwszą, na \(m\) sposobów, to jedną LUB drugą czynność można wykonać na \(n + m\) sposobów.

Przykład 2: W szafie mamy 4 swetry i 3 bluzy. Na ile sposobów możemy wybrać jeden element garderoby (sweter LUB bluzę)?

Rozwiązanie: Sweter możemy wybrać na 4 sposoby, a bluzę na 3 sposoby. Ponieważ wybieramy albo sweter, albo bluzę (nie oba naraz), stosujemy regułę dodawania: \(4 + 3 = 7\) sposobów.

Silnia i symbol Newtona

Zanim przejdziemy do głównych wzorów kombinatorycznych, warto przypomnieć definicję silni, która jest kluczowym elementem wielu wzorów.

Silnia

Silnia liczby naturalnej \(n\), oznaczana jako \(n!\), to iloczyn wszystkich liczb naturalnych od 1 do \(n\):

\[n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n\]

Dodatkowo przyjmujemy, że \(0! = 1\).

Kilka przykładowych wartości silni:

• \(0! = 1\)
• \(1! = 1\)
• \(2! = 1 \cdot 2 = 2\)
• \(3! = 1 \cdot 2 \cdot 3 = 6\)
• \(4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24\)
• \(5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120\)

Symbol Newtona

Symbol Newtona, znany również jako współczynnik dwumianowy, oznaczany jest jako \(\binom{n}{k}\) i definiowany wzorem:

\[\binom{n}{k} = \frac{n!}{k!(n-k)!}\]

gdzie \(n\) i \(k\) są liczbami naturalnymi oraz \(k \leq n\).

Symbol Newtona odczytujemy jako „\(n\) po \(k\)” i reprezentuje liczbę sposobów wyboru \(k\) elementów z \(n\)-elementowego zbioru bez uwzględniania kolejności.

Podstawowe operacje kombinatoryczne

W kombinatoryce wyróżniamy trzy podstawowe operacje: permutacje, wariacje i kombinacje. Każda z nich występuje w dwóch wariantach: bez powtórzeń i z powtórzeniami.

Permutacje

Permutacja to ustawienie wszystkich elementów zbioru w określonej kolejności.

Permutacje bez powtórzeń

Liczba permutacji zbioru \(n\)-elementowego bez powtórzeń wynosi:

\[P(n) = n!\]

Przykład 3: Na ile sposobów można ustawić 5 różnych książek na półce?

Rozwiązanie: Jest to permutacja 5 elementów, więc liczba możliwości wynosi \(P(5) = 5! = 120\).

Permutacje z powtórzeniami

Jeśli w zbiorze \(n\)-elementowym pewne elementy się powtarzają (np. \(n_1\) elementów pierwszego rodzaju, \(n_2\) elementów drugiego rodzaju, itd.), to liczba permutacji wynosi:

\[P(n; n_1, n_2, \ldots, n_k) = \frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}\]

gdzie \(n = n_1 + n_2 + \ldots + n_k\).

Przykład 4: Ile różnych słów (niekoniecznie sensownych) można utworzyć z liter słowa „MATEMATYKA”?

Rozwiązanie: Słowo „MATEMATYKA” składa się z 10 liter, w tym:

• litera M występuje 2 razy
• litera A występuje 3 razy
• litera T występuje 2 razy
• pozostałe litery (E, Y, K) występują po 1 razie

Stosujemy wzór na permutacje z powtórzeniami:

\[P(10; 2, 3, 2, 1, 1, 1) = \frac{10!}{2! \cdot 3! \cdot 2! \cdot 1! \cdot 1! \cdot 1!} = \frac{3\,628\,800}{2 \cdot 6 \cdot 2 \cdot 1 \cdot 1 \cdot 1} = \frac{3\,628\,800}{24} = 151\,200\]

Wariacje

Wariacja to wybór \(k\) elementów z \(n\)-elementowego zbioru z uwzględnieniem ich kolejności.

Wariacje bez powtórzeń

Liczba wariacji \(k\)-elementowych ze zbioru \(n\)-elementowego bez powtórzeń wynosi:

\[V(n, k) = \frac{n!}{(n-k)!} = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)\]

Przykład 5: Z grupy 10 uczniów należy wybrać przewodniczącego, zastępcę i skarbnika. Na ile sposobów można dokonać tego wyboru?

Rozwiązanie: Jest to wariacja 3-elementowa z 10-elementowego zbioru bez powtórzeń:

\[V(10, 3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = \frac{10 \cdot 9 \cdot 8 \cdot 7!}{7!} = 10 \cdot 9 \cdot 8 = 720\]

Wariacje z powtórzeniami

Liczba wariacji \(k\)-elementowych ze zbioru \(n\)-elementowego z powtórzeniami wynosi:

\[V'(n, k) = n^k\]

Przykład 6: Ile można utworzyć kodów 4-cyfrowych, jeśli można używać cyfr od 0 do 9?

Rozwiązanie: Jest to wariacja 4-elementowa z 10-elementowego zbioru z powtórzeniami:

\[V'(10, 4) = 10^4 = 10\,000\]

Kombinacje

Kombinacja to wybór \(k\) elementów z \(n\)-elementowego zbioru bez uwzględniania ich kolejności.

Kombinacje bez powtórzeń

Liczba kombinacji \(k\)-elementowych ze zbioru \(n\)-elementowego bez powtórzeń wynosi:

\[C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}\]

Przykład 7: W klasie jest 20 uczniów. Na ile sposobów można wybrać 3-osobową delegację?

Rozwiązanie: Jest to kombinacja 3-elementowa z 20-elementowego zbioru bez powtórzeń:

\[C(20, 3) = \binom{20}{3} = \frac{20!}{3!(20-3)!} = \frac{20!}{3!17!} = \frac{20 \cdot 19 \cdot 18 \cdot 17!}{3 \cdot 2 \cdot 1 \cdot 17!} = \frac{20 \cdot 19 \cdot 18}{6} = \frac{6840}{6} = 1140\]

Kombinacje z powtórzeniami

Liczba kombinacji \(k\)-elementowych ze zbioru \(n\)-elementowego z powtórzeniami wynosi:

\[C'(n, k) = \binom{n+k-1}{k} = \frac{(n+k-1)!}{k!(n-1)!}\]

Przykład 8: W lodziarni są 4 smaki lodów. Na ile sposobów można wybrać 3 gałki lodów (smaki mogą się powtarzać)?

Rozwiązanie: Jest to kombinacja 3-elementowa z 4-elementowego zbioru z powtórzeniami:

\[C'(4, 3) = \binom{4+3-1}{3} = \binom{6}{3} = \frac{6!}{3!3!} = \frac{6 \cdot 5 \cdot 4 \cdot 3!}{3! \cdot 3 \cdot 2 \cdot 1} = \frac{120}{6} = 20\]

Jak rozpoznać, którego wzoru użyć?

Wybór odpowiedniego wzoru kombinatorycznego może początkowo sprawiać trudności. Oto kilka wskazówek, które pomogą w podjęciu decyzji:

1. Czy liczy się kolejność elementów?
   • Tak → wariacja lub permutacja
   • Nie → kombinacja
2. Czy wybieramy wszystkie elementy?
   • Tak → permutacja
   • Nie → wariacja lub kombinacja
3. Czy elementy mogą się powtarzać?
   • Tak → operacja z powtórzeniami
   • Nie → operacja bez powtórzeń

Poniższa tabela podsumowuje wszystkie wzory:

Operacja	Bez powtórzeń	Z powtórzeniami
Permutacje (wszystkie elementy, liczy się kolejność)	\(P(n) = n!\)	\(P(n; n_1, n_2, \ldots, n_k) = \frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}\)
Wariacje (k z n elementów, liczy się kolejność)	\(V(n, k) = \frac{n!}{(n-k)!}\)	\(V'(n, k) = n^k\)
Kombinacje (k z n elementów, nie liczy się kolejność)	\(C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}\)	\(C'(n, k) = \binom{n+k-1}{k} = \frac{(n+k-1)!}{k!(n-1)!}\)

Rozwiązywanie złożonych zadań kombinatorycznych

W praktyce często spotykamy się z zadaniami, które wymagają zastosowania kilku wzorów kombinatorycznych jednocześnie lub podzielenia problemu na mniejsze części.

Przykład 9: Z grupy 8 kobiet i 7 mężczyzn wybieramy 5-osobową komisję, w której muszą być co najmniej 2 kobiety. Ile jest możliwości utworzenia takiej komisji?

Rozwiązanie: Podzielmy problem na przypadki w zależności od liczby kobiet w komisji:

• 2 kobiety i 3 mężczyzn: \(\binom{8}{2} \cdot \binom{7}{3} = 28 \cdot 35 = 980\) możliwości
• 3 kobiety i 2 mężczyzn: \(\binom{8}{3} \cdot \binom{7}{2} = 56 \cdot 21 = 1176\) możliwości
• 4 kobiety i 1 mężczyzna: \(\binom{8}{4} \cdot \binom{7}{1} = 70 \cdot 7 = 490\) możliwości
• 5 kobiet i 0 mężczyzn: \(\binom{8}{5} \cdot \binom{7}{0} = 56 \cdot 1 = 56\) możliwości

Łącznie: \(980 + 1176 + 490 + 56 = 2702\) możliwości.

Przykład 10: Ile jest słów 6-literowych (niekoniecznie sensownych) utworzonych z liter słowa „KOMBINATORYKA”, w których nie występują litery powtórzone?

Rozwiązanie: Słowo „KOMBINATORYKA” składa się z 13 liter, w tym niektóre się powtarzają. Najpierw znajdźmy zbiór różnych liter: K, O, M, B, I, N, A, T, R, Y, K, A – po usunięciu powtórzeń zostaje 11 różnych liter.

Mamy więc wybrać 6 liter spośród 11 różnych i ustawić je w określonej kolejności. Jest to wariacja 6-elementowa z 11-elementowego zbioru bez powtórzeń:

\[V(11, 6) = \frac{11!}{(11-6)!} = \frac{11!}{5!} = 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 = 332\,640\]

Własności symbolu Newtona

Symbol Newtona ma kilka ważnych własności, które mogą być przydatne przy rozwiązywaniu zadań kombinatorycznych:

1. \(\binom{n}{0} = \binom{n}{n} = 1\)
2. \(\binom{n}{k} = \binom{n}{n-k}\)
3. \(\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}\)
4. \(\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n} = 2^n\)

Przykład 11: Oblicz \(\binom{10}{7}\) korzystając z własności symbolu Newtona.

Rozwiązanie: Korzystając z własności \(\binom{n}{k} = \binom{n}{n-k}\), mamy:

\[\binom{10}{7} = \binom{10}{10-7} = \binom{10}{3} = \frac{10!}{3!(10-3)!} = \frac{10!}{3!7!} = \frac{10 \cdot 9 \cdot 8 \cdot 7!}{3 \cdot 2 \cdot 1 \cdot 7!} = \frac{720}{6} = 120\]

Zastosowania kombinatoryki

Kombinatoryka znajduje zastosowanie w wielu dziedzinach, takich jak:

1. Teoria prawdopodobieństwa – obliczanie liczby sprzyjających zdarzeń i wszystkich możliwych wyników
2. Informatyka – analiza algorytmów, struktury danych, kompresja
3. Kryptografia – projektowanie i analiza systemów szyfrowania
4. Genetyka – analiza sekwencji DNA, badanie mutacji
5. Statystyka – projektowanie eksperymentów, analiza danych

Przykład 12: W loterii losuje się 6 liczb z 49. Jakie jest prawdopodobieństwo trafienia „szóstki”?

Rozwiązanie: Liczba wszystkich możliwych wyników to liczba kombinacji 6-elementowych z 49-elementowego zbioru bez powtórzeń:

\[\binom{49}{6} = \frac{49!}{6!(49-6)!} = \frac{49!}{6!43!} \approx 13\,983\,816\]

Liczba sprzyjających zdarzeń to 1 (tylko jeden układ sześciu liczb jest wygrywający).

Prawdopodobieństwo trafienia „szóstki” wynosi więc:

\[P = \frac{1}{\binom{49}{6}} \approx \frac{1}{13\,983\,816} \approx 0.0000000715\]

co oznacza około 1 szansy na 14 milionów.

Narzędzia obliczeniowe

Przy rozwiązywaniu zadań kombinatorycznych często przydatne są narzędzia obliczeniowe, które pozwalają na szybkie obliczenie wartości silni czy symbolu Newtona. Poniżej przedstawiamy prosty kalkulator kombinatoryczny w JavaScript:

Podsumowanie

Kombinatoryka stanowi ważny dział matematyki, który dostarcza narzędzi do rozwiązywania problemów związanych z liczeniem różnych układów elementów. Znajomość podstawowych wzorów i technik kombinatorycznych jest niezbędna w wielu dziedzinach nauki i techniki.

Najważniejsze wzory kombinatoryczne to:

• Permutacje bez powtórzeń: \(P(n) = n!\)
• Permutacje z powtórzeniami: \(P(n; n_1, n_2, \ldots, n_k) = \frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}\)
• Wariacje bez powtórzeń: \(V(n, k) = \frac{n!}{(n-k)!}\)
• Wariacje z powtórzeniami: \(V'(n, k) = n^k\)
• Kombinacje bez powtórzeń: \(C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}\)
• Kombinacje z powtórzeniami: \(C'(n, k) = \binom{n+k-1}{k} = \frac{(n+k-1)!}{k!(n-1)!}\)

Przy rozwiązywaniu zadań kombinatorycznych warto zastanowić się, czy liczy się kolejność elementów oraz czy elementy mogą się powtarzać, co pozwoli na wybór odpowiedniego wzoru.