Kombinacje

Definicja
Kombinacją \(k\)-elementową utworzoną ze zbioru \(n\)-elementowego \((k\le n)\) nazywamy każdy \(k\)-elementowy podzbiór tego zbioru.

Z definicji wynika, że kombinacja zawiera jedynie określoną liczbę \(k\) \((k\le n)\) różnych elementów spośród danych \(n\) elementów oraz że kolejność elementów kombinacji nie ma znaczenia. Dwa podzbiory złożone z tych samych elementów, ale różniące się tylko ich porządkiem stanowią więc tę samą kombinację.

Przykład
Wyznaczymy wszystkie możliwe \(2\)-elementowe kombinacje zbioru \(A=\{a,b,c\}\).
Zauważmy, że tworząc \(2\)-elementowe kombinacje zbioru \(A=\{a,b,c\}\), łączymy jego elementy w pary.
Do elementu \(a\) możemy dobrać element \(b\) albo element \(c\) i w ten sposób otrzymamy dwa różne \(2\)-elementowe podzbiory zbioru \(A=\{a,b,c\}\):
\(\left\{a,b\right\}\) oraz \(\left\{a,c\right\}\)
Element \(b\) moglibyśmy połączyć w parę z elementem \(a\) albo z elementem \(c\), wówczas otrzymalibyśmy dwa \(2\)-elementowe podzbiory zbioru \(A=\{a,b,c\}\):
\(\left\{b,a\right\}\) oraz \(\left\{b,c\right\}\)
Trzeba jednak pamiętać, że podzbiory o tych samych elementach tylko ustawionych w innej kolejności to ta sama kombinacja. Zatem nie bierzemy pod uwagę kombinacji \(\left\{a,b\right\}\) i mamy trzy różne \(2\)-elementowe kombinacje zbioru \(A=\{a,b,c\}\):
\(\left\{a,b\right\}\), \(\left\{a,c\right\}\), \(\left\{b,c\right\}\)
Rozważając element \(c\), nie otrzymamy już żadnego innego \(2\)-elementowe podzbioru zbioru \(A=\{a,b,c\}\).
Z elementów zbioru \(A\) można zatem utworzyć tylko \(2+1=3\) różne kombinacje.

Jeżeli \(k\le n\) oraz \(C_n^k\) oznacza liczbę wszystkich możliwych \(k\)-elementowych kombinacji zbioru \(n\)-elementowego, to \[\eqalign{C_n^k&={n \choose k}=\frac{n!}{k!\cdot\left(n-k\right)!}= \frac{\ccancel{\fioletowy}{\left(n-k\right)!}\cdot \left(n-k+1\right)\cdot \left(n-k+2\right)\cdot \left(n-k+3\right)\cdot\ldots\cdot n}{k!\cdot\ccancel{\fioletowy}{\left(n-k\right)!}}=\cr &= \frac{\left(n-k+1\right)\cdot \left(n-k+2\right)\cdot \left(n-k+3\right)\cdot\ldots\cdot n}{k!}\cr}\]

