Wróć do informacji o e-podręczniku Wydrukuj Pobierz materiał do PDF Pobierz materiał do EPUB Pobierz materiał do MOBI Zaloguj się, aby dodać do ulubionych Zaloguj się, aby skopiować i edytować materiał Zaloguj się, aby udostępnić materiał Zaloguj się, aby dodać całą stronę do teczki
Oceń projekt

Przeczytaj

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 kombinacja ze zbioruk‑elementowa kombinacja zbioru n‑elementowegoelementowa kombinacja 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 0≤k≤3, to jest w niej jednocześnie 3-k losów pustych.

Ponieważ:

  • są 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 wylosowania spośród nichliczba wszystkich k‑elementowych kombinacji zbioru n‑elementowegomoż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 n, k 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:

  1. iloczyn jest parzysty,

  2. suma jest nieparzysta.

Rozwiązanie

  1. Każdy wynik losowania 5 liczb spośród 22 jest pięcioelementową kombinacją 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.

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

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

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

    3. 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]\pojecie‑ref={liczba wszystkich k‑elementowych kombinacji zbioru n‑elementowego} 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. jest wśród nich jedna cyfra 6, a pozostałe cyfry to zera,

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

    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:

    1. jest wśród nich jedna cyfra 4, a pozostałe cyfry to zera,

    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. Przypadek pierwszy:

    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,

    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,

    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. Przypadek drugi:

    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. 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 0≤k≤n, 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 0≤k≤n, 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 A i B 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

Wprowadzenie
Animacja