Kombinatoryka - permutacje, wariacje, kombinacje: wzory i przykłady

Kombinatoryka to dział matematyki, który odpowiada na pytanie „na ile sposobów?”: ile jest ustawień, wyborów albo ciągów spełniających dane warunki. Wybór wzoru zależy od dwóch pytań - czy kolejność ma znaczenie i czy elementy mogą się powtarzać:

Reguła mnożenia i reguła dodawania

Reguła mnożenia: jeśli wybór składa się z kolejnych etapów, a w pierwszym jest $m$ możliwości, w drugim $n$ (niezależnie od wyniku pierwszego), to wszystkich wyborów jest $m \cdot n$. Z trzech koszul i czterech par spodni da się ułożyć $3 \cdot 4 = 12$ strojów.

Reguła dodawania: jeśli wybieramy albo z jednej grupy ($m$ możliwości), albo z drugiej, rozłącznej ($n$ możliwości), wyborów jest $m + n$. Gdy grupy się przecinają, trzeba odjąć część wspólną - to zasada włączeń i wyłączeń.

Wszystkie wzory niżej wynikają z reguły mnożenia.

Silnia

Silnia liczby naturalnej $n$ to iloczyn kolejnych liczb od $1$ do $n$: $n! = 1 \cdot 2 \cdot \ldots \cdot n$. Na przykład $5! = 120$. Przyjmuje się $0! = 1$ - tak, by wzory działały też dla zbioru pustego (pusty zbiór da się ustawić na jeden sposób). Silnia rośnie bardzo szybko: $10! = 3\,628\,800$.

Permutacje

Permutacja zbioru $n$-elementowego to ustawienie wszystkich jego elementów w ciąg. Na pierwszym miejscu może stać dowolny z $n$ elementów, na drugim - jeden z pozostałych $n - 1$ i tak dalej:

$P_n = n!$

Przykład. Pięć różnych książek można ustawić na półce na $5! = 120$ sposobów.

Permutacje z powtórzeniami - gdy niektóre elementy są identyczne, dzielimy przez liczbę przestawień, których nie da się rozróżnić: $\frac{n!}{k_1! \cdot k_2! \cdot \ldots}$. Słowo MAMA ma $\frac{4!}{2! \cdot 2!} = 6$ różnych ustawień liter (dwa M i dwa A).

Wariacje bez powtórzeń

Wariacja bez powtórzeń to $k$-wyrazowy ciąg różnych elementów wybranych ze zbioru $n$-elementowego - wybieramy $k$ elementów i kolejność ma znaczenie:

$V_n^k = n \cdot (n-1) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n-k)!}$

Przykład. Na ile sposobów można rozdać złoty, srebrny i brązowy medal wśród $8$ zawodników? Kolejność ma znaczenie (złoto to nie srebro), zawodnik nie dostaje dwóch medali: $V_8^3 = 8 \cdot 7 \cdot 6 = 336$.

Wariacje z powtórzeniami

Wariacja z powtórzeniami to $k$-wyrazowy ciąg, w którym elementy mogą się powtarzać. Na każdym z $k$ miejsc może stać dowolny z $n$ elementów:

$\overline{V}_n^k = n^k$

Przykłady. Czterocyfrowych kodów PIN jest $10^4 = 10\,000$. Rzut trzema kostkami ma $6^3 = 216$ wyników (rozróżniając kostki).

Kombinacje

Kombinacja to $k$-elementowy podzbiór zbioru $n$-elementowego - wybieramy $k$ elementów, a kolejność nie ma znaczenia. Każdy podzbiór odpowiada $k!$ wariacjom (ustawieniom tych samych elementów), więc

$C_n^k = \binom{n}{k} = \frac{V_n^k}{k!} = \frac{n!}{k!\,(n-k)!}.$

Liczbę $\binom{n}{k}$ nazywa się symbolem Newtona (czyt. „$n$ po $k$”).

Przykłady.

