Matematyka dla liceum/Rachunek prawdopodobieństwa/Elementy kombinatoryki

Elementy kombinatoryki

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). Szablon:Mat:Def $n!=\{\begin{array}{c}1,\text{ gdy }n=0\text{ lub }n=1\\ 1\cdot 2\cdot 3\cdot ...\cdot (n-1)\cdot n,\text{ gdy }n\ge 2\end{array}$

Przykłady:

1. $4!=1\cdot 2\cdot 3\cdot 4=24$
2. $\frac{5!}{6!}=\frac{120}{720}=\frac{1}{6}$
3. $3!\cdot 4\cdot 5\cdot 6=6!=720$
4. $\frac{(n+2)!}{n!}=\frac{n!\cdot (n+1)\cdot (n+2)}{n!}=(n+1)\cdot (n+2)$

Permutacje

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

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. Szablon:Mat:Def

Przykłady:

$W_3^2=3^2=9$

$W_4^5=4^5=1024$

$W_1^{100}=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_4^2=4^2=16$ .

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

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

Itd.

Wariacje bez powtórzeń

Przykład:

$V_3^2=\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

Szablon:Mat:Ciek Szablon:Mat:Def Symbol $(\genfrac{}{}{0ex}{}{n}{k})$ czytamy n po k lub n nad k.

Warto zapamiętać, że:

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

$(\genfrac{}{}{0ex}{}{n}{k})+(\genfrac{}{}{0ex}{}{n}{k+1})=(\genfrac{}{}{0ex}{}{n+1}{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ść $(\genfrac{}{}{0ex}{}{n}{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. Szablon:Mat:Def

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 elementowego. Wszystkich takich kombinacji jest
$C_3^2=(\genfrac{}{}{0ex}{}{3}{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