Iloma sposobami można rozdzielić cztery 1-osobowe zaproszenia do teatru między dziesięć osób, jeśli każda może otrzymać co najwyżej jedno zaproszenie?
Możliwości rozdzielenia czterech zaproszeń między dziesięć osób jest tyle, ile \(4\)-elementowych kombinacji \(10\)-elementowego zbioru osób. Oznacza to, że wszystkich możliwych sposobów podziału zaproszeń jest \[C_{10}^4={10 \choose 4}=\frac{10!}{4!\cdot\left(10-4\right)!}=\frac{10!}{4!\cdot6!}= \frac{\stackrel{{ \;\;\; }}{\ccancel{\fioletowy}{6!}}\cdot 7\cdot 8\cdot 9\cdot 10} {4!\cdot\stackrel{{ \;\;\; }}{\ccancel{\fioletowy}{6!}}}=210\]
Obliczyć liczbę wszystkich przekątnych \(n\)-kąta wypukłego.
Do obliczenia liczby przekątnych w \(n\)-kącie wypukłym można użyć \(2\)-elementowych podzbiorów \(n\)-elementowego zbioru wierzchołków tego \(n\)-kąta. Jednak wśród nich są również pary sąsiednich wierzchołków, które odpowiadają bokom tego \(n\)-kąta, a nie przekątnym, i muszą zostać odjęte od liczby wszystkich \(2\)-elementowych kombinacji \(n\)-elementowego zbioru wierzchołków. Przekątnych w dowolnym \(n\)-kącie wypukłym jest zatem \[\eqalign{C_n^2-n&={n \choose 2}-n=\frac{n!}{2!\cdot\left(n-2\right)!}-n= \frac{\ccancel{\fioletowy}{\left(n-2\right)!}\cdot \left(n-1\right)\cdot n}{2!\cdot\ccancel{\fioletowy}{\left(n-2\right)!}}-n=\cr&= \frac{\left(n-1\right)\cdot n}{2!}-n= \frac{n\cdot\left(n-3\right)}{2}\cr}\]
Trener siatkarzy ma do dyspozycji dziesięciu zawodników. Ile różnych 6-osobowych drużyn może skompletować?
Możliwości wyboru sześciu siatkarzy spośród dziesięciu osób jest tyle, ile istnieje \(6\)-elementowych kombinacji \(10\)-elementowego zbioru zawodników. Trener może więc stworzyć ich \[C_{10}^6={10 \choose 6}=\frac{10!}{6!\cdot\left(10-6\right)!}=\frac{10!}{6!\cdot4!}= \frac{\stackrel{{ \;\;\; }}{\ccancel{\fioletowy}{6!}}\cdot 7\cdot 8\cdot 9\cdot 10} {\stackrel{{ \;\;\; }}{\ccancel{\fioletowy}{6!}}\cdot 4!}=210\]
Spotyka się ośmiu kolegów. Każdy wita się z każdym poprzez uścisk dłoni. Ile nastąpi powitań?
Każdemu uściskowi dłoni odpowiada jeden podzbiór \(2\)-elementowy \(8\)-elementowego zbioru kolegów. Powitań nastąpi zatem \[C_8^2={8 \choose 2}=\frac{8!}{2!\cdot\left(8-2\right)!}=\frac{8!}{2!\cdot6!}= \frac{\ccancel{\fioletowy}{6!}\cdot 7\cdot 8}{2!\cdot\ccancel{\fioletowy}{6!}}=28\]
Ile różnych prostych można poprowadzić przez dziesięć punktów, z których żadne trzy nie są współliniowe?
Każda prosta łączy tylko dwa z dziesięciu danych punktów, gdyż żadne trzy punkty nie są współliniowe. Zatem jednej prostej odpowiada jeden \(2\)-elementowy podzbiór \(10\)-elementowego zbioru punktów. Prostych wyznaczonych przez dziesięć punktów, z których żadne trzy nie są współliniowe, jest zatem \[C_{10}^2={10 \choose 2}=\frac{10!}{2!\cdot\left(10-2\right)!}=\frac{10!}{2!\cdot8!}= \frac{\ccancel{\fioletowy}{8!}\cdot 9\cdot 10}{2!\cdot\ccancel{\fioletowy}{8!}}=45\]
Na ile sposobów z talii \(52\) kart można wylosować pięć kart tak, aby wśród nich były dwa asy?
W talii \(52\) kart są cztery asy i \(48\) innych kart. Losując pięć kart, chcemy, aby wśród nich były dwa asy i trzy inne karty. Dwa asy możemy wylosować na tyle sposobów, ile jest \(2\)-elementowych podzbiorów \(4\)-elementowego zbioru asów, czyli \[C_2^4={4 \choose 2}=\frac{4!}{2!\cdot\left(4-2\right)!}= \frac{4!}{2!\cdot2!}=\frac{\ccancel{\fioletowy}{2!}\cdot 3\cdot 4}{2!\cdot\ccancel{\fioletowy}{2!}}=6\] Pozostałe trzy karty możemy wylosować na tyle sposobów, ile jest \(3\)-elementowych kombinacji \(48\)-elementowego zbioru kart innych niż asy, więc możemy to zrobić na \[ C_{47}^3={47 \choose 3}=\frac{47!}{3!\cdot\left(47-3\right)!}= \frac{47!}{3!\cdot44!}=\frac{\ccancel{\fioletowy}{44!}\cdot45\cdot46\cdot47}{3!\cdot\ccancel{\fioletowy}{44!}}= 16\ 215\] sposobów. Zgodnie z regułą mnożenia z talii \(52\) kart możliwości wylosowania pięciu kart, wśród których będą dwa asy, jest \[C_4^2\cdot C_{47}^3={4 \choose 2}\cdot{47 \choose 3}=6\cdot 16\ 215=97\ 290\]
W pudełku znajduje się dziesięć żarówek, w tym dwie wadliwe. Wybieramy losowo bez zwracania trzy żarówki. Ile istnieje sposobów wylosowania co najwyżej jednej wadliwej żarówki?
Skoro wśród wylosowanych żarówek ma być co najwyżej jedna wadliwa, to musimy rozważyć dwa przypadki:
  1. wylosujemy jedną z dwóch wadliwych żarówek i dwie z ośmiu działających żarówek lub
  2. wylosujemy same dobre żarówki.
W pierwszym przypadku zgodnie z regułą mnożenia mamy \[ C_2^1\cdot C_8^2={2 \choose 1}\cdot{8 \choose 2}=1\cdot\frac{8!}{2!\cdot\left(8-2\right)!}= \frac{8!}{2!\cdot6!}=\frac{\ccancel{\fioletowy}{6!}\cdot7\cdot8}{2!\cdot\ccancel{\fioletowy}{6!}}=28\] możliwości. W drugim przypadku możliwości jest \[C_8^3={8 \choose 3}=\frac{8!}{3!\cdot\left(8-3\right)!}= \frac{8!}{2!\cdot5!}=\frac{\ccancel{\fioletowy}{5!}}{2!\cdot\ccancel{\fioletowy}{5!}}=168\] Zgodnie z regułą dodawania sposobów wylosowania co najwyżej jednej wadliwej żarówki jest zatem \[28+168=196\]
Reguła mnożenia
Jeżeli dane są dwa zbiory skończone \(A\) i \(B\), z których zbiór \(A\) ma \(m\) elementów,
a zbiór \(B\) ma \(n\) elementów, to liczba różnych par \((a,b)\), takich że \(a\in A\) i \(b\in B\),
jest równa iloczynowi mocy tych zbiorów: \(m\cdot n\).
Reguła dodawania
Jeżeli dane są dwa zbiory rozłączne \(A\) i \(B\), z których zbiór \(A\) ma \(m\) elementów,
a zbiór \(B\) ma \(n\) elementów, to moc zbioru \(A\cup B\) jest równa sumie mocy tych zbiorów: \(m+n\).