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

Rozwiązując złożone zadania z kombinatoryki musimy być bardzo uważni. Nie możemy polegać na powtarzających się algorytmach. Trzeba dobrze zrozumieć opisaną w zadaniu sytuację i dobrać odpowiednią strategię. Prześledźmy sposoby rozwiązywania tego typu zadań na kilku przykładach.

Przykład 1

Na loterię fantową przygotowano 27 ponumerowanych losów, wśród których jest 5 pustych. Z pudełka, w którym te wszystkie losy zostały umieszczone wybieramy jednocześnie 3 sztuki.

Zauważmy, że wynikiem tego losowania jest 3-elementowa kombinacjak-elementowa kombinacja zbioru n-elementowegokombinacja ze zbioru 27-elementowego, a więc wszystkich wyników tego losowania jest 273=27!3!·24!=27·26·253·2·1=2925.

Zauważmy też, że jeżeli w wylosowanej grupie 3 losów ma być dokładnie k losów wygrywających, gdzie 0k3, to jest w niej jednocześnie 3-k losów pustych.

Ponieważ:

  • 22 losy wygrywające, więc wszystkich możliwych wyborów k spośród nich jest tyle, ile jest k-elementowych kombinacji ze zbioru 22-elementowego,

  • jest 5 losów pustych, więc wszystkich możliwych wyborów 3-k spośród nich jest tyle, ile jest 3-k-elementowych kombinacji ze zbioru 5-elementowego.

Wykorzystując te spostrzeżenia oraz regułę mnożeniareguła mnożeniaregułę mnożenia dostajemy stąd, następujące wnioski:

(1) wszystkich możliwości otrzymania w omawianym losowaniu samych losów wygrywających (wtedy k=3) jest 223·50=22!3!·19!·1=22·21·203·2·1=1540,

(2) wszystkich możliwości otrzymania wówczas dokładnie k=2 losów wygrywających (wtedy wraz z nimi jest wśród wylosowanych 1 los pusty) jest 222·51=22!2!·20!·5!1!·4!=22·212·1·5=1155,

(3) wszystkich możliwości otrzymania dokładnie jednego losu wygrywającego (k=1; wtedy wraz z nim wśród wylosowanych są 2 losy puste) jest 221·52=22!1!·21!·5!2!·3!=22·5·42·1=220,

(4) w przypadku k=0 obliczymy wszystkie możliwości otrzymania w tym losowaniu samych losów pustych - jest ich 220·53=1·5!3!·2!=5·42·1=10.

Ponieważ cztery wyżej wymienione przypadki są rozłączne i jednocześnie opisują wszystkie możliwe wyniki omawianego losowania, więc zachodzi następująca równość:

273=223·50+222·51+221·52+220·53,

którą - wobec obliczeń przeprowadzonych powyżej - łatwo można zweryfikować.

Uwaga. Jeśli rozpatrzymy loterię, w której jest n+k losów, z czego n jest wygrywających, to - rozumując podobnie jak w powyższym przykładzie - stwierdzimy, że liczba wszystkich możliwości wylosowanialiczba wszystkich k–elementowych kombinacji zbioru n-elementowegoliczba wszystkich możliwości wylosowania spośród nich m losów może być zapisana na dwa sposoby:

  • jako n+km

  • lub w rozbiciu na rozłączne przypadki, zależne od liczby wylosowanych losów wygrywających, jako suma nm·k0+nm-1·k1++n0·km.

Stąd wniosek, że dla dowolnych nieujemnych liczb całkowitych nk oraz m prawdziwa jest równość (nazywana tożsamością Cauchy'ego lub tożsamością/splotem Vandermonde'a)

n+km=i=0mnm-i·ki.

Przykład 2

Ze zbioru 1,2,3,,22 dwudziestu dwóch początkowych dodatnich liczb całkowitych losujemy jednocześnie pięć liczb. Obliczymy, ile jest wszystkich możliwości wylosowania takich pięciu liczb, których:

  • (a) iloczyn jest parzysty.

  • (b) suma jest nieparzysta.

Rozwiązanie

(a) Każdy wynik losowania 5 liczb spośród 22 jest pięcioelementową kombinacjąk-elementowa kombinacja zbioru n-elementowegokombinacją ze zbioru 22-elementowego, zatem wszystkich wyników takiego doświadczenia jest 225. Iloczyn tak wylosowanych liczb może być albo parzysty, albo nieparzysty. W tym drugim przypadku każda z wylosowanych liczb musi być nieparzysta, a skoro wśród losowanych liczb jest 11 liczb nieparzystych, to takich możliwości jest 115.

Zatem jest 225-115=22·21·20·19·185·4·3·2·1-11·10·9·8·75·4·3·2·1=26334-462=25872 wszystkich możliwości wylosowania takich pięciu liczb, których iloczyn jest parzysty.

Uwaga. Ponieważ rozpatrywany iloczyn jest parzysty wtedy i tylko wtedy, gdy co najmniej jeden z jego czynników jest parzysty, więc rozwiązanie można było przeprowadzić analizując cztery rozłączne przypadki ze względu na dodatnią liczbę czynników parzystych. W efekcie otrzymalibyśmy wówczas, że wszystkich możliwości jest

