Silnia i kombinacje
W tym artykule zostaną omówione kombinacje, czyli wybór elementów z pewnego zbioru, ale kolejność ich wyboru nie ma znaczenia.
Wcześniej zapoznaj się z pojęciem silni.
Silnia
Dla liczby \$n\in\mathbb{N}\$ określamy silnie jako iloczyn:
\[ n! = \begin{cases} 1 \ \text{dla} \ n=0 \\ 1*2*3*\cdots * (n-1) * n \ \text{dla} \ n\ge 1 \end{cases}\]a) \$0! = 1\$
b) \$1! = 1\$
c) \$4! = 1*2*3*4 = 24\$
d) \$5! = 1*2*3*4*5 = 120\$
e) \$(n+1)! = 1*2*3*\cdots * n * (n+1) = n! * (n+1)\$
Silnia rośnie bardzo szybko, ale jej zapis przydaje się w zadaniach kombinatorycznych. To jest podobnie jak z mnożeniem czy potęgowaniem, używamy pewnego skrótu np. \$2^5=2*2*2*2*2\$.
Na ile sposobów ustawimy \$8\$ osób w kolejce jeden za drugim?
Na pierwszym miejscu ustawiamy \$1\$ osobę z \$8\$.
Na drugim miejscu ustawiamy \$1\$ osobę z \$7\$.
Na trzecim miejscu ustawiamy \$1\$ osobę z \$6\$.
\$ \qquad \vdots\$
Na ostatnim miejscu ustawiamy ostatnią osobę.
Z reguły mnożenia otrzymujemy:
\[ 8*7*6*5*4*3*2*1 = 8! \]Odp. Osiem osób ustawimy w kolejce na \$8!\$ sposobów.
Na ile sposobów można zaparkować \$8\$ samochodów na \$5\$ miejscach parkingowych?
Kolejność ustawiania samochodów ma znaczenie (Miejsca parkingowe są numerowane). Będziemy mieć ciąg pięciu elementów. Położenie w ciągu odpowiada miejscu parkingowemu.
Na pierwszym miejscu ustawiamy \$1\$ samochód z \$8\$.
Na drugim miejscu ustawiamy \$1\$ samochód z \$7\$.
Na trzecim miejscu ustawiamy \$1\$ samochód z \$6\$.
\$ \qquad \vdots\$
Na ostatnim piątym miejscu ustawiamy \$1\$ samochód z \$4\$ pozostałych.
Z reguły mnożenia otrzymujemy:
\[ 8*7*6*5*4\]Stosując silnię otrzymujemy:
\[ 8*7*6*5*4 = \frac{8*7*6*5*4*3*2*1}{3*2*1} = \frac{8!}{3!} \]Odp. Osiem samochodów możemy zaparkować na pięciu miejscach parkingowych na \$\displaystyle{\frac{8!}{3!} }\$ sposobów.
Kombinacje
Kombinacją \$k\$ elementową ze zbioru \$n\$ elementowego \$A\$ nazywamy dowolny podzbiór \$B\subset A\$, który zawiera \$k\$ elementów. Zakładamy, że \$0\le k\le n\$.
Ilość kombinacji (podzbiorów) \$k\$ elementowych zbioru \$n\$ elementowego określa wzór:
Kiedy wybieramy ze zbioru jakieś elementy i kolejność ich wyboru nie ma znaczenia, to używamy wzoru na kombinacje.
Wzór na kombinacje nie jest wymagany na maturze na poziomie podstawowym, ale warto umieć z niego korzystać, bo może ułatwić obliczenia w zadaniach kombinatorycznych.
Weźmy zbiór \$A=\{ a, b, c, d \}\$. Ile jest podzbiorów \$3\$ elementowych zbioru \$A\$?
Używamy wzoru na kombinacje:
\[\begin{aligned} C^3_4 = \frac{4!}{(4-3)! * 3!} = \frac{4!}{1! * 3!} = \frac{\cancel{3!} * 4}{1 * \cancel{3!}} = 4 \end{aligned}\]Mamy \$4\$ podzbiory. Wypiszmy je:
\[ \{ a,b,c \}, \{ a,b,d \}, \{ a,c,d \}, \{ b, c, d \} \]Kolejność wyboru dwóch osób nas nie interesuje.
Sposób I
Na każdą z \$23\$ osób możemy wybrać \$22\$ osoby i w ten sposób znajdziemy ilość wszystkich par \$(\text{osoba1}, \text{osoba2})\$, w której kolejność ma znaczenie.
\[ 23*22 \]Dzielimy iloczyn przez dwa otrzymując właściwą ilość podzbiorów (elementy nie powtarzają się).
\[ \frac{23*\cancel{22}}{\cancel{2}} = 23 * 11 = 253 \]Odp. Wybierzemy \$2\$ uczniów z klasy \$23\$ osobowej na \$253\$ sposoby.
Sposób II
Używamy wzoru na kombinacje:
\[\begin{aligned} C^2_{23} = \frac{23!}{(23-2)! * 2!} = \frac{23!}{21! * 2!} = \frac{\cancel{21!} * \cancel{22}^{11} * 23}{\cancel{21!} * \cancel{2}} &= 11*23 \\ &=253 \end{aligned}\]Odp. Wybierzemy \$2\$ uczniów z klasy \$23\$ osobowej na \$253\$ sposoby.
Kolejność wyboru trzech osób nas nie interesuje.
Szukamy ilość kombinacji \$3\$ elementowych ze zbioru \$20\$ elementowego.
\[\begin{aligned} C^3_{20} = \frac{20!}{(20-3)! * 3!} = \frac{20!}{17! * 3!} &= \frac{\cancel{17!} * \cancel{18}^3 * 19 * 20}{\cancel{17!} * \cancel{6}} \\ &= 3*19*20 \\ &= 1140 \end{aligned}\]Odp. Podany samorząd uczniowski można wybrać na \$1140\$ sposoby.
Kolejność wyboru nauczycieli do kolegium nie ma znaczenia.
\[ \text{ilość wyboru mężczyzn} * \text{ilość wyboru kobiet} \]Ilość możliwości wyboru mężczyzn:
\[\begin{aligned} C^2_7 = \frac{7!}{5! * 2!} = \frac{\cancel{5!} * \cancel{6}^3 * 7}{\cancel{5!} * \cancel{2}} = 3*7 = 21 \end{aligned}\]Ilość możliwości wyboru kobiet:
\[\begin{aligned} C^2_8 = \frac{8!}{6! * 2!} = \frac{\cancel{6!} * 7 * \cancel{8}^4}{\cancel{6!} * \cancel{2}} = 7*4 = 28 \end{aligned}\]Razem:
\[ 21*28 = 588 \]Odp. Podane kolegium nauczycielskie wybierzemy na \$588\$ sposobów.