Rozdział 6 Kombinatoryka

Jeżeli chcemy zliczać \(r\)-elementowe zestawy stworzone ze zbioru złożonego z \(n\) elementów, możemy skorzystać, w zależności od sytuacji, z jednego z poniższych wzorów.

6.1 Wariacje

Jeżeli w tworzonych \(r\)-elementowych zestawach kolejność ma znaczenie, to takie zestawy (ciągi) nazywamy wariacjami1.

Jeżeli elementy wariacji pobierane są bez zwracania (nie mogą się powtarzać), to liczba możliwych wariacji wynosi:

\[\begin{equation} Możliwości = \frac{n!}{(n-r)!} \tag{6.1} \end{equation}\]

Jeżeli elementy wariacji mogą się powtarzać, to liczba możliwych wariacji wynosi:

\[\begin{equation} Możliwości = n^r \tag{6.2} \end{equation}\]

W przypadku wariacji z powtórzeniami \(r\) może być większe niż \(n\).

6.2 Kombinacje

Kombinacjami nazywamy zestawy, w których kolejność nie ma znaczenia, np. zestawy {1; 2} i {2; 1} to ten sam zestaw.

Gdy elementy pobierane są bez zwracania, do wyznaczenia liczby kombinacji możemy wykorzystać Symbol Newtona

\[\begin{equation} Możliwości = \binom{n}{r} = \frac{n!}{r! \left( n-r \right)!} \tag{6.3} \end{equation}\]

Kombinacje ze zwracaniem możemy zliczyć za pomocą wzoru:

\[\begin{equation} Możliwości = \binom{n+r-1}{r} = \frac{\left(n+r-1\right)!}{r! \left( n-1 \right)!} \tag{6.4} \end{equation}\]

6.3 Pytania

Pytanie 6.1 Zaproponuj przykład, w którym przydadzą się kombinacje ze zwracaniem.

Pytanie 6.2 Czy w przypadku kombinacji ze zwracaniem \(r\) może być większe niż \(n\)?

Pytanie 6.3 Ile wynosi 0! (0 silnia)?

6.4 Zadania

Zadanie 6.1 Pewien kolekcjoner ma 16 średniowiecznych monet, ale 6 z nich to falsyfikaty. Losowo wybieramy 4 z 16 monet. Jakie jest prawdopodobieństwo, że wszystkie 4 wylosowane monety będą falsyfikatami?

Zadanie 6.2 Ile jest możliwych kombinacji liczb w Lotto (6 z 49)?

Zadanie 6.3 W sobotę 8 października 2022 w losowaniu Lotto padły następujące liczby: 7, 20, 23, 25, 29, 43. Ile było kombinacji wygrywających "trójkę"?

Zadanie 6.4 Ile ośmioznakowych haseł można ułożyć z 26 małych liter, 26 wielkich liter, 10 cyfr i 4 znaków specjalnych

  1. zakładając, że znaki mogą się powtarzać i brak wymagań typu "przynajmniej jedna cyfra"?

  2. zakładając, że znaki nie mogą się powtarzać?

Zadanie 6.5 Oblicz:

  1. \[\frac{7!}{3!(7-3)!}\]

  2. \[5 \choose 3\]

  3. \[8 \choose 0\]

  4. \[5 \choose 5\]

  5. \[7 \choose 6\]

  1. Uwaga! W starszych anglojęzycznych podręcznikach, wariacje nazywane są permutacjami (permutations), choć ten termin w pierwotnym znaczeniu definiuje się inaczej. Po polsku słowo permutacje w tym kontekście nie jest używane.↩︎