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:
- wylosujemy jedną z dwóch wadliwych żarówek i dwie z ośmiu działających żarówek lub
- wylosujemy same dobre żarówki.
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\).
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\).
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\).