• Delegację $3$ osób z klasy liczącej $10$ osób można wybrać na $\binom{10}{3} = 120$ sposobów.
• $10$ osób wita się uściskiem dłoni każdy z każdym: uścisków jest $\binom{10}{2} = 45$.
• W Lotto losuje się $6$ liczb z $49$: możliwych zestawów jest $\binom{49}{6} = 13\,983\,816$, więc szansa na „szóstkę” przy jednym zakładzie to mniej więcej $1$ do $14$ milionów.

Własności symbolu Newtona: $\binom{n}{k} = \binom{n}{n-k}$, $\binom{n}{0} = \binom{n}{n} = 1$ oraz $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ - na tym polega trójkąt Pascala. Więcej: dwumian Newtona.

Kombinacje z powtórzeniami

Gdy wybieramy $k$ elementów z $n$ rodzajów, kolejność nie ma znaczenia, a rodzaje mogą się powtarzać, liczba wyborów to

$\overline{C}_n^k = \binom{n+k-1}{k}.$

Przykład. Trzy gałki lodów z pięciu smaków (smaki mogą się powtarzać, kolejność gałek nie gra roli): $\binom{5+3-1}{3} = \binom{7}{3} = 35$ możliwości.

Kombinatoryka a prawdopodobieństwo

W klasycznej definicji prawdopodobieństwa $P(A) = \frac{|A|}{|\Omega|}$ obie liczby liczy się właśnie metodami kombinatoryki. Przykłady zastosowań: rachunek prawdopodobieństwa, paradoks urodzin i zasada szufladkowa Dirichleta.

Najczęstsze pytania

Czym różni się wariacja od kombinacji? W wariacji kolejność ma znaczenie (ciąg), w kombinacji - nie (podzbiór). Wybór prezesa, zastępcy i skarbnika z $10$ osób to wariacja ($720$ sposobów), wybór trzyosobowego zarządu bez funkcji - kombinacja ($120$ sposobów).

Ile wynosi 0!?$0! = 1$. Tak się przyjmuje, żeby wzory kombinatoryki działały dla $k = 0$ i $k = n$ - na przykład $\binom{n}{n} = \frac{n!}{n! \cdot 0!} = 1$.

Jak rozpoznać, którego wzoru użyć? Zadaj dwa pytania: czy kolejność ma znaczenie i czy elementy mogą się powtarzać. Kolejność ważna i bez powtórzeń - wariacje bez powtórzeń (lub permutacje, gdy bierzemy wszystkie elementy); kolejność ważna i z powtórzeniami - $n^k$; kolejność nieważna - kombinacje.

Ile jest możliwych wyników w Lotto?$\binom{49}{6} = 13\,983\,816$ zestawów sześciu liczb.

Co to jest permutacja z powtórzeniami? Ustawienie elementów, wśród których niektóre są identyczne. Liczbę ustawień otrzymuje się, dzieląc $n!$ przez silnie liczebności powtarzających się elementów.

Ile jest kodów PIN? Czterocyfrowych: $10^4 = 10\,000$ - na każdym z czterech miejsc może stać dowolna z dziesięciu cyfr.

Przećwicz

• Reguła mnożenia i dodawania → - kody, liczby o różnych cyfrach, parzyste i podzielne przez 5.
• Permutacje → - kolejka, osoby obok siebie i nie obok siebie, anagramy KAJAK i MATEMATYKA.
• Wariacje → - podium, kody PIN, rozdzielanie nagród, sygnały z flag.
• Kombinacje → - delegacje, uściski dłoni, przekątne, symbol Newtona.
• Zadania mieszane → - rozpoznawanie modelu i liczenie „co najmniej jeden” przez dopełnienie.

Wszystkie zadania w jednym miejscu: Kombinatoryka - zadania z rozwiązaniami.

Podsumowanie

• Reguła mnożenia: etapy wyboru mnożymy; wszystkie wzory z niej wynikają.
• Permutacje $n!$; wariacje bez powtórzeń $\frac{n!}{(n-k)!}$; wariacje z powtórzeniami $n^k$.
• Kombinacje $\binom{n}{k} = \frac{n!}{k!(n-k)!}$; z powtórzeniami $\binom{n+k-1}{k}$.
• Kolejność ważna - wariacje (permutacje); nieważna - kombinacje.
• $0! = 1$, $\binom{n}{k} = \binom{n}{n-k}$.