Każdy $k$–elementowy podzbiór zbioru $n$–elementowego, gdzie $0\le k\le n$, nazywamy $k$–elementową kombinacją tego zbioru $n$–elementowego.

Liczba wszystkich $k$–elementowych kombinacji zbioru $n$–elementowego, gdzie $0\le k\le n$, jest równa

$\left(\begin{array}{c}n\\ k\end{array}\right)=\frac{n!}{k!·\left(n-k\right)!}=\frac{n·\left(n-1\right)·\dots ·\left(n-k+1\right)}{1·2·\dots ·k}$

Omówimy kilka zastosowań twierdzenia o liczbie kombinacjiliczba wszystkich $k$–elementowych kombinacji zbioru $n$–elementowegotwierdzenia o liczbie kombinacji, w których kontekst dotyczący zliczania liczby podzbiorów wynika – jak się wydaje – natychmiast z treści zadania.

1. Do turnieju koszykówki, rozgrywanego systemem „każdy z każdym” (bez rewanżów), zgłosiło się $12$ drużyn. Zatem każdy mecz w tym turnieju przypisany był do dokładnie jednej pary drużyn wybieranej spośród $12$ zgłoszonych.

   Wynika stąd, że wszystkich meczów, które w tym turnieju należało rozegrać było tyle, ile wszystkich dwuelementowych kombinacji$k$–elementowa kombinacja zbioru $n$–elementowegokombinacji zbioru $12$–elementowego, czyli $\left(\begin{array}{c}12\\ 2\end{array}\right)=\frac{12!}{2!·10!}=\frac{12·11}{2·1}=66$.

2. Z pudełka, w którym znajduje się $20$ kul ponumerowanych liczbami od $1$ do $20$ losujemy jednocześnie $3$ kule. Wobec tego każdy wynik takiego losowania to trzyelementowa kombinacja$k$–elementowa kombinacja zbioru $n$–elementowegokombinacja zbioru dwudziestoelementowego.

   Stąd liczba wszystkich możliwych wyników takiego losowania jest równa $\left(\begin{array}{c}20\\ 3\end{array}\right)=\frac{20!}{3!·17!}=\frac{20·19·18}{3·2·1}=1140$.

3. Na okręgu zaznaczono $25$ różnych punktów. Obliczymy, ile jest wszystkich czworokątów wypukłych, których wierzchołkami są punkty wybrane spośród tych zaznaczonych.

   Ponieważ wybierając dowolne cztery z tych jedenastu punktów wyznaczamy dokładnie jeden czworokąt wypukły, więc każdy taki czworokąt opisuje dokładnie jedna czteroelementowa kombinacja$k$–elementowa kombinacja zbioru $n$–elementowegokombinacja $25$–elementowego zbioru punktów zaznaczonych na okręgu.

   Oznacza to, że wszystkich czworokątów spełniających warunki zadania jest $\left(\begin{array}{c}25\\ 4\end{array}\right)=\frac{25!}{4!·21!}=\frac{25·24·23·22}{4·3·2·1}=12650$.

4. Spośród uczniów $31-$osobowej klasy należy wybrać pięcioosobową delegację, która będzie reprezentować klasę na spotkaniu z dyrekcją szkoły. Zatem każda taka delegacja to pięcioelementowa kombinacja$k$–elementowa kombinacja zbioru $n$–elementowegokombinacja zbioru liczącego $31$ elementów.

   Wynika stąd, że liczba wszystkich delegacji, które można w ten sposób utworzyć jest równa $\left(\begin{array}{c}31\\ 5\end{array}\right)=\frac{31!}{5!·26!}=\frac{31·30·29·28·27}{5·4·3·2·1}=\mathrm{169\; 911}$.

5. W pewnej grze losowej należy wybrać $6$ liczb ze zbioru $\left\{1,2,3,\dots ,49\right\}$ wszystkich dodatnich liczb całkowitych mniejszych od $50$. Oznacza to, że każda wybrana szóstka liczb to sześcioelementowa kombinacja$k$–elementowa kombinacja zbioru $n$–elementowegokombinacja zbioru $49$–elementowego.

   Liczba tych wyborów jest więc równa $\left(\begin{array}{c}49\\ 6\end{array}\right)=\frac{49!}{6!·43!}=\frac{49·48·47·46·45·44}{6·5·4·3·2·1}=13 983 816$

6. W rozdaniu brydżowym gracz otrzymuje $13$ kart wybranych losowo z talii, w której są $52$ karty. Wynik takiego rozdania można więc opisać jako $13$–elementową kombinację$k$–elementowa kombinacja zbioru $n$–elementowegokombinację zbioru $52$–elementowego. Wynika stąd, że liczba wszystkich układów kart możliwych do otrzymania przez brydżystę jest równa $\left(\begin{array}{c}51\\ 13\end{array}\right)=\frac{52!}{13!·39!}=\frac{52·51·50·\dots ·41·40}{13·12·\dots ·2·1}=635 013 559 600$

