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.
Na loterię fantową przygotowano ponumerowanych losów, wśród których jest pustych. Z pudełka, w którym te wszystkie losy zostały umieszczone wybieramy jednocześnie sztuki.
Zauważmy, że wynikiem tego losowania jest –elementowa kombinacja ze zbioruelementowa kombinacja ze zbioru –elementowego, a więc wszystkich wyników tego losowania jest .
Zauważmy też, że jeżeli w wylosowanej grupie losów ma być dokładnie losów wygrywających, gdzie , to jest w niej jednocześnie losów pustych.
Ponieważ:
są losy wygrywające, więc wszystkich możliwych wyborów spośród nich jest tyle, ile jest –elementowych kombinacji ze zbioru –elementowego,
jest losów pustych, więc wszystkich możliwych wyborów spośród nich jest tyle, ile jest –elementowych kombinacji ze zbioru –elementowego.
Wykorzystując te spostrzeżenia oraz regułę mnożeniaregułę mnożenia, dostajemy stąd, następujące wnioski:
wszystkich możliwości otrzymania w omawianym losowaniu samych losów wygrywających (wtedy ) jest ,
wszystkich możliwości otrzymania wówczas dokładnie losów wygrywających (wtedy wraz z nimi jest wśród wylosowanych los pusty) jest ,
wszystkich możliwości otrzymania dokładnie jednego losu wygrywającego (; wtedy wraz z nim wśród wylosowanych są losy puste) jest ,
w przypadku obliczymy wszystkie możliwości otrzymania w tym losowaniu samych losów pustych – jest ich .
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ść:
,
którą – wobec obliczeń przeprowadzonych powyżej – łatwo można zweryfikować.
Uwaga! Jeśli rozpatrzymy loterię, w której jest losów, z czego jest wygrywających, to – rozumując podobnie jak w powyższym przykładzie – stwierdzimy, że liczba wszystkich możliwości wylosowania spośród nichmożliwości wylosowania spośród nich losów może być zapisana na dwa sposoby:
jako
lub w rozbiciu na rozłączne przypadki, zależne od liczby wylosowanych losów wygrywających, jako suma .
Stąd wniosek, że dla dowolnych nieujemnych liczb całkowitych , oraz prawdziwa jest równość (nazywana tożsamością Cauchy'ego lub tożsamością/splotem Vandermonde'a)
.
Ze zbioru 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:
iloczyn jest parzysty,
suma jest nieparzysta.
Rozwiązanie
Każdy wynik losowania liczb spośród jest pięcioelementową kombinacją ze zbioru –elementowego, zatem wszystkich wyników takiego doświadczenia jest . 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 liczb nieparzystych, to takich możliwości jest .
Zatem jest 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
.
Zauważmy, że oba sposoby rozwiązania łączy zależność, którą otrzymamy przyjmując w podanej powyżej tożsamości Cauchy'ego oraz :
.
Wynika z niej równość
,
w której po obu stronach w symboliczny sposób zapisana jest liczba , będąca odpowiedzią na pytanie zadane w poleceniu.
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 ,
wśród wylosowanych liczb są trzy nieparzyste (zatem wraz z nimi są dwie liczby parzyste); takich możliwości jest ,
wszystkie wylosowane liczby są nieparzyste; takich możliwości jest .
Wynika stąd, że liczba wszystkich możliwości wylosowania takich pięciu liczb, których suma jest nieparzysta jest równa
.Uwaga! Pomysł na rozwiązanie można było przeprowadzić również zgodnie z poniższymi obliczeniami:
.
Natomiast zamieniając w wylosowanej piątce liczb każdą wylosowaną liczbę na liczbę znajdziemy podstawę do skorzystania z reguły równolicznościreguły równoliczności. A z tego wynika, że szukaną liczbę możliwych wyników możemy również zapisać jako
.
Grupa chłopców wybrała się na pięciodniową wycieczkę. Kiedy dotarli na pierwszy nocleg okazało się, że mają do dyspozycji pokoje czteroosobowe. Kwaterując się na drugi nocleg mieli do dyspozycji 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 chłopców spośród wszystkich , co można zrobić na sposobów,
do drugiego pokoju wybieramy chłopców spośród pozostałych , co można zrobić na sposobów,
w trzecim pokoju kwaterujemy pozostałych chłopców.
Korzystając z reguły mnożeniareguły mnożenia, otrzymujemy więc, że wszystkich możliwych sposobów zakwaterowania było w tym przypadku
.
Podział drugiego dnia miał być z kolei taki:
do pierwszego pokoju wybieramy chłopców spośród wszystkich , co można zrobić na sposobów,
do drugiego pokoju wybieramy chłopców spośród pozostałych , co można zrobić na sposobów,
do trzeciego pokoju wybieramy chłopców spośród pozostałych , co można zrobić na sposobów,
w czwartym pokoju kwaterujemy pozostałych chłopców.
Korzystając z reguły mnożeniareguły mnożenia, otrzymujemy więc, że wszystkich możliwych sposobów zakwaterowania było tym razem .
Rozumując podobnie, jak w dwóch poprzednich przypadkach stwierdzimy, że:
trzeciego dnia wszystkich możliwych sposobów zakwaterowania tych chłopców było
,
czwartego dnia możliwych sposobów zakwaterowania tej grupy było
.
Uwaga 1. Jeśli dane są dodatnia liczba całkowita oraz takich dodatnich liczb całkowitych , że
,
to liczba wszystkich podziałów zbioru]\pojecie‑ref={liczba wszystkich k‑elementowych kombinacji zbioru n‑elementowego} –elementowego na rozłączne, oddzielnie identyfikowane podzbiory: pierwszy, który ma elementów, drugi, który ma elementów, itd. aż do –tego podzbioru, który ma elementów, jest równa
.
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 możliwości podziału zbioru –elementowego na trzy rozłączne podzbiory –elementowe,
jest możliwości podziału zbioru –elementowego na cztery rozłączne podzbiory –elementowe,
jest możliwości podziału zbioru –elementowego na sześć rozłącznych podzbiorów dwuelementowych,
jest możliwości podziału zbioru –elementowego na rozłączne podzbiory: –elementowy, –elementowy oraz –elementowy,
jest możliwości podziału zbioru –elementowego na rozłączne podzbiory: –elementowy, –elementowy oraz –elementowy,
jest możliwości podziału zbioru –elementowego na rozłączne podzbiory: dwa –elementowe oraz podzbiór –elementowy.
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 ,
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.
Pierwszą cyfrą jest ; mamy wtedy następujące rozłączne przypadki rozkładu pozostałych cyfr:
jest wśród nich jedna cyfra , a pozostałe cyfry to zera,
jest wśród nich jedna cyfra , jedna cyfra , a pozostałe cyfry to zera,
są wśród nich trzy cyfry , a pozostałe cyfry to zera.
Pierwszą cyfrą jest ; mamy wtedy następujące rozłączne przypadki rozkładu pozostałych cyfr:
jest wśród nich jedna cyfra , a pozostałe cyfry to zera,
są wśród nich dwie cyfry , a pozostałe cyfry to zera,
pierwszą cyfrą jest ; wtedy jedną z pozostałych cyfr jest , a pozostałe cyfry to zera,
pierwszą cyfrą jest ; wtedy każdą z pozostałych cyfr jest .
Obliczamy, ile jest liczb spełniających warunki zadania w każdym z powyżej opisanych przypadków.
Przypadek pierwszy:
miejsce dla cyfry wybierzemy na sposobów, a pozostałe miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku ,
miejsce dla cyfry wybierzemy na sposobów, miejsce dla cyfry wybierzemy na sposobów, a pozostałe miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku ,
miejsca dla trzech cyfr wybierzemy na sposobów, a pozostałe miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku .
Przypadek drugi:
miejsce dla cyfry wybierzemy na sposobów, a pozostałe miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku ,
miejsca dla dwóch cyfr wybierzemy na sposobów, a pozostałe miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku ,
miejsce dla cyfry wybierzemy na sposobów, a pozostałe miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku ,
pozostaje nam uzupełnić miejsc zerami, więc w tym przypadku jest liczba spełniająca warunki zadania.
Oznacza to, że jest wszystkich dwudziestocyfrowych liczb naturalnych, które spełniają warunki zadania.
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
liczba wszystkich możliwych wyników doświadczenia polegającego na wykonaniu po kolei czynności, z których pierwsza może zakończyć się na jeden z sposobów, druga – na jeden z sposobów, trzecia – na jeden z sposobów i tak dalej do –tej czynności, która może zakończyć się na jeden z sposobów, jest równa
dwa zbiory i są równoliczne (mają tyle samo elementów) jeżeli ich elementy można przyporządkować wzajemnie jednoznacznie, to znaczy: każdemu elementowi zbioru przyporządkujemy dokładnie jeden element zbioru oraz każdemu elementowi zbioru przyporządkujemy dokładnie jeden element zbioru