Matematyka dla liceum/Rachunek prawdopodobieństwa/Elementy kombinatoryki

Elementy kombinatoryki

Kombinatoryka - dział w matematyce, w którym zajmujemy się m.in. obliczaniem liczebności zbiorów bądź długości ciągów, które łączą w określony sposób elementy należące do skończonego zbioru (teoria zliczania).

Silnia

Jeśli mamy wyrażenie, którym jest ciąg mnożeń kolejnych liczb od 1, np. $1*2*3*4*5$, możemy zapisać go w skrócie jako 5! (pięć silnia).

DEFINICJA Silnia z liczby naturalnej n jest oznaczana przez n!. Dla $n=0$ lub $n=1$ wynosi ona 1, natomiast dla $n \ge 2$ jest równa iloczynowi wszystkich liczb naturalnych od 1 do n.

$n! = \begin{cases} 1 , \quad \mbox{ gdy } n=0 \mbox{ lub } n=1\\ 1 \cdot 2 \cdot 3 \cdot ... \cdot (n-1) \cdot n , \quad \mbox{ gdy } n \ge 2\end{cases}$

Przykłady:

1. $4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24$

1. $\frac{5!}{6!} = \frac{120}{720} = \frac{1}{6}$

1. $3! \cdot 4 \cdot 5 \cdot 6 = 6! = 720$

1. $\frac{(n+2)!}{n!} = \frac{n! \cdot (n+1) \cdot (n+2)}{n!} = (n+1) \cdot (n+2)$

Permutacje

Jeśli, mając liczbę 1243, zechcemy zamienić miejscami niektóre cyfry, możemy otrzymać np. 4321 lub 1432 lub 3214. Każda z nich jest permutacją zbioru cyfr $\{1,2,3,4\}$.

DEFINICJA Ciąg utworzony ze wszystkich n elementów zbioru nazywamy jego permutacją. Liczbę wszystkich permutacji danego n-elementowego zbioru obliczamy wg wzoru  $P_{n}\,=\,n!$ .

Przykłady:

$P_2 = 2! = 1 \cdot 2 = 2$

$P_7 = 7! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 = 5040$

Wyjaśnienie:

Załóżmy, że mamy zbiór składający się z 4 elementów: a, b, c oraz d. Ile możemy ułożyć permutacji? Pierwszy element permutacji wybieramy spośród liter a, b, c i d. Mamy więc 4 możliwości. Gdy już wybierzemy, zostaną nam 3 litery i spośród nich wybierzemy drugi element. Dla każdego wybranego pierwszego elementu drugi możemy wybrać na 3 możliwości. Możemy takich par stworzyć 3*4=12. Dla każdej z 12 par, trzeci element wybierzemy z pozostałych 2 liter, czyli na 2 możliwości, dzięki czemu możemy uzyskać 24 trójki (2*3*4). Zostaje nam jedna litera, która będzie czwartym elementem (tak więc 1 możliwość). Mamy więc 1*2*3*4=24 opcji ułożenia permutacji z 4 liter.

W przypadku, w którym zbiór składałby się z trzech elementów i tymi elementami byłyby a, b oraz c:

$P_3 = 1 \cdot 2 \cdot 3 = 6$

1. abc    2. acb

3. bac    4. bca

5. cab    6. cba

Wariacje z powtórzeniami

Ułóżmy dowolną 3-cyfrową liczbę, mając do dyspozycji cyfry 1,2,3,4,5. Może to być np. 134, 325, 222. Wszystkie one są 3-wyrazowymi wariacjami zbioru 5-elementowego.

DEFINICJA Wariacją z powtórzeniami nazywamy ciąg o długości k, którego wyrazy pochodzą z n-elementowego zbioru. Liczbę wszystkich wariacji danego zbioru obliczamy ze wzoru $W^k_n = n^k$ .

Przykłady:

$W^2_3 = 3^2 = 9$

$W^5_4 = 4^5 = 1024$

$W^{100}_1 = 1^{100} = 1$

Wyjaśnienie:

Policzmy, ile można stworzyć wariacji k=2 elementowych ze zbioru n=4 elementów, np. {a,b,c,d}. Pierwszym elementem ciągu (wariacji) może być dowolna z liter a,b,c,d. Są więc 4 możliwości, dla każdej z nich możemy wybrać drugi element, także z liter a,b,c,d. Dla każdego z 4 możliwych pierwszych elementów mamy 4 możliwości wybrania drugiego elementu, razem 4*4=16 możliwych wariacji (z powtórzeniami). Wg wzoru: $W^2_4\,=\,4^2\,=\,16$ .

1. aa     2. ab     3. ac     4. ad

5. ba     6. bb     7. bc     8. bd

Itd.

Wariacje bez powtórzeń

DEFINICJA Wariacją bez powtórzeń nazywamy ciąg k wyrazów, nie powtarzających się, które są elementami danego zbioru o liczności n. Ilość wszystkich wariacji obliczamy ze wzoru $V^k_n = \frac{n!}{(n-k)!}$ .

Przykład:

$V^2_3 = \frac{3!}{(3-2)!} = \frac{1 \cdot 2 \cdot 3}{1} = 6$

Tzn. mając zbiór n=3 elementowy, np. {a,b,c}, możemy uzyskać 6 wariacji o długości k=2:

1. ab     2. ac

3. ba     4. bc

5. ca     6. cb

Symbol Newtona

Czy wiesz, że... Isaac Newton - matematyk, fizyk, astronom i filozof angielski. Zasłynął odkryciami w fizyce. Był także współtwórcą rachunku różniczkowego i całkowego.

DEFINICJA Symbol Newtona ${n \choose k} = \frac{n!}{k! \cdot (n-k)!}\ ,\;\; \mbox{gdzie}\;\; n,k \in \mathbb{N}\;\; \mbox{i}\;\; n \ge k.$

Symbol ${n \choose k}$ czytamy n po k lub n nad k.

Warto zapamiętać, że:

1. ${n \choose 0} = 1$
2. ${n \choose 1} = n$
3. ${n \choose n} = 1$
4. ${n \choose n-1} = n$
5. ${n \choose k} = {n \choose n-k}$
6. Pewna równość dla symboli Newtona

${n \choose k} + {n \choose k+1} = {n+1 \choose k+1}$

Ciekawostka:
Wyżej wymienione równanie jest wykorzystane w trójkącie Pascala. Obliczamy k-tą liczbę w n-tym wierszu jako wartość ${n \choose k}$. Zauważmy, że każda liczba jest sumą dwóch stojących nad nią (z wyjątkiem jedynek, tworzących "boki" trójkąta).

Kombinacje

W odróżnieniu od permutacji i wariacji, kombinacja nie jest ciągiem, a podzbiorem elementów. Ważna cecha - kolejność nie ma znaczenia.

DEFINICJA Kombinacją k-elementową nazywamy dowolny podzbiór (k- wyrazowy) danego n-elementowego zbioru. Liczbę wszystkich takich kombinacji wyraża wzór:   $C_n^k = {n \choose k}$ .

Przykład:
W urnie znajduje się biała, czarna i niebieska kula (zbiór {b,c,n}). Losujemy z niej 2 kule. W ten sposób uzyskujemy k=2 elementową kombinację zbioru n=3 elemntowego. Wszystkich takich kombinacji jest
$C_3^2\,=\,{3 \choose 2}\,=\,\frac{3!}{2!(3-2)!}\,=\,3$

Istotnie, możemy wylosować tylko
1. białą i czarną,
2. białą i niebieską,
3. czarną i niebieską.

> Rozwiązane zadania