Przeczytaj
Rozpatrzmy –elementowy zbiór .
Liczbę wszystkich –elementowych podzbiorów zbioru , gdzie , oznaczamy symbolem , co czytamy „ po ” lub „ nad ”.
Zauważmy, że elementy każdego –elementowego podzbioru, dowolnie wybranego spośród opisanych powyżej, możemy rozmieścić na sposobów – otrzymamy wtedy wszystkie możliwe permutacje tego podzbioru –elementowego. Jeżeli tę czynność powtórzymy dla wszystkich podzbiorów, to w efekcie otrzymamy wszystkie –elementowe wariacje bez powtórzeń –elementowego zbioru .
Z drugiej strony: wiemy, że jest wszystkich –elementowych wariacji bez powtórzeń zbioru –elementowego (gdzie ).
Otrzymujemy stąd równość , co oznacza, że
dla każdych liczb całkowitych , , które spełniają warunek .
Dla podzbioru pustego (wtedy ) zbioru –elementowego dostajemy w szczególności .
Ponieważ zbiór –elementowy nie ma podzbiorów, które mają więcej niż –elementów, więc gdy dodatnie liczby całkowite oraz spełniaja warunek , to .
Każdy –elementowy podzbiór zbioru –elementowego, gdzie , nazywamy –elementową kombinacją tego zbioru –elementowego.
Liczba wszystkich –elementowych kombinacji zbioru –elementowego, gdzie , jest równa
Omówimy kilka zastosowań twierdzenia o liczbie kombinacjitwierdzenia o liczbie kombinacji, w których kontekst dotyczący zliczania liczby podzbiorów wynika – jak się wydaje – natychmiast z treści zadania.
Do turnieju koszykówki, rozgrywanego systemem „każdy z każdym” (bez rewanżów), zgłosiło się drużyn. Zatem każdy mecz w tym turnieju przypisany był do dokładnie jednej pary drużyn wybieranej spośród zgłoszonych.
Wynika stąd, że wszystkich meczów, które w tym turnieju należało rozegrać było tyle, ile wszystkich dwuelementowych kombinacjikombinacji zbioru –elementowego, czyli .
Z pudełka, w którym znajduje się kul ponumerowanych liczbami od do losujemy jednocześnie kule. Wobec tego każdy wynik takiego losowania to trzyelementowa kombinacjakombinacja zbioru dwudziestoelementowego.
Stąd liczba wszystkich możliwych wyników takiego losowania jest równa .
Na okręgu zaznaczono 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 kombinacjakombinacja –elementowego zbioru punktów zaznaczonych na okręgu.
Oznacza to, że wszystkich czworokątów spełniających warunki zadania jest .
Spośród uczniów 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 kombinacjakombinacja zbioru liczącego elementów.
Wynika stąd, że liczba wszystkich delegacji, które można w ten sposób utworzyć jest równa .
W pewnej grze losowej należy wybrać liczb ze zbioru wszystkich dodatnich liczb całkowitych mniejszych od . Oznacza to, że każda wybrana szóstka liczb to sześcioelementowa kombinacjakombinacja zbioru –elementowego.
Liczba tych wyborów jest więc równa
W rozdaniu brydżowym gracz otrzymuje kart wybranych losowo z talii, w której są karty. Wynik takiego rozdania można więc opisać jako –elementową kombinacjękombinację zbioru –elementowego. Wynika stąd, że liczba wszystkich układów kart możliwych do otrzymania przez brydżystę jest równa
Obliczymy, ile jest wszystkich funkcji rosnących, których dziedziną jest zbiór , a zbiorem wartości jest zbiór .
Rozwiązanie
Zauważmy, że każdy sześcioelementowy podzbiór zbioru 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ękombinację zbioru , odpowiadającą zbiorowi wartości tej funkcji.
Wynika stąd, że jest funkcji rosnących ze zbioru do zbioru .
Elektroniczna zabawka ma przycisków, rozmieszczonych po w dwóch rzędach (jak na poniższym rysunku).
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 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 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 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 do , w dolnym rzędzie, również idąc od lewej do prawej, numerami od do , to każda sekwencja kolejno naciśniętych przycisków odpowiada wzajemnie jednoznacznie pewnej permutacjipermutacji zbioru .
Melodyjkę usłyszymy wtedy i tylko wtedy, gdy w tej permutacjipermutacji numery od do pojawią się w porządku wzrastania numerów i jednocześnie numery od do pojawią się w porządku wzrastania numerów – taki warunek spełnia np. permutacjapermutacja . PermutacjęPermutację, która spełnia powyższe warunki nazwijmy dobrą.
Zauważmy zatem, że aby otrzymać permutacjępermutację dobrą należy ustalić w niej miejsc dla numerów od do , 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 do .
Ponieważ każdy wybór numerów ze zbioru to –elementowa kombinacjakombinacja ze zbioru –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 .
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:
wypadły dokładnie reszki.
Wystarczy w tym celu ustalić, na ile sposobów można wybrać miejsca dla elementów 'r' w opisanym powyżej –elementowym ciągu. Ponieważ każdy taki wybór to –elementowa kombinacjakombinacja ze zbioru –elementowego, więc wszystkich możliwych wyników dziewięciokrotnego rzutu monetą, w których wypadły reszki jest
wypadło dokładnie orłów.
Podobnie jak w poprzednim przykładzie ustalimy, na ile sposobów można wybrać miejsc dla elementów 'o' w omawianym –elementowym ciągu. Ponieważ każdy taki wybór to –elementowa kombinacjakombinacja ze zbioru –elementowego, więc wszystkich możliwych wyników dziewięciokrotnego rzutu monetą, w których wypadło orłów jest .
Zauważmy, że każdy wynik dziewięciokrotnego rzutu monetą, w którym w pewnych rzutach wypadł orzeł, jednocześnie opisuje taki wynik, w którym w każdym z pozostałych 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 –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 reszek (gdzie ) jest równa liczbie wszystkich wyników tego doświadczenia, w których wypadło orłów.
Zatem dla dowolnych liczb całkowitych i takich, że zachodzi równość
Algebraiczny dowód tej tożsamości pozostawiamy czytelnikowi jako nietrudne ćwiczenie.
Uwaga 2. Jeśli rozpatrzymy –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ć lub , lub , , lub . Oznacza to, że wszystkich wyników jest
.
Z drugiej strony w każdym z tych rzutów mamy dwie możliwości: otrzymamy orła lub nie otrzymamy orła, zatem wszystkich wyników jest .
Wobec tego dla dowolnych liczb całkowitych i takich, że zachodzi równość
Słownik
każdy –elementowy podzbiór zbioru –elementowego, gdzie , nazywamy –elementową kombinacją tego zbioru –elementowego
liczba wszystkich –elementowych kombinacji zbioru –elementowego, gdzie , jest równa
każdy ciąg utworzony ze wszystkich elementów zbioru –elementowego