114·111+113·112+112·113+111·114+

+115·110=330·11+165·55+55·165+11·330+462·1=

=3630+9075+9075+3630+462=25872.

Zauważmy, że oba sposoby rozwiązania łączy zależność, którą otrzymamy przyjmując w podanej powyżej tożsamości Cauchy'ego n=k=11 oraz m=5:

11+115=i=05115-i·11i.

Wynika z niej równość

225-115·110=i=15115-i·11i

w której po obu stronach w symboliczny sposób zapisana jest liczba 25872, będąca odpowiedzią na pytanie zadane w poleceniu.

(b) Ponieważ suma pięciu wylosowanych liczb jest nieparzysta wtedy i tylko wtedy, gdy jest wśród nich nieparzysta liczba składników nieparzystych, więc należy rozpatrzyć następujące trzy rozłączne przypadki:

  • wśród wylosowanych liczb jest jedna nieparzysta (zatem wraz z nią są cztery liczby parzyste); takich możliwości jest 111·114,

  • wśród wylosowanych liczb są trzy nieparzyste (zatem wraz z nimi są dwie liczby parzyste); takich możliwości jest 113·112,

  • wszystkie wylosowane liczby są nieparzyste; takich możliwości jest 115.

Wynika stąd, że liczba wszystkich możliwości wylosowania takich pięciu liczb, których suma jest nieparzysta jest równa

111·114+113·112+115=3630+9075+462=13167.

Uwaga. Pomysł na rozwiązanie można było przeprowadzić również zgodnie z poniższymi obliczeniami:

225-110·115+112·113+114·111==26334-462+3630+9075=13167.

Natomiast zamieniając w wylosowanej piątce liczb każdą wylosowaną liczbę l na liczbę 23-l znajdziemy podstawę do skorzystania z reguły równolicznościReguła równolicznościreguły równoliczności. A z tego wynika, że szukaną liczbę możliwych wyników możemy również zapisać jako

12·225=12·26334=13167.

Przykład 3

Grupa 12 chłopców wybrała się na pięciodniową wycieczkę. Kiedy dotarli na pierwszy nocleg okazało się, że mają do dyspozycji 3 pokoje czteroosobowe. Kwaterując się na drugi nocleg mieli do dyspozycji  4 pokoje trzyosobowe. Kiedy przybyli na trzeci nocleg okazało się, że mają do dyspozycji jeden pokój pięcioosobowy, jeden czteroosobowy i jeden trzyosobowy. Natomiast gdy przybyli na czwarty nocleg okazało się, że mają do dyspozycji jeden pokój siedmioosobowy, jeden trzyosobowy i jeden dwuosobowy.

Na ile sposobów ta grupa chłopców mogła podzielić się w każdym przypadku stosownie do dostępnego zakwaterowania?

Rozwiązanie

Pierwszego dnia należało podzielić tę dwunastoosobową grupę następująco:

  • do pierwszego pokoju wybieramy 4 chłopców spośród wszystkich 12, co można zrobić na 124 sposobów,

  • do drugiego pokoju wybieramy 4 chłopców spośród pozostałych 8, co można zrobić na 84 sposobów,

  • w trzecim pokoju kwaterujemy 4 pozostałych chłopców.

Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia otrzymujemy więc, że wszystkich możliwych sposobów zakwaterowania było w tym przypadku

124·84=12!4!·8!·8!4!·4!=34650.

Podział drugiego dnia miał być z kolei taki:

  • do pierwszego pokoju wybieramy 3 chłopców spośród wszystkich 12, co można zrobić na 123 sposobów,

  • do drugiego pokoju wybieramy 3 chłopców spośród pozostałych 9, co można zrobić na 93 sposobów,

  • do trzeciego pokoju wybieramy 3 chłopców spośród pozostałych 6, co można zrobić na 63 sposobów,

  • w czwartym pokoju kwaterujemy 3 pozostałych chłopców.

Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia otrzymujemy więc, że wszystkich możliwych sposobów zakwaterowania było tym razem 123·93·63=12!3!·9!·9!3!·6!·6!3!·3!=369600.

Rozumując podobnie, jak w dwóch poprzednich przypadkach stwierdzimy, że:

  • trzeciego dnia wszystkich możliwych sposobów zakwaterowania tych 12 chłopców było

    125·74=12!5!·7!·7!4!·3!=27720,

  • czwartego dnia możliwych sposobów zakwaterowania tej grupy było

    127·53=12!7!·5!·5!3!·2!=7920.

Uwaga 1. Jeśli dane są dodatnia liczba całkowita n oraz k takich dodatnich liczb całkowitych n1,n2,,nk, że

n1+n2++nk=n,

to liczba wszystkich  podziałów zbioru n-elementowego na rozłączne, oddzielnie identyfikowane podzbiory: pierwszy, który ma n1 elementów, drugi, który ma n2 elementów, itd. aż do k-tego podzbioru, który ma nk elementów, jest równa

nn1·n-n1n2··n-n1--nk-1nk=n!n1!·n2!··nk!.

Uwaga 2. Jeżeli przy podziale wymienionym powyżej podzbiory nie są oddzielnie identyfikowane, to należy zwrócić uwagę na to, aby nie zliczać wielokrotnie tych samych przypadków.

Nawiązując m.in. do podziałów omawianych w powyższym przykładzie obliczymy wtedy, że:

  • jest 124·843!=346506=5775 możliwości podziału zbioru 12-elementowego na trzy rozłączne podzbiory 4-elementowe,

  • jest 123·93·634!=36960024=15400 możliwości podziału zbioru 12-elementowego na cztery rozłączne podzbiory 3-elementowe,

  • jest 122·102·82·62·426!=10395 możliwości podziału zbioru 12-elementowego na sześć rozłącznych podzbiorów dwuelementowych,

  • jest 125·74=27720 możliwości podziału zbioru 12-elementowego na rozłączne podzbiory: 5-elementowy, 4-elementowy oraz 3-elementowy,

  • jest 127·53=7920 możliwości podziału zbioru 12-elementowego na rozłączne podzbiory: 7-elementowy, 3-elementowy oraz 2-elementowy,

  • jest 123·932!=184802=9240 możliwości podziału zbioru 12-elementowego na rozłączne podzbiory: dwa 3-elementowe oraz podzbiór 6-elementowy.

Przykład 4

Obliczymy, ile jest dwudziestocyfrowych liczb naturalnych, które spełniają następujące trzy warunki:

  • suma ich cyfr w zapisie dziesiętnym jest równa 7,

  • pierwsza cyfra jest nieparzysta,

  • wszystkie pozostałe cyfry są parzyste.

Rozwiązanie

Rozpatrujemy rozłączne przypadki ze względu na pierwszą cyfrę zapisu dziesiętnego szukanej liczby.

(1) pierwszą cyfrą jest 1; mamy wtedy następujące rozłączne przypadki rozkładu pozostałych 19 cyfr:

(1.1) jest wśród nich jedna cyfra 6, a pozostałe cyfry to zera,

(1.2) jest wśród nich jedna cyfra 4, jedna cyfra 2, a pozostałe cyfry to zera,

(1.3) są wśród nich trzy cyfry 2, a pozostałe cyfry to zera,

(2) pierwszą cyfrą jest 3; mamy wtedy następujące rozłączne przypadki rozkładu pozostałych 19 cyfr:

(2.1) jest wśród nich jedna cyfra 4, a pozostałe cyfry to zera,

(2.2) są wśród nich dwie cyfry 2, a pozostałe cyfry to zera,

(3) pierwszą cyfrą jest 5; wtedy jedną z pozostałych 19 cyfr jest 2, a pozostałe cyfry to zera,

(4) pierwszą cyfrą jest 7; wtedy każdą z pozostałych 19 cyfr jest 0.

Obliczamy, ile jest liczb spełniających warunki zadania w każdym z powyżej opisanych przypadków.

(1.1): miejsce dla cyfry 6 wybierzemy na 191 sposobów, a pozostałe 18 miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku 19.

(1.2): miejsce dla cyfry 4 wybierzemy na 191 sposobów, miejsce dla cyfry 2 wybierzemy na 181 sposobów, a pozostałe 17 miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku 191·181=19·18=342.

(1.3): miejsca dla trzech cyfr 2 wybierzemy na 193 sposobów, a pozostałe 16 miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku 193=969.

(2.1): miejsce dla cyfry 4 wybierzemy na 191 sposobów, a pozostałe 18 miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku 19.

(2.2): miejsca dla dwóch cyfr 2 wybierzemy na 192 sposobów, a pozostałe 17 miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku 192=171.

(3): miejsce dla cyfry 2 wybierzemy na 191 sposobów, a pozostałe 18 miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku 19.

(4): pozostaje nam uzupełnić 19 miejsc zerami, więc w tym przypadku jest 1 liczba spełniająca warunki zadania.

Oznacza to, że jest 19+342+969+19+171+19+1=1540 wszystkich dwudziestocyfrowych liczb naturalnych, które spełniają warunki zadania.

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

reguła mnożenia
reguła mnożenia

liczba wszystkich możliwych wyników doświadczenia polegającego na wykonaniu po kolei n czynności, z których pierwsza może zakończyć się na jeden z k1 sposobów, druga – na jeden z k2 sposobów, trzecia – na jeden z k3 sposobów i tak dalej do n-tej czynności, która może zakończyć się na jeden z kn sposobów, jest równa

k1·k2··kn

reguła równoliczności
reguła równoliczności

dwa zbiory AB są równoliczne (mają tyle samo elementów) jeżeli ich elementy można przyporządkować wzajemnie jednoznacznie, to znaczy: każdemu elementowi zbioru A przyporządkujemy dokładnie jeden element zbioru B oraz każdemu elementowi zbioru B przyporządkujemy dokładnie jeden element zbioru A