Obliczymy, ile jest wszystkich funkcji rosnących, których dziedziną jest zbiór $A=\left\{a,b,c,d,e,f\right\}$, a zbiorem wartości jest zbiór $B=\left\{1,2,3,4,5,6,7,8,9\right\}$.

Rozwiązanie

Zauważmy, że każdy sześcioelementowy podzbiór zbioru $B$ można uporządkować rosnąco dokładnie na jeden sposób. Zatem każdej funkcji różnowartościowej spełniającej warunki zadania wzajemnie jednoznacznie przypiszemy sześcioelementową kombinację$k$–elementowa kombinacja zbioru $n$–elementowegokombinację zbioru $B$, odpowiadającą zbiorowi wartości tej funkcji.

Wynika stąd, że jest $\left(\begin{array}{c}9\\ 6\end{array}\right)=\frac{9!}{6!·3!}=\frac{9·8·7}{3·2·1}=84$ funkcji rosnących ze zbioru $A$ do zbioru $B$.

Elektroniczna zabawka ma $10$ przycisków, rozmieszczonych po $5$ w dwóch rzędach (jak na poniższym rysunku).

R1akw8sul7qVT

Ilustracja przedstawia elektroniczną zabawkę. Posiada ona 10 przycisków. rozłożone są po 4 na prawej i lewej stronie zabawki oraz dwa pionowo na środku.

Po naciśnięciu w tej zabawce dowolnie wybranego przycisku zapala się dioda, która zmienia jego kolor na czerwony, a dopiero po włączeniu diody każdym z $10$ przycisków następuje wyłączenie wszystkich diod (inaczej żadnej diody zgasić nie można).

Jeżeli naciśniemy każdy przycisk dokładnie raz, pilnując zasady: przycisk w danym rzędzie można wcisnąć wtedy i tylko wtedy, gdy wszystkie przyciski z jego lewej strony zostały już wciśnięte, to po zapaleniu $10$ diod odgrywana jest melodyjka.

Obliczymy, ile jest możliwych sposobów naciśnięcia wszystkich przycisków tej zabawki w takim porządku, po którym będzie można usłyszeć melodyjkę.

Rozwiązanie

Naszym zadaniem jest podjęcie $10$ kolejnych decyzji, za każdym razem polegających na wybraniu i wciśnięciu przycisku, pod którym nie świeci się dioda.

Jeżeli ponumerujemy przyciski: w górnym rzędzie, idąc od lewej do prawej, numerami od $1$ do $5$, w dolnym rzędzie, również idąc od lewej do prawej, numerami od $6$ do $10$, to każda sekwencja $10$ kolejno naciśniętych przycisków odpowiada wzajemnie jednoznacznie pewnej permutacjipermutacja zbioru $n$–elementowegopermutacji zbioru $\left\{1,2,3,4,5,6,7,8,9,10\right\}$.

Melodyjkę usłyszymy wtedy i tylko wtedy, gdy w tej permutacjipermutacja zbioru $n$–elementowegopermutacji numery od $1$ do $5$ pojawią się w porządku wzrastania numerów i jednocześnie numery od $6$ do $10$ pojawią się w porządku wzrastania numerów – taki warunek spełnia np. permutacjapermutacja zbioru $n$–elementowegopermutacja $\left(6,7,1,8,2,3,4,9,10,5\right)$. Permutacjępermutacja zbioru $n$–elementowegoPermutację, która spełnia powyższe warunki nazwijmy dobrą.

Zauważmy zatem, że aby otrzymać permutacjępermutacja zbioru $n$–elementowegopermutację dobrą należy ustalić w niej $5$ miejsc dla numerów od $1$ do $5$, następnie rozmieścić te numery na wybranych miejscach w porządku ich wzrastania (co da się zrobić tylko na jeden sposób), a następnie na pozostałych miejscach, również w kolejności rosnącej, rozmieścić  numery od $6$ do $10$.

Ponieważ każdy wybór $5$ numerów ze zbioru $\left\{1,2,3,4,5,6,7,8,9,10\right\}$ to $5$–elementowa kombinacja$k$–elementowa kombinacja zbioru $n$–elementowegokombinacja ze zbioru $10$–elementowego, więc wszystkich możliwych sposobów naciśnięcia dziesięciu przycisków tej zabawki w takim porządku, który gwarantuje odsłuchanie melodyjki jest $\left(\begin{array}{c}10\\ 5\end{array}\right)=\frac{10·9·8·7·6}{5·4·3·2·1}=252$.

Rozpatrzmy dziewięciokrotny rzut monetą.

Zauważmy, że jeżeli do numeru każdego z kolejnych rzutów przypiszemy jego wynik: 'o' – jeśli wypadł orzeł, 'r' – jeśli wypadła reszka, to wynikowi każdego dziewięciokrotnego rzutu monetą przyporządkujemy wzajemnie jednoznacznie dziewięcioelementowy ciąg, którego elementami są 'o' lub 'r'.

Korzystając z tego spostrzeżenia, możemy obliczyć, ile jest wszystkich możliwych wyników określonych następującymi warunkami:

1. wypadły dokładnie $4$ reszki.

   Wystarczy w tym celu ustalić, na ile sposobów można wybrać $4$ miejsca dla $4$ elementów 'r' w opisanym powyżej $9$–elementowym ciągu. Ponieważ każdy taki wybór to $4$–elementowa kombinacja$k$–elementowa kombinacja zbioru $n$–elementowegokombinacja ze zbioru $9$–elementowego, więc wszystkich możliwych wyników dziewięciokrotnego rzutu monetą, w których wypadły $4$ reszki jest $\left(\begin{array}{c}9\\ 4\end{array}\right)=\frac{9!}{4!·5!}=\frac{9·8·7·6}{4·3·2·1}=126$

2. wypadło dokładnie $5$ orłów.

   Podobnie jak w poprzednim przykładzie ustalimy, na ile sposobów można wybrać $5$ miejsc dla $5$ elementów 'o' w omawianym $9$–elementowym ciągu. Ponieważ każdy taki wybór to $5$–elementowa kombinacja$k$–elementowa kombinacja zbioru $n$–elementowegokombinacja ze zbioru $9$–elementowego, więc wszystkich możliwych wyników dziewięciokrotnego rzutu monetą, w których wypadło $5$ orłów jest $\left(\begin{array}{c}9\\ 5\end{array}\right)=\frac{9!}{5!·4!}=\frac{9·8·7·6}{4·3·2·1}=126$.

Zauważmy, że każdy wynik dziewięciokrotnego rzutu monetą, w którym w pewnych $5$ rzutach wypadł orzeł, jednocześnie opisuje taki wynik, w którym w każdym z pozostałych $4$ rzutów wypadła reszka. Jest to więc dokładnie ten sam wynik, co omówiony w podpunkcie (a), a więc liczby tych wyników są – jak to już zresztą bezpośrednio obliczyliśmy – równe.

Uwaga 1. Jeśli rozpatrzymy $n$–krotny rzut monetą, to – rozumując podobnie jak w powyższym przykładzie – stwierdzimy, że liczba wszystkich możliwych wyników tego doświadczenia, w których wypadło $k$ reszek (gdzie $0\le k\le n$) jest równa liczbie wszystkich wyników tego doświadczenia, w których wypadło $n-k$ orłów.

Zatem dla dowolnych liczb całkowitych $n$ i $k$ takich, że $0\le k\le n$ zachodzi równość

$\left(\begin{array}{c}n\\ k\end{array}\right)=\left(\begin{array}{c}n\\ n-k\end{array}\right)$

Algebraiczny dowód tej tożsamości pozostawiamy czytelnikowi jako nietrudne ćwiczenie.

Uwaga 2. Jeśli rozpatrzymy $n$–krotny rzut monetą, to wszystkie możliwe wyniki możemy podzielić na rozłączne przypadki ze względu np. na liczbę otrzymanych orłów. Możemy ich wyrzucić $0$ lub $1$, lub $2$, $\dots$, lub $n$. Oznacza to, że wszystkich wyników jest

$\left(\begin{array}{c}n\\ 0\end{array}\right)+\left(\begin{array}{c}n\\ 1\end{array}\right)+\left(\begin{array}{c}n\\ 2\end{array}\right)+\dots +\left(\begin{array}{c}n\\ n\end{array}\right)$.

Z drugiej strony w każdym z tych $n$ rzutów mamy dwie możliwości: otrzymamy orła lub nie otrzymamy orła, zatem wszystkich wyników jest $2^n$.

Wobec tego dla dowolnych liczb całkowitych $n$ i $k$ takich, że $0\le k\le n$ zachodzi równość

$\sum _{k=0}^n\left(\begin{array}{c}n\\ k\end{array}\right)=\left(\begin{array}{c}n\\ 0\end{array}\right)+\left(\begin{array}{c}n\\ 1\end{array}\right)+\left(\begin{array}{c}n\\ 2\end{array}\right)+\dots +\left(\begin{array}{c}n\\ n\end{array}\right)=2^n$

każdy $k$–elementowy podzbiór zbioru $n$–elementowego, gdzie $0\le k\le n$, nazywamy $k$–elementową kombinacją tego zbioru $n$–elementowego

liczba wszystkich $k$–elementowych kombinacji zbioru $n$–elementowego, gdzie $0\le k\le n$, jest równa

$\left(\begin{array}{c}n\\ k\end{array}\right)=\frac{n!}{k!·\left(n-k\right)!}=\frac{n·\left(n-1\right)·\dots ·\left(n-k+1\right)}{1·2·\dots ·k}$

każdy ciąg utworzony ze wszystkich elementów zbioru $n$–elementowego