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 wariacjami¹.

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.↩︎