Wróć do informacji o e-podręczniku Wydrukuj Zapisz jako PDF Udostępnij materiał

Rozpatrzmy n-elementowy zbiór A.

Liczbę wszystkich k-elementowych podzbiorów zbioru A, gdzie 0kn, oznaczamy symbolem nk, co czytamy „n po k” lub „n nad k”.

Zauważmy, że elementy każdego k-elementowego podzbioru, dowolnie wybranego spośród opisanych powyżej, możemy rozmieścić na k! sposobów - otrzymamy wtedy wszystkie możliwe permutacje tego podzbioru k-elementowego. Jeżeli tę czynność powtórzymy dla wszystkich nk podzbiorów, to w efekcie otrzymamy wszystkie k-elementowe wariacje bez powtórzeń n-elementowego zbioru A.

Z drugiej strony: wiemy, że jest n!n-k! wszystkich k-elementowych wariacji bez powtórzeń zbioru n-elementowego (gdzie 0kn).

Otrzymujemy stąd równość k!·nk=n!n-k!, co oznacza, że

nk=n!k!·n-k!

dla każdych liczb całkowitych k, n, które spełniają warunek 0kn.

Dla podzbioru pustego (wtedy k=0) zbioru n-elementowego dostajemy w szczególności n0=1.

Ponieważ zbiór n-elementowy nie ma podzbiorów, które mają więcej niż n-elementów, więc gdy dodatnie liczby całkowite n oraz k spełniaja warunek k>n, to nk=0.

k-elementowa kombinacja zbioru n-elementowego
Definicja: k-elementowa kombinacja zbioru n-elementowego

Każdy k-elementowy podzbiór zbioru n-elementowego, gdzie 0kn, nazywamy k-elementową kombinacją tego zbioru n-elementowego.

liczba wszystkich k–elementowych kombinacji zbioru n-elementowego
Twierdzenie: liczba wszystkich k–elementowych kombinacji zbioru n-elementowego

Liczba wszystkich k-elementowych kombinacji zbioru n-elementowego, gdzie 0kn, jest równa

nk=n!k!·n-k!=n·n-1··n-k+11·2··k

Przykład 1

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.

(a) 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 kombinacjik-elementowa kombinacja zbioru n-elementowegokombinacji zbioru 12-elementowego, czyli 122=12!2!·10!=12·112·1=66.

(b) 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 kombinacjak-elementowa kombinacja zbioru n-elementowegokombinacja zbioru dwudziestoelementowego.

Stąd liczba wszystkich możliwych wyników takiego losowania jest równa 203=20!3!·17!=20·19·183·2·1=1140.

(c) 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 kombinacjak-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 254=25!4!·21!=25·24·23·224·3·2·1=12650.

(d) 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 kombinacjak-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 315=31!5!·26!=31·30·29·28·275·4·3·2·1=169 911.

(e) W pewnej grze losowej należy wybrać 6 liczb ze zbioru 1,2,3,,49 wszystkich dodatnich liczb całkowitych mniejszych od 50. Oznacza to, że każda wybrana szóstka liczb to sześcioelementowa kombinacjak-elementowa kombinacja zbioru n-elementowegokombinacja zbioru 49-elementowego.

Liczba tych wyborów jest więc równa 496=49!6!·43!=49·48·47·46·45·446·5·4·3·2·1=13 983 816

(f) 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 5113=52!13!·39!=52·51·50··41·4013·12··2·1=635 013 559 600

Przykład 2

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

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 96=9!6!·3!=9·8·73·2·1=84 funkcji rosnących ze zbioru A do zbioru B.

Przykład 3

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

R1akw8sul7qVT

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 1,2,3,4,5,6,7,8,9,10.

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 6,7,1,8,2,3,4,9,10,5. 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 1,2,3,4,5,6,7,8,9,10 to 5-elementowa kombinacjak-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 105=10·9·8·7·65·4·3·2·1=252.

Przykład 4

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:

(a) 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 kombinacjak-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 94=9!4!·5!=9·8·7·64·3·2·1=126

(b) 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 kombinacjak-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 95=9!5!·4!=9·8·7·64·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 0kn) 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 nk takich, że 0kn zachodzi równość

nk=nn-k

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, ..., lub n. Oznacza to, że wszystkich wyników jest

n0+n1+n2++nn.

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 2n.

Wobec tego dla dowolnych liczb całkowitych nk takich, że 0kn zachodzi równość

k=0nnk=n0+n1+n2++nn=2n

Słownik

k-elementowa kombinacja zbioru n-elementowego
k-elementowa kombinacja zbioru n-elementowego

każdy k-elementowy podzbiór zbioru n-elementowego, gdzie 0kn, nazywamy k-elementową kombinacją tego zbioru n-elementowego

liczba wszystkich k–elementowych kombinacji zbioru n-elementowego
liczba wszystkich k–elementowych kombinacji zbioru n-elementowego

liczba wszystkich k-elementowych kombinacji zbioru n-elementowego, gdzie 0kn, jest równa

nk=n!k!·n-k!=n·n-1··n-k+11·2··k

permutacja zbioru n–elementowego
permutacja zbioru n–elementowego

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