5. Kombinacje

Rl3FoRQbmJL04

Czy widzisz różnicę między pytaniem o liczbę możliwych wyborów dwuosobowej delegacji uczniów pewnej klasy, a pytaniem o liczbę możliwych wyborów przewodniczącego i skarbnika tej klasy? W pierwszym przypadku pytamy jedynie o dwuelementowy podzbiór zboru jaki stanowi rozważana klasa. Nie rozróżniamy między sobą członków delegacji.

W tej lekcji będziemy zajmować się podzbiorami ustalonego zbioru. W szczególności będzie nas interesowało, ile jest wśród nich podzbiorów o ustalonej liczbie elementów.

Twoje cele

Nauczysz się rozpoznawać kombinacje w typowych doświadczeniach związanych z wyborami podzbiorów ustalonego zbioru.
Znajomość twierdzenia o liczbie kombinacji pozwoli Ci obliczać, ile jest wyników wymienionych wyżej doświadczeń.
Nauczysz się wykorzystywać powyższą umiejętność do rozwiązywania zadań dotyczących podziału zbioru na podzbiory.

Rozpatrzmy $n$ –elementowy zbiór $A$ .

Liczbę wszystkich $k$ –elementowych podzbiorów zbioru $A$ , gdzie $0 \leq k \leq n$ , oznaczamy symbolem $(\begin{matrix} n \\ k \end{matrix})$ , 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 $(\begin{matrix} n \\ k \end{matrix})$ podzbiorów, to w efekcie otrzymamy wszystkie $k$ –elementowe wariacje bez powtórzeń $n$ –elementowego zbioru $A$ .

Z drugiej strony: wiemy, że jest $\frac{n!}{(n - k)!}$ wszystkich $k$ –elementowych wariacji bez powtórzeń zbioru $n$ –elementowego (gdzie $0 \leq k \leq n$ ).

Otrzymujemy stąd równość $k! \cdot (\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{(n - k)!}$ , co oznacza, że

$(\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{k! \cdot (n - k)!}$

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

Dla podzbioru pustego (wtedy $k = 0$ ) zbioru $n$ –elementowego dostajemy w szczególności $(\begin{matrix} n \\ 0 \end{matrix}) = 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 $(\begin{matrix} n \\ k \end{matrix}) = 0$ .

k

–elementowa kombinacja zbioru

n

–elementowego

Definicja:

k

–elementowa kombinacja zbioru

n

–elementowego

Każdy $k$ –elementowy podzbiór zbioru $n$ –elementowego, gdzie $0 \leq k \leq n$ , 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 $0 \leq k \leq n$ , jest równa

$(\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{k! \cdot (n - k)!} = \frac{n \cdot (n - 1) \cdot \dots \cdot (n - k + 1)}{1 \cdot 2 \cdot \dots \cdot k}$

Przykład 1

Omówimy kilka zastosowań twierdzenia 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ę $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 kombinacji zbioru $12$ –elementowego, czyli $(\begin{matrix} 12 \\ 2 \end{matrix}) = \frac{12!}{2! \cdot 10!} = \frac{12 \cdot 11}{2 \cdot 1} = 66$ .
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 kombinacja zbioru dwudziestoelementowego.
Stąd liczba wszystkich możliwych wyników takiego losowania jest równa $(\begin{matrix} 20 \\ 3 \end{matrix}) = \frac{20!}{3! \cdot 17!} = \frac{20 \cdot 19 \cdot 18}{3 \cdot 2 \cdot 1} = 1140$ .
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 kombinacja $25$ –elementowego zbioru punktów zaznaczonych na okręgu.
Oznacza to, że wszystkich czworokątów spełniających warunki zadania jest $(\begin{matrix} 25 \\ 4 \end{matrix}) = \frac{25!}{4! \cdot 21!} = \frac{25 \cdot 24 \cdot 23 \cdot 22}{4 \cdot 3 \cdot 2 \cdot 1} = 12650$ .
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 kombinacja 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 $(\begin{matrix} 31 \\ 5 \end{matrix}) = \frac{31!}{5! \cdot 26!} = \frac{31 \cdot 30 \cdot 29 \cdot 28 \cdot 27}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 169 911$ .
W pewnej grze losowej należy wybrać $6$ liczb ze zbioru $\{1, 2, 3, \dots, 49\}$ wszystkich dodatnich liczb całkowitych mniejszych od $50$ . Oznacza to, że każda wybrana szóstka liczb to sześcioelementowa kombinacja zbioru $49$ –elementowego.
Liczba tych wyborów jest więc równa $(\begin{matrix} 49 \\ 6 \end{matrix}) = \frac{49!}{6! \cdot 43!} = \frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 13 983 816$
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ę zbioru $52$ –elementowego. Wynika stąd, że liczba wszystkich układów kart możliwych do otrzymania przez brydżystę jest równa $(\begin{matrix} 51 \\ 13 \end{matrix}) = \frac{52!}{13! \cdot 39!} = \frac{52 \cdot 51 \cdot 50 \cdot \dots \cdot 41 \cdot 40}{13 \cdot 12 \cdot \dots \cdot 2 \cdot 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ękombinację zbioru $B$ , odpowiadającą zbiorowi wartości tej funkcji.

Wynika stąd, że jest $(\begin{matrix} 9 \\ 6 \end{matrix}) = \frac{9!}{6! \cdot 3!} = \frac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 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

Ilustracja przedstawia elektroniczną zabawkę. Posiada ona 10 przycisków. rozłożone są po 4 na prawej i lewej stronie zabawki oraz dwa pionowo na środku.

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 kombinacjakombinacja 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 $(\begin{matrix} 10 \\ 5 \end{matrix}) = \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 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:

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 kombinacja ze zbioru $9$ –elementowego, więc wszystkich możliwych wyników dziewięciokrotnego rzutu monetą, w których wypadły $4$ reszki jest $(\begin{matrix} 9 \\ 4 \end{matrix}) = \frac{9!}{4! \cdot 5!} = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2 \cdot 1} = 126$
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 kombinacja ze zbioru $9$ –elementowego, więc wszystkich możliwych wyników dziewięciokrotnego rzutu monetą, w których wypadło $5$ orłów jest $(\begin{matrix} 9 \\ 5 \end{matrix}) = \frac{9!}{5! \cdot 4!} = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2 \cdot 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 $0 \leq k \leq n$ ) 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 $n$ i $k$ takich, że $0 \leq k \leq n$ zachodzi równość

$(\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n \\ n - k \end{matrix})$

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

$(\begin{matrix} n \\ 0 \end{matrix}) + (\begin{matrix} n \\ 1 \end{matrix}) + (\begin{matrix} n \\ 2 \end{matrix}) + \dots + (\begin{matrix} n \\ n \end{matrix})$ .

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 $2^{n}$ .

Wobec tego dla dowolnych liczb całkowitych $n$ i $k$ takich, że $0 \leq k \leq n$ zachodzi równość

$\sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n \\ 0 \end{matrix}) + (\begin{matrix} n \\ 1 \end{matrix}) + (\begin{matrix} n \\ 2 \end{matrix}) + \dots + (\begin{matrix} n \\ n \end{matrix}) = 2^{n}$

Polecenie 1

Zapoznaj się z przedstawioną poniżej animacją. Przeanalizuj zaprezentowane w niej rozwiązanie zadania, w którym pokazane jest, jak obliczyć, ile jest dziesięcioliterowych napisów spełniających jednocześnie dwa warunki.

RZ89TmKf0nWp5

Polecenie 2

Korzystając z przykładu omówionego w animacji, rozwiąż samodzielnie następujące zadanie.

Z ośmiu liter alfabetu: $a$ , $b$ , $c$ , $d$ , $A$ , $B$ , $C$ , $D$ tworzymy ośmioliterowy napis, w którym każda z tych liter występuje dokładnie raz.
Oblicz, ile jest takich napisów, w których litera $A$ znajdzie się przez $B$ , $B$ przed $C$ oraz $C$ przed $D$ , a ponadto odpowiednia mała litera będzie zapisana przed taką samą dużą. Te warunki spełnia np. napis $b a A c B d C D$ .

Zaprezentujemy rozwiązanie sposobem, który nie został wykorzystany w animacji.

Polega on na zapisywaniu w czterech kolejnych etapach par liter:
$a A$ , $b B$ , $c C$ , $d D$ ,
tak, aby utworzony został napis spełniający warunki zadania.

Wówczas:

litery $a$ oraz $A$ możemy zapisać zgodnie z warunkami zadania tylko na $1$ sposób: $a A$ ,
literę $B$ możemy dopisać jedynie na końcu napisu otrzymanego w punkcie pierwszym. Wtedy przed każdą z zapisanych już trzech liter możemy przewidzieć dodatkowe miejsce na literę $b$ . Zatem są $1 \cdot 3 = 3$ sposoby, na które możemy utworzyć napis spełniający warunki zadania, złożony z dwóch par liter $a A$ , $b B$ ,
literę $C$ możemy dopisać jedynie na końcu napisu otrzymanego w punkcie drugim. Wtedy przed każdą z pięciu zapisanych już liter możemy przewidzieć dodatkowe miejsce na literę $c$ . Zatem jest $1 \cdot 3 \cdot 5 = 15$ sposobów, na które możemy utworzyć napis spełniający warunki zadania, złożony z par liter $a A$ , $b B$ , $c C$ ,
literę $D$ możemy dopisać jedynie na końcu napisu otrzymanego w punkcie trzecim. Wtedy przed każdą z siedmiu zapisanych już liter możemy przewidzieć dodatkowe miejsce na literę $d$ . Zatem jest $1 \cdot 3 \cdot 5 \cdot 7 = 105$ sposobów, na które możemy utworzyć napis spełniający wszystkie warunki zadania.

Poniżej zaprezentujemy opis, w którym tworzony jest napis $b a A c B d C D$ .

Etap $I$ :
Najpierw zapisujemy literę $A$ i zauważamy, że jest tylko jedno miejsce, po lewej od $A$ , na którym możemy dopisać literę $a$ ; w ten sposób otrzymaliśmy napis $a A$ .

Etap $II$ :
Dopisujemy literę $B$ – można ją wstawić tylko na końcu napisu otrzymanego w pierwszym etapie.
Następnie zauważamy, że są trzy miejsca, na których można zapisać literę $b$ , te miejsca poniżej zaznaczone są kropką:
$∙ a ∙ A ∙ B$ .
Niezależnie od tego, gdzie wstawimy teraz $b$ , w każdy następnym etapie będzie ta sama liczba kolejnych możliwych wyborów.
Załóżmy więc, że wstawiliśmy $b$ przed $a$ – rozpatrujemy więc dla przykładu napis $b a A B$ , pamiętając, że są $3$ napisy możliwe do otrzymania po drugim etapie.

Etap $III$ :
Dopisujemy literę $C$ – można ją wstawić tylko na końcu napisu otrzymanego po drugim etapie.
Następnie zauważamy, że jest $5$ miejsc (do poprzednich trzech doszły dwa nowe: przed dopisaną literą $b$ oraz przed dopisaną literą $C$ ), na których można zapisać literę $c$ , te miejsca w przykładowym rozmieszczeniu poniżej zaznaczone są kropką
$∙ b ∙ a ∙ A ∙ B ∙ C$ .
Niezależnie od tego, gdzie wstawimy teraz $c$ , w następnym etapie będzie ta sama liczba kolejnych możliwych wyborów.
Załóżmy więc, że wstawiliśmy $c$ między $A$ i $B$ – po trzecim etapie rozpatrujemy więc dla przykładu napis $b a A c B C$ .
Zauważmy, że jest $3 \cdot 5$ wszystkich napisów możliwych do otrzymania po trzecim etapie.

Etap $IV$ :
Dopisujemy literę $D$ – zgodnie z warunkami zadania można ją dopisać tylko na końcu napisu $b a A c B C$ .
Następnie zauważamy, że jest $7$ miejsc, na których można zapisać literę $d$ (do poprzednich pięciu doszły dwa nowe: przed dopisaną literą $c$ oraz przed dopisaną literą $D$ ; te miejsca w przykładowym rozmieszczeniu poniżej zaznaczone są kropką:
$∙ b ∙ a ∙ A ∙ c ∙ B ∙ C ∙ D$ .
Jak widać, mamy $7$ miejsc, na których możemy wstawić literę $d$ . Dla przykładu wstawimy $d$ między $B$ i $C$ . Otrzymany ośmioliterowy napis $b a A c B d C D$ spełnia warunki zadania.
Zatem jest $3 \cdot 5 \cdot 7 = 105$ wszystkich możliwych napisów spełniających warunki zadania.

$105$

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 5

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 zbioruelementowa kombinacja ze zbioru $27$ –elementowego, a więc wszystkich wyników tego losowania jest $(\begin{matrix} 27 \\ 3 \end{matrix}) = \frac{27!}{3! \cdot 24!} = \frac{27 \cdot 26 \cdot 25}{3 \cdot 2 \cdot 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 \leq k \leq 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:

wszystkich możliwości otrzymania w omawianym losowaniu samych losów wygrywających (wtedy $k = 3$ ) jest $(\begin{matrix} 22 \\ 3 \end{matrix}) \cdot (\begin{matrix} 5 \\ 0 \end{matrix}) = \frac{22!}{3! \cdot 19!} \cdot 1 = \frac{22 \cdot 21 \cdot 20}{3 \cdot 2 \cdot 1} = 1540$ ,
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 $(\begin{matrix} 22 \\ 2 \end{matrix}) \cdot (\begin{matrix} 5 \\ 1 \end{matrix}) = \frac{22!}{2! \cdot 20!} \cdot \frac{5!}{1! \cdot 4!} = \frac{22 \cdot 21}{2 \cdot 1} \cdot 5 = 1155$ ,
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 $(\begin{matrix} 22 \\ 1 \end{matrix}) \cdot (\begin{matrix} 5 \\ 2 \end{matrix}) = \frac{22!}{1! \cdot 21!} \cdot \frac{5!}{2! \cdot 3!} = 22 \cdot \frac{5 \cdot 4}{2 \cdot 1} = 220$ ,
w przypadku $k = 0$ obliczymy wszystkie możliwości otrzymania w tym losowaniu samych losów pustych – jest ich $(\begin{matrix} 22 \\ 0 \end{matrix}) \cdot (\begin{matrix} 5 \\ 3 \end{matrix}) = 1 \cdot \frac{5!}{3! \cdot 2!} = \frac{5 \cdot 4}{2 \cdot 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ść:

$(\begin{matrix} 27 \\ 3 \end{matrix}) = (\begin{matrix} 22 \\ 3 \end{matrix}) \cdot (\begin{matrix} 5 \\ 0 \end{matrix}) + (\begin{matrix} 22 \\ 2 \end{matrix}) \cdot (\begin{matrix} 5 \\ 1 \end{matrix}) + (\begin{matrix} 22 \\ 1 \end{matrix}) \cdot (\begin{matrix} 5 \\ 2 \end{matrix}) + (\begin{matrix} 22 \\ 0 \end{matrix}) \cdot (\begin{matrix} 5 \\ 3 \end{matrix})$ ,

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 nichmożliwości wylosowania spośród nich $m$ losów może być zapisana na dwa sposoby:

jako $(\begin{matrix} n + k \\ m \end{matrix})$
lub w rozbiciu na rozłączne przypadki, zależne od liczby wylosowanych losów wygrywających, jako suma $(\begin{matrix} n \\ m \end{matrix}) \cdot (\begin{matrix} k \\ 0 \end{matrix}) + (\begin{matrix} n \\ m - 1 \end{matrix}) \cdot (\begin{matrix} k \\ 1 \end{matrix}) + \dots + (\begin{matrix} n \\ 0 \end{matrix}) \cdot (\begin{matrix} k \\ m \end{matrix})$ .

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)

$(\begin{matrix} n + k \\ m \end{matrix}) = \sum_{i = 0}^{m} (\begin{matrix} n \\ m - i \end{matrix}) \cdot (\begin{matrix} k \\ i \end{matrix})$ .

Przykład 6

Ze zbioru $\{1, 2, 3, \dots, 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:

iloczyn jest parzysty,
suma jest nieparzysta.

Rozwiązanie

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 $(\begin{matrix} 22 \\ 5 \end{matrix})$ . 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 $(\begin{matrix} 11 \\ 5 \end{matrix})$ .
Zatem jest $(\begin{matrix} 22 \\ 5 \end{matrix}) - (\begin{matrix} 11 \\ 5 \end{matrix}) = \frac{22 \cdot 21 \cdot 20 \cdot 19 \cdot 18}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} - \frac{11 \cdot 10 \cdot 9 \cdot 8 \cdot 7}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 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
$(\begin{matrix} 11 \\ 4 \end{matrix}) \cdot (\begin{matrix} 11 \\ 1 \end{matrix}) + (\begin{matrix} 11 \\ 3 \end{matrix}) \cdot (\begin{matrix} 11 \\ 2 \end{matrix}) + (\begin{matrix} 11 \\ 2 \end{matrix}) \cdot (\begin{matrix} 11 \\ 3 \end{matrix}) + (\begin{matrix} 11 \\ 1 \end{matrix}) \cdot (\begin{matrix} 11 \\ 4 \end{matrix}) +$
$+ (\begin{matrix} 11 \\ 5 \end{matrix}) \cdot (\begin{matrix} 11 \\ 0 \end{matrix}) = 330 \cdot 11 + 165 \cdot 55 + 55 \cdot 165 + 11 \cdot 330 + 462 \cdot 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$ :
$(\begin{matrix} 11 + 11 \\ 5 \end{matrix}) = \sum_{i = 0}^{5} (\begin{matrix} 11 \\ 5 - i \end{matrix}) \cdot (\begin{matrix} 11 \\ i \end{matrix})$ .
Wynika z niej równość
$(\begin{matrix} 22 \\ 5 \end{matrix}) - (\begin{matrix} 11 \\ 5 \end{matrix}) \cdot (\begin{matrix} 11 \\ 0 \end{matrix}) = \sum_{i = 1}^{5} (\begin{matrix} 11 \\ 5 - i \end{matrix}) \cdot (\begin{matrix} 11 \\ i \end{matrix})$ ,
w której po obu stronach w symboliczny sposób zapisana jest liczba $25872$ , 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:
1. wśród wylosowanych liczb jest jedna nieparzysta (zatem wraz z nią są cztery liczby parzyste); takich możliwości jest $(\begin{matrix} 11 \\ 1 \end{matrix}) \cdot (\begin{matrix} 11 \\ 4 \end{matrix})$ ,
2. wśród wylosowanych liczb są trzy nieparzyste (zatem wraz z nimi są dwie liczby parzyste); takich możliwości jest $(\begin{matrix} 11 \\ 3 \end{matrix}) \cdot (\begin{matrix} 11 \\ 2 \end{matrix})$ ,
3. wszystkie wylosowane liczby są nieparzyste; takich możliwości jest $(\begin{matrix} 11 \\ 5 \end{matrix})$ .
Wynika stąd, że liczba wszystkich możliwości wylosowania takich pięciu liczb, których suma jest nieparzysta jest równa
$(\begin{matrix} 11 \\ 1 \end{matrix}) \cdot (\begin{matrix} 11 \\ 4 \end{matrix}) + (\begin{matrix} 11 \\ 3 \end{matrix}) \cdot (\begin{matrix} 11 \\ 2 \end{matrix}) + (\begin{matrix} 11 \\ 5 \end{matrix}) = 3630 + 9075 + 462 = 13167$ .
Uwaga! Pomysł na rozwiązanie można było przeprowadzić również zgodnie z poniższymi obliczeniami:
$(\begin{matrix} 22 \\ 5 \end{matrix}) - ((\begin{matrix} 11 \\ 0 \end{matrix}) \cdot (\begin{matrix} 11 \\ 5 \end{matrix}) + (\begin{matrix} 11 \\ 2 \end{matrix}) \cdot (\begin{matrix} 11 \\ 3 \end{matrix}) + (\begin{matrix} 11 \\ 4 \end{matrix}) \cdot (\begin{matrix} 11 \\ 1 \end{matrix})) =$ $= 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
$\frac{1}{2} \cdot (\begin{matrix} 22 \\ 5 \end{matrix}) = \frac{1}{2} \cdot 26334 = 13167$ .

Przykład 7

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 $(\begin{matrix} 12 \\ 4 \end{matrix})$ sposobów,
do drugiego pokoju wybieramy $4$ chłopców spośród pozostałych $8$ , co można zrobić na $(\begin{matrix} 8 \\ 4 \end{matrix})$ 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

$(\begin{matrix} 12 \\ 4 \end{matrix}) \cdot (\begin{matrix} 8 \\ 4 \end{matrix}) = \frac{12!}{4! \cdot 8!} \cdot \frac{8!}{4! \cdot 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 $(\begin{matrix} 12 \\ 3 \end{matrix})$ sposobów,
do drugiego pokoju wybieramy $3$ chłopców spośród pozostałych $9$ , co można zrobić na $(\begin{matrix} 9 \\ 3 \end{matrix})$ sposobów,
do trzeciego pokoju wybieramy $3$ chłopców spośród pozostałych $6$ , co można zrobić na $(\begin{matrix} 6 \\ 3 \end{matrix})$ 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 $(\begin{matrix} 12 \\ 3 \end{matrix}) \cdot (\begin{matrix} 9 \\ 3 \end{matrix}) \cdot (\begin{matrix} 6 \\ 3 \end{matrix}) = \frac{12!}{3! \cdot 9!} \cdot \frac{9!}{3! \cdot 6!} \cdot \frac{6!}{3! \cdot 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
$(\begin{matrix} 12 \\ 5 \end{matrix}) \cdot (\begin{matrix} 7 \\ 4 \end{matrix}) = \frac{12!}{5! \cdot 7!} \cdot \frac{7!}{4! \cdot 3!} = 27720$ ,
czwartego dnia możliwych sposobów zakwaterowania tej grupy było
$(\begin{matrix} 12 \\ 7 \end{matrix}) \cdot (\begin{matrix} 5 \\ 3 \end{matrix}) = \frac{12!}{7! \cdot 5!} \cdot \frac{5!}{3! \cdot 2!} = 7920$ .

Uwaga 1. Jeśli dane są dodatnia liczba całkowita $n$ oraz $k$ takich dodatnich liczb całkowitych $n_{1}, n_{2}, \dots, n_{k}$ , że

$n_{1} + n_{2} + \dots + n_{k} = 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 $n_{1}$ elementów, drugi, który ma $n_{2}$ elementów, itd. aż do $k$ –tego podzbioru, który ma $n_{k}$ elementów, jest równa

$(\begin{matrix} n \\ n_{1} \end{matrix}) \cdot (\begin{matrix} n - n_{1} \\ n_{2} \end{matrix}) \cdot \dots \cdot (\begin{matrix} n - n_{1} - \dots - n_{k - 1} \\ n_{k} \end{matrix}) = \frac{n!}{n_{1}! \cdot n_{2}! \cdot \dots \cdot n_{k}!}$ .

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 $\frac{(\begin{matrix} 12 \\ 4 \end{matrix}) \cdot (\begin{matrix} 8 \\ 4 \end{matrix})}{3!} = \frac{34650}{6} = 5775$ możliwości podziału zbioru $12$ –elementowego na trzy rozłączne podzbiory $4$ –elementowe,
jest $\frac{(\begin{matrix} 12 \\ 3 \end{matrix}) \cdot (\begin{matrix} 9 \\ 3 \end{matrix}) \cdot (\begin{matrix} 6 \\ 3 \end{matrix})}{4!} = \frac{369600}{24} = 15400$ możliwości podziału zbioru $12$ –elementowego na cztery rozłączne podzbiory $3$ –elementowe,
jest $\frac{(\begin{matrix} 12 \\ 2 \end{matrix}) \cdot (\begin{matrix} 10 \\ 2 \end{matrix}) \cdot (\begin{matrix} 8 \\ 2 \end{matrix}) \cdot (\begin{matrix} 6 \\ 2 \end{matrix}) \cdot (\begin{matrix} 4 \\ 2 \end{matrix})}{6!} = 10395$ możliwości podziału zbioru $12$ –elementowego na sześć rozłącznych podzbiorów dwuelementowych,
jest $(\begin{matrix} 12 \\ 5 \end{matrix}) \cdot (\begin{matrix} 7 \\ 4 \end{matrix}) = 27720$ możliwości podziału zbioru $12$ –elementowego na rozłączne podzbiory: $5$ –elementowy, $4$ –elementowy oraz $3$ –elementowy,
jest $(\begin{matrix} 12 \\ 7 \end{matrix}) \cdot (\begin{matrix} 5 \\ 3 \end{matrix}) = 7920$ możliwości podziału zbioru $12$ –elementowego na rozłączne podzbiory: $7$ –elementowy, $3$ –elementowy oraz $2$ –elementowy,
jest $\frac{(\begin{matrix} 12 \\ 3 \end{matrix}) \cdot (\begin{matrix} 9 \\ 3 \end{matrix})}{2!} = \frac{18480}{2} = 9240$ możliwości podziału zbioru $12$ –elementowego na rozłączne podzbiory: dwa $3$ –elementowe oraz podzbiór $6$ –elementowy.

Przykład 8

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.

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

Przypadek pierwszy:
1. miejsce dla cyfry $6$ wybierzemy na $(\begin{matrix} 19 \\ 1 \end{matrix})$ 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 $(\begin{matrix} 19 \\ 1 \end{matrix})$ sposobów, miejsce dla cyfry $2$ wybierzemy na $(\begin{matrix} 18 \\ 1 \end{matrix})$ sposobów, a pozostałe $17$ miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku $(\begin{matrix} 19 \\ 1 \end{matrix}) \cdot (\begin{matrix} 18 \\ 1 \end{matrix}) = 19 \cdot 18 = 342$ ,
3. miejsca dla trzech cyfr $2$ wybierzemy na $(\begin{matrix} 19 \\ 3 \end{matrix})$ sposobów, a pozostałe $16$ miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku $(\begin{matrix} 19 \\ 3 \end{matrix}) = 969$ .
Przypadek drugi:
1. miejsce dla cyfry $4$ wybierzemy na $(\begin{matrix} 19 \\ 1 \end{matrix})$ 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 $(\begin{matrix} 19 \\ 2 \end{matrix})$ sposobów, a pozostałe $17$ miejsc uzupełnimy zerami. Zatem wszystkich możliwości jest w tym przypadku $(\begin{matrix} 19 \\ 2 \end{matrix}) = 171$ ,
3. miejsce dla cyfry $2$ wybierzemy na $(\begin{matrix} 19 \\ 1 \end{matrix})$ 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.

Polecenie 3

Zapoznaj się z przedstawioną poniżej animacją. Przeanalizuj zaprezentowane w niej rozwiązanie zadania, dotyczącego dziesięciocyfrowych liczb naturalnych, których iloczyn cyfr jest równy $84$ .

R1CDGaYZyxROQ

Polecenie 4

Korzystając z pomysłu omówionego w powyższej animacji, oblicz, ile jest dwunastocyfrowych liczb naturalnych, których iloczyn cyfr w zapisie dziesiętnym jest równy $180$ .

Sprawdzamy, że rozkładem na czynniki pierwsze liczby $180$ jest
$180 = 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5$ .

Ponieważ każda z cyfr rozpatrywanej liczby jest dodatnią liczbą całkowitą mniejszą od $10$ , więc jako cyfry tej liczby dopuszczalne są:
$2 \cdot 1 = 2$ ,
$2 \cdot 2 = 4$ ,
$2 \cdot 3 = 6$ ,
$3 \cdot 1 = 3$ ,
$3 \cdot 3 = 9$ ,
$5 \cdot 1 = 5$ .

Otrzymujemy stąd sześć następujących, rozłącznych przypadków.

$180 = 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5 \cdot 1^{7}$
W tym przypadku zliczanie wszystkich możliwości przeprowadzimy w trzech kolejnych etapach:
1. spośród $12$ dostępnych cyfr wybierzemy dwie, którym przypiszemy wartość $2$ – można to zrobić na $(\begin{matrix} 12 \\ 2 \end{matrix})$ sposobów,
2. z pozostałych $10$ cyfr wybierzemy dwie, którym przypiszemy wartość $3$ – można to zrobić na $(\begin{matrix} 10 \\ 2 \end{matrix})$ sposobów,
3. z pozostałych po drugim wyborze $8$ cyfr wybierzemy jedną, której przypiszemy wartość $5$ , a pozostałym na koniec siedmiu cyfrom przypiszemy wartość $1$ – można to zrobić na $8$ sposobów.
Zatem wszystkich możliwości jest w tym przypadku
$(\begin{matrix} 12 \\ 2 \end{matrix}) \cdot (\begin{matrix} 10 \\ 2 \end{matrix}) \cdot 8 = 66 \cdot 45 \cdot 8 = 23760$ .
$180 = (2 \cdot 2) \cdot 3 \cdot 3 \cdot 5 = 4 \cdot 3 \cdot 3 \cdot 5 \cdot 1^{8}$
W tym przypadku zliczanie wszystkich możliwości również przeprowadzimy w trzech kolejnych etapach:
1. spośród $12$ dostępnych cyfr wybierzemy jedną, której przypiszemy wartość $4$ – można to zrobić na $12$ sposobów,
2. z pozostałych $11$ cyfr wybierzemy dwie, którym przypiszemy wartość $3$ – można to zrobić na $(\begin{matrix} 11 \\ 2 \end{matrix})$ sposobów,
3. z pozostałych po drugim wyborze $9$ cyfr wybierzemy jedną, której przypiszemy wartość $5$ , a pozostałym na koniec ośmiu cyfrom przypiszemy wartość $1$ - można to zrobić na $9$ sposobów.
Wobec tego wszystkich możliwości jest w tym przypadku
$12 \cdot (\begin{matrix} 11 \\ 2 \end{matrix}) \cdot 9 = 12 \cdot 55 \cdot 9 = 5940$ .
$180 = (2 \cdot 2) \cdot (3 \cdot 3) \cdot 5 = 4 \cdot 9 \cdot 5 \cdot 1^{9}$
W tym przypadku zliczanie wszystkich możliwości również przeprowadzimy w trzech kolejnych etapach:
1. spośród $12$ dostępnych cyfr wybierzemy jedną, której przypiszemy wartość $4$ – można to zrobić na $12$ sposobów,
2. z pozostałych $11$ cyfr wybierzemy jedną, której przypiszemy wartość $9$ – można to zrobić na $11$ sposobów,
3. z pozostałych po drugim wyborze $10$ cyfr wybierzemy jedną, której przypiszemy wartość $5$ , a pozostałym na koniec dziewięciu cyfrom przypiszemy wartość $1$ - można to zrobić na $10$ sposobów.
Oznacza to, że wszystkich możliwości jest w tym przypadku $12 \cdot 11 \cdot 10 = 1320$ .
$180 = (2 \cdot 3) \cdot 2 \cdot 3 \cdot 5 = 6 \cdot 2 \cdot 3 \cdot 5 \cdot 1^{8}$
W tym przypadku zliczanie wszystkich możliwości przeprowadzimy w czterech kolejnych etapach:
1. spośród $12$ dostępnych cyfr wybierzemy jedną, której przypiszemy wartość $6$ – można to zrobić na $12$ sposobów,
2. z pozostałych $11$ cyfr wybierzemy jedną, której przypiszemy wartość $2$ – można to zrobić na $11$ sposobów,
3. z pozostałych po drugim wyborze $10$ cyfr wybierzemy jedną, której przypiszemy wartość $3$ ,
4. pozostałych po trzecim wyborze $9$ cyfr wybierzemy jedną, której przypiszemy wartość $5$ , a pozostałym na koniec ośmiu cyfrom przypiszemy wartość $1$ - można to zrobić na $9$ sposobów.
Zatem wszystkich możliwości jest w tym przypadku
$12 \cdot 11 \cdot 10 \cdot 9 = 11880$ .
$180 = (2 \cdot 3) \cdot (2 \cdot 3) \cdot 5 = 6 \cdot 6 \cdot 5 \cdot 1^{9}$
W tym przypadku zliczanie wszystkich możliwości przeprowadzimy w dwóch kolejnych etapach:
1. spośród $12$ dostępnych cyfr wybierzemy dwie, którym przypiszemy wartość $6$ – można to zrobić na $(\begin{matrix} 12 \\ 2 \end{matrix})$ sposobów,
2. z pozostałych $10$ cyfr wybierzemy jedną, której przypiszemy wartość $5$ , a pozostałym na koniec dziewięciu cyfrom przypiszemy wartość $1$ - można to zrobić na $10$ sposobów.
Zatem wszystkich możliwości jest w tym przypadku $(\begin{matrix} 12 \\ 2 \end{matrix}) \cdot 10 = 66 \cdot 10 = 660$ .
$180 = 2 \cdot 2 \cdot (3 \cdot 3) \cdot 5 = 2 \cdot 2 \cdot 9 \cdot 5 \cdot 1^{8}$
W tym przypadku zliczanie wszystkich możliwości przeprowadzimy w trzech kolejnych etapach:
1. spośród $12$ dostępnych cyfr wybierzemy jedną, której przypiszemy wartość $9$ – można to zrobić na $12$ sposobów,
2. z pozostałych $11$ cyfr wybierzemy dwie, którym przypiszemy wartość $2$ – można to zrobić na $(\begin{matrix} 11 \\ 2 \end{matrix})$ sposobów,
3. z pozostałych po drugim wyborze $9$ cyfr wybierzemy jedną, której przypiszemy wartość $5$ , a pozostałym na koniec ośmiu cyfrom przypiszemy wartość $1$ - można to zrobić na $9$ sposobów.
Wobec tego wszystkich możliwości jest w tym przypadku $12 \cdot (\begin{matrix} 11 \\ 2 \end{matrix}) \cdot 9 = 12 \cdot 55 \cdot 9 = 5940$ .

Na koniec obliczamy, że jest
$23760 + 5940 + 1320 + 11880 + 660 + 5940 = 49500$
dwunastocyfrowych liczb naturalnych, których iloczyn cyfr w zapisie dziesiętnym jest równy $180$ .

$49500$ .

Na początek przedstawimy kilka nietrudnych zastosowań twierdzenia o liczbie kombinacjitwierdzenia o liczbie kombinacji, które dotyczą zliczania typowych figur płaskich: punktów leżących na prostej, punktów leżących na okręgu, wielokątów i ich przekątnych.

Przykład 9

a) Na płaszczyźnie poprowadzono $15$ prostych tak, że żadne dwie z nich nie są równoległe oraz żadne trzy z nich nie przecinają się w jednym punkcie. Obliczymy, ile jest wszystkich punktów przecięcia się tych prostych.

Rozwiązanie

Z warunków zadania wynika, że każde dwie z rozpatrywanych prostych przecinają się i punkt ich przecięcia jest różny od każdego innego punktu, w którym przecinają się pewne dwie inne proste spośród tych $15$ . Zatem wszystkich punktów przecięcia tych prostych jest tyle, ile jest dwuelementowych kombinacjikombinacji zbioru $15$ –elementowego, czyli $(\begin{matrix} 15 \\ 2 \end{matrix}) = \frac{15 \cdot 14}{2} = 105$

b) Na okręgu zaznaczono $20$ różnych punktów. Obliczymy, ile jest różnych łuków o końcach w tych punktach.

Rozwiązanie

I sposób:

Ponieważ każda para wybrana spośród tych $20$ punktów dzieli okrąg na dwa różne łuki, więc wszystkich różnych łuków jest $2 \cdot (\begin{matrix} 20 \\ 2 \end{matrix}) = 2 \cdot \frac{20 \cdot 19}{2} = 380$ .

II sposób:

Wybieramy jeden z zaznaczonych punktów i oznaczamy go przez $A_{1}$ . Następnie poruszamy się po okręgu zgodnie z ruchem wskazówek zegara i każdy kolejny napotkany punkt indeksujemy, od $A_{2}$ do $A_{20}$ . Zauważmy teraz, że poruszając się zgodnie z ruchem wskazówek zegara każdy z $20$ wierzchołków możemy połączyć z każdym z $19$ pozostałych łukiem i otrzymane w ten sposób łuki będą parami różne. Zatem wszystkich łuków jest $20 \cdot 19 = 380$ .

c) Obliczymy, ile przekątnych ma $n$ –kąt wypukły.

Rozwiązanie

I sposób:

Zauważmy, że dobierając wierzchołki w pary dostaniemy ich tyle, ile jest dwuelementowych kombinacjikombinacji zbioru $n$ –elementowego, czyli $(\begin{matrix} n \\ 2 \end{matrix})$ . Wszystkie te pary punktów dzielimy na dwie rozłączne grupy:

pary, które są końcami pewnego boku wielokąta,

pary, które są końcami pewnej przekątnej wielokąta.

Ponieważ par w pierwszej grupie jest $n$ , więc przekątnych jest $(\begin{matrix} n \\ 2 \end{matrix}) - n = \frac{n \cdot (n - 1)}{2} - n = \frac{n \cdot (n - 1) - 2 n}{2} = \frac{n \cdot (n - 3)}{2}$ .

II sposób:

Zauważmy, że z każdego wierzchołka danego wielokąta można poprowadzić przekątną łącząc go z $(n - 3)$ wierzchołkami (spośród $(n - 1)$ różnych od niego wierzchołków odrzucamy dwa sąsiednie), więc licząc przekątne w każdym wierzchołku dostaniemy ich w sumie $n \cdot (n - 3)$ . Ponieważ każdą przekątną policzyliśmy w ten sposób dwukrotnie (uwzględniliśmy ją w każdym z jej dwóch końców), więc wszystkich przekątnych w $n$ –kącie jest $\frac{n \cdot (n - 3)}{2}$ .

Przykład 10

Na każdym z boków trójkąta $A B C$ zaznaczono po cztery punkty tak, że dzielą one każdy z tych boków na pięć odcinków równej długości. Obliczymy, ile jest wszystkich trójkątów, których wierzchołkami są trzy punkty wybrane spośród tych $12$ zaznaczonych na bokach trójkąta.

Rozwiązanie

Zauważmy na początek, że wybrana trójka punktów to wierzchołki trójkąta (niezdegenerowanego) wtedy i tylko wtedy, gdy nie są to punkty leżące na jednej prostej. Korzystając z tego faktu pokażemy rozwiązanie na dwa sposoby.

I sposób:

Obliczamy, że wszystkich możliwych wyborów trzech punktów spośród $12$ zaznaczonych na bokach trójkąta $A B C$ jest tyle, ile jest $3$ –elementowych kombinacjikombinacji zbioru $12$ –elementowego, czyli $(\begin{matrix} 12 \\ 3 \end{matrix}) = \frac{12 \cdot 11 \cdot 10}{3 \cdot 2 \cdot 1} = 220$ .

Ponieważ wśród wyborów opisanych powyżej trzy punkty na jednej prostej dostaniemy, gdy będą one leżały na jednym z boków trójkąta $A B C$ , więc jest ich w sumie $3 \cdot (\begin{matrix} 4 \\ 3 \end{matrix}) = 3 \cdot 4 = 12$ .

Wynika stąd, że trójkątów spełniających warunki zadania jest $220 - 12 = 208$ .

II sposób:

Warunki zadania będą spełnione, gdy wybierzemy trzy punkty w dwóch następujących, rozłącznych przypadkach:

$(1)$ kiedy dwa z nich leżą na jednym z boków trójkąta $A B C$ , a trzeci – na jednym z dwóch pozostałych boków,

$(2)$ kiedy każdy z tych trzech punktów leży na innym boku trójkąta $A B C$ .

W przypadku $(1)$ obliczenia przeprowadzamy w trzech kolejnych etapach: najpierw ustalamy jeden z trzech boków trójkąta $A B C$ , następnie wybieramy na nim dwa punkty z dostępnych czterech, a następnie z pozostałych $8$ dostępnych punktów na innych dwóch bokach tego trójkąta wybieramy jeden. Zatem w tym przypadku wszystkich możliwości jest $3 \cdot (\begin{matrix} 4 \\ 2 \end{matrix}) \cdot (\begin{matrix} 8 \\ 1 \end{matrix}) = 3 \cdot 6 \cdot 8 = 144$ .

W przypadku $(2)$ mamy wybrać po jednym punkcie z czterech dostępnych na każdym z boków trójkąta $A B C$ , więc tym razem wszystkich możliwości jest $(\begin{matrix} 4 \\ 1 \end{matrix}) \cdot (\begin{matrix} 4 \\ 1 \end{matrix}) \cdot (\begin{matrix} 4 \\ 1 \end{matrix}) = 4 \cdot 4 \cdot 4 = 64$ .

Oznacza to, że wszystkich trójkątów, które spełniają warunki zadania jest $144 + 64 = 208$ .

Przykład 11

Prostokąt $A B C D$ , w którym $|A B| = 8$ , $|A D| = 11$ , podzielono prostymi równoległymi do boków na $88$ kwadracików jednostkowych, jak na poniższym rysunku.

R1LPZJPhhSLLK

Ilustracja przedstawia prostokąt A B C D. W środku znajduję się 88 jednakowych kwadracików.

Obliczymy, ile jest prostokątów, których boki zawierają się w liniach otrzymanej w ten sposób siatki.

Rozwiązanie

Ponumerujmy widoczne na rysunku linie otrzymanej siatki:

pionowe, od $1$ do $9$ ,

poziome, od $1$ do $12$ .

R1WQwj0ePyeec

Ilustracja przedstawia prostokąt A B C D. W środku znajduję się 88 jednakowych kwadracików. Bok A D podpisano cyframi od jeden do 12, a bok A B podpisano od 1 do 9

Zauważmy, że każdy prostokąt narysowany zgodnie z warunkami zadania możemy przypisać do dwóch par liczb: pary „czerwonej”, wybranej spośród numerów przypisanych do linii pionowych oraz pary „niebieskiej”, wybranej spośród numerów przypisanych do linii poziomych.
Jeżeli umówimy się, że podając te dwie pary dla identyfikacji prostokąta jako pierwszą zapiszemy parę „czerwoną”, to zapis $(\{2, 7\}, \{3, 8\})$ opisuje prostokąt, którego dwa boki pionowe leżą na liniach o numerach $2$ oraz $7$ , a dwa boki poziome – na liniach o numerach $3$ oraz $8$ .

R15OqJKrKsKgM

Zauważmy, że istotne jest ustalenie porządku przy wypisywaniu par omówionych wyżej – dwójka par $(\{2, 7\}, \{3, 8\})$ opisuje inny prostokąt, niż dwójka par $(\{3, 8\}, \{2, 7\})$ – ten drugi prostokąt prezentujemy poniżej.

RpahKWtnRJPzB

Z drugiej strony: jeżeli najpierw narysujemy prostokąt spełniający warunki zadania, to jemu przypiszemy dokładnie jedną dwójkę uporządkowanych jak wyżej par liczb. Zatem to przyporządkowanie:
prostokąt – dwójka par
jest wzajemnie jednoznaczne.
Wobec tego dla rozwiązania zadania wystarczy obliczyć, ile jest dwójek par liczb opisanych powyżej.

Ponieważ liczby w parze „czerwonej” wybierzemy na $(\begin{matrix} 9 \\ 2 \end{matrix})$ sposobów, a liczby w parze „niebieskiej” – na $(\begin{matrix} 12 \\ 2 \end{matrix})$ sposobów, więc korzystając z reguły mnożeniaReguła mnożeniareguły mnożenia obliczymy, że wszystkich prostokątów, których boki zawierają się w liniach otrzymanej w ten sposób siatki jest $(\begin{matrix} 9 \\ 2 \end{matrix}) \cdot (\begin{matrix} 12 \\ 2 \end{matrix}) = 36 \cdot 66 = 2376$ .

Przykład 12

Rozpatrzmy wszystkie trójkąty, których wierzchołki są wybrane spośród wszystkich wierzchołków piętnastokąta foremnego. Obliczymy, ile jest wśród nich trójkątów nierównoramiennych.

Rozwiązanie

Ponieważ żadne trzy wierzchołki piętnastokąta foremnego nie leżą na jednej prostej, więc wszystkich trójkątów, których wierzchołki są wybrane spośród wierzchołków piętnastokąta foremnego jest $(\begin{matrix} 15 \\ 3 \end{matrix}) = \frac{15 \cdot 14 \cdot 13}{3 \cdot 2 \cdot 1} = 455$ . Obliczymy, ile jest wśród nich trójkątów równoramiennych.

Zauważmy, że w trójkącie równoramiennym wpisanym w okrąg prosta przechodząca przez środek tego okręgu i wierzchołek między ramionami trójkąta jest osią symetrii tego trójkąta. Zauważmy też, że żadne dwa wierzchołki piętnastokąta foremnego nie leżą na osi symetrii okręgu opisanego na tym wielokącie.

Oznaczmy wierzchołki rozpatrywanego piętnastokąta przez $A_{1}$ , $A_{2}$ , $. . .$ , $A_{15}$ . Wybierzmy dla przykładu wierzchołek $A_{8}$ i poprowadźmy prostą przez środek $O$ okręgu opisanego na piętnastokącie $A_{1} A_{2} A_{3} . . . A_{15}$ .

RVjZtQBxCUxPp

Ilustracja przedstawia okrąg o środku O. Wpisano w niego piętnastokąt z wierzchołkami od A indeks dolny jeden koniec indeksu do A indeks dolny 15 koniec indeksu.

Zauważmy, że pozostałe $14$ wierzchołków można podzielić na $7$ par tak, aby każda para wraz z $A_{8}$ tworzyła trzy wierzchołki trójkąta równoramiennego. Są to pary: $A_{1} A_{15}$ , $A_{2} A_{14}$ , $A_{3} A_{13}$ , $A_{4} A_{12}$ , $A_{5} A_{11}$ , $A_{6} A_{10}$ oraz $A_{7} A_{9}$ .

R19BePUr2Go0Y

Jedna z tych par, $A_{3} A_{13}$ , wraz z $A_{8}$ daje trójkę wierzchołków trójkąta równobocznego.

RwdCBwRLjyYJb

Wobec tego jest $6$ trójkątów równoramiennych, w których $A_{8}$ to jedyny wierzchołek między równymi bokami.

Powtarzając to rozumowanie dla każdego z wierzchołków piętnastokąta foremnego stwierdzimy, że w sytuacji opisanej w zadaniu:

jest $15 \cdot 6 = 90$ nierównobocznych trójkątów równoramiennych,

jest $\frac{15}{3} = 5$ trójkątów równobocznych.

Wynika stąd, że wszystkich trójkątów równoramiennych, których wierzchołki są wybrane spośród wszystkich wierzchołków piętnastokąta foremnego jest $90 + 5 = 95$ .

Zatem wszystkich trójkątów nierównoramiennych spełniających warunki zadania jest $(\begin{matrix} 15 \\ 3 \end{matrix}) - 95 = 455 - 95 = 360$ .

Przykład 13

Rozpatrzmy wszystkie trapezy, których wierzchołki są wybrane spośród wierzchołków szesnastokąta foremnego. Obliczymy, ile jest wśród nich takich czworokątów, które nie są prostokątami.

Rozwiązanie

Zauważmy, że w każdy trapez wpisany w okrąg jest równoramienny, więc ma oś symetrii, która przechodzi przez środek tego okręgu.
Rozpatrzmy trapezy, których wierzchołki są wybrane spośród wszystkich wierzchołków szesnastokąta foremnego. Możemy je podzielić na dwie grupy ze względu na liczbę wierzchołków szesnastokąta, które leżą na osi symetrii rozpatrywanego trapezu.
$(1)$ na osi symetrii trapezu nie leży żaden z wierzchołków szesnastokąta.

RDwSNCPWX39yd

Ilustracja przedstawia okrąg o środku O. Wpisano w niego szesnastokąt z wierzchołkami od A indeks dolny jeden koniec indeksu do A indeks dolny 16 koniec indeksu.

Wtedy dla wybranej osi symetrii, np. będącej symetralną boku $A_{1} A_{16}$ , wszystkie $16$ wierzchołków rozpatrywanego wielokąta można podzielić na $8$ par odcinków, dla każdego z których ta symetralna jest osią symetrii.

R185UnTn7aP6q

Zatem jest $(\begin{matrix} 8 \\ 2 \end{matrix}) = 28$ wszystkich trapezów, których osią symetrii jest ustalona symetralna.

Zauważmy, że wśród tych trapezów są $4$ prostokąty.

R164GO6BNd1ag

Oznacza to, że dla ustalonej w tym przypadku osi symetrii są $24$ trapezy, niebędące prostokątami.
Powtarzając to rozumowanie dla każdej z $\frac{16}{2} = 8$ osi symetrii otrzymamy tym razem $24 \cdot 8 = 192$ trapezy spełniające warunki zadania.

$(2)$ na osi symetrii trapezu leżą dokładnie dwa wierzchołki szesnastokąta.

R8PgF1KQzGyqJ

Wtedy dla wybranej osi symetrii, np. prostej $A_{1} A_{9}$ , wszystkie $14$ pozostałych wierzchołków rozpatrywanego wielokąta można podzielić na $7$ par odcinków, dla każdego z których ta symetralna jest osią symetrii.

R1G4WAMK8ycRk

Zatem jest $(\begin{matrix} 7 \\ 2 \end{matrix}) = 21$ wszystkich trapezów, których osią symetrii jest ustalona symetralna.

Zauważmy, że wśród tych trapezów są $3$ prostokąty.

RhlpUqf5sQtpi

Oznacza to, że dla ustalonej w tym przypadku osi symetrii jest $18$ trapezów, niebędących prostokątami.
Powtarzając to rozumowanie dla każdej z $\frac{16}{2} = 8$ osi symetrii otrzymamy $18 \cdot 8 = 144$ trapezy spełniające warunki zadania.

Podsumowując, otrzymujemy $192 + 144 = 336$ trapezów spełniających warunki zadania.

Przykład 14

Spośród wszystkich wierzchołków $50$ –kąta foremnego wybieramy $3$ . Obliczymy, ile spośród wybranych trójek punktów to wierzchołki trójkąta rozwartokątnego.

Rozwiązanie

Oznaczamy:

kolejne wierzchołki $50$ –kąta foremnego przez $A_{1}$ , $A_{2}$ , $A_{3}$ , $. . .$ , $A_{50}$ ,

okrąg opisany na rozpatrywanym wielokącie foremnym przez $o$ .

Dalszą część rozwiązania przedstawimy na dwa sposoby.

I sposób:

Wszystkich trójkątów o wierzchołkach wybranych spośród $A_{1}$ , $A_{2}$ , $A_{3}$ , $. . .$ , $A_{50}$ jest tyle, ile jest trzyelementowych kombinacjikombinacji zbioru $50$ –elementowego, czyli $(\begin{matrix} 50 \\ 3 \end{matrix}) = \frac{50 \cdot 49 \cdot 48}{3 \cdot 2 \cdot 1} = 19600$ . Trójkąty te możemy podzielić na trzy rozłączne grupy:

trójkąty prostokątne,

trójkąty ostrokątne,

trójkąty rozwartokątne.

Obliczymy, ile jest trójkątów w każdej z tych grup.

Najpierw obliczamy, ile jest trójkątów prostokątnych.

Zauważmy, że każdy trójkąt prostokątny wpisany w dany $50$ –kąt foremny jest jednoznacznie identyfikowany przez swoją przeciwprostokątną (średnicę okręgu $o$ ) oraz wierzchołek kąta prostego (punkt leżący na jednym z półokręgów wyznaczonych przez tę średnicę).
Ponieważ wszystkich średnic o końcach w wierzchołkach $50$ –kąta foremnego jest $\frac{50}{2} = 25$ , a dla każdej z nich jako przeciwprostokątnej trzeci wierzchołek trójkąta prostokątnego możemy wybrać dowolnie spośród $48$ pozostałych wierzchołków danego wielokąta, więc wśród rozpatrywanych trójkątów jest $25 \cdot 48 = 1200$ prostokątnych.

Obliczamy z kolei, ile jest trójkątów ostrokątnych.

Weźmy pod uwagę przykładowy prostokąt o wierzchołkach wybranych spośród wierzchołków $50$ –kąta foremnego. Przyjmijmy, że jednym z jego boków jest cięciwa $A_{i} A_{i + k}$ , która nie jest średnicą okręgu $o$ . Wtedy ten prostokąt to czworokąt $A_{i} A_{i + k} A_{25 + i} A_{25 + i + k}$ .

RuidmkAachk2k

Ilustracja przedstawia okrąg o środku O z zaznaczonymi punktami. Wpisano w niego prostokąt o wierzchołkach Ai+25+k, Ai+25, Ai+k oraz Ai.

Powyższych oznaczeń będziemy używać do opisu każdego z prostokątów o wierzchołkach wybranych spośród wierzchołków $50$ –kąta foremnego, jeśli spełnione są jednocześnie trzy następujące warunki:

$i = 1, 2, . . ., 50$ ,

$0 < k < 25$ (wtedy przy ustalonym $i$ dla dowolnego $k$ wszystkie odcinki $A_{i} A_{i + k}$ leżą po jednej stronie środka okręgu $o$ ),

jeśli liczba opisująca indeks przy numeracji wierzchołków (czyli $i + k$ , $25 + i$ lub $25 + i + k$ ) jest większa od $50$ , to dla otrzymania właściwej wartości indeksu należy ją zmniejszyć o $50$ , tzn. $51$ zamieniamy na właściwe $1$ , $52$ zamieniamy na właściwe $2$ , itd. (krótko mówiąc: liczby opisujące indeksy przy numeracji wierzchołków bierzemy modulo $50$ ).

Obliczymy, ile jest trójkątów ostrokątnych, w których jeden z boków to cięciwa $A_{i} A_{i + k}$ . Zauważmy, że wówczas trzeci wierzchołek takiego trójkąta może być wybrany jedynie spośród $k - 1$ wierzchołków: $A_{26 + i}$ , $A_{27 + i}$ , $. . .$ , $A_{25 + (k - 1) + i}$ .

RDdP7zJEh7zuw

Ilustracja przedstawia okrąg o środku O z zaznaczonymi punktami. Wpisano w niego prostokąt o wierzchołkach Ai+25+k, Ai+25, Ai+k oraz Ai. Z wierzchołków Ai+k oraz Ai. Poprowadzono proste do punktów na górze okręgu.

To znaczy, że dla ustalonych $i$ oraz $k$ do cięciwy $A_{i} A_{i + k}$ dobierzemy trzeci wierzchołek trójkąta ostrokątnego na $k - 1$ sposobów.

Ponieważ $k \in \{1, 2, 3, . . ., 24\}$ , więc dla ustalonego $i$ wszystkich trójkątów ostrokątnych opisanych powyższymi warunkami jest $0 + 1 + 2 + . . . + 23 = \frac{23 \cdot 24}{2} = 276$ .
Ponadto $i \in \{1, 2, 3, . . ., 50\}$ , zatem zliczając trójkąty dla każdej z $50$ możliwych wartości $i$ dostaniemy, że jest ich $50 \cdot 276 = 13800$ .
W trójkącie ostrokątnym przy każdym z trzech wierzchołków jest kąt ostry, skąd wynika, że otrzymana powyżej wartość jest trzykrotnie większa od poszukiwanej liczby trójkątów ostrokątnych. Wobec tego trójkątów ostrokątnych, których wierzchołki można wybrać spośród wierzchołków $50$ –kąta foremnego jest $\frac{13800}{3} = 4600$ .

Oznacza to, że trójkątów rozwartokątnych spełniających warunki zadania jest $19600 - 1200 - 4600 = 13800$ .

II sposób:

Obliczymy najpierw, ile jest trójkątów rozwartokątnych $A_{1} B C$ , wpisanych w $50$ –kąt foremny, w których kąt przy wierzchołku $A_{1}$ jest ostry oraz $B$ , $C \in \{A_{2}, . . ., A_{50}\}$ .

Zauważmy, że odcinek $A_{1} A_{26}$ jest średnicą okręgu $o$ , opisanego na rozpatrywanym $50$ –kącie.
Oznacza to, że pozostałe dwa wierzchołki $B$ i $C$ poszukiwanego trójkąta leżą na okręgu $o$ po tej samej stronie średnicy $A_{1} A_{26}$ . Zatem możemy je wybrać w jednym z dwóch rozłącznych przypadków:
$(1)$ spośród $24$ wierzchołków $A_{2}$ , $A_{3}$ , $. . .$ , $A_{25}$ ,
$(2)$ spośród $24$ wierzchołków $A_{27}$ , $A_{28}$ , $. . .$ , $A_{50}$ .

W każdym z tych dwóch przypadków wybieramy dwa wierzchołki spośród $24$ , a więc razem mamy $2 \cdot (\begin{matrix} 24 \\ 2 \end{matrix}) = 2 \cdot \frac{24 \cdot 23}{2} = 552$ możliwości. Oznacza to, że dla ustalonego wierzchołka rozpatrywanego $50$ –kąta są $552$ trójkąty spełniające warunki zadania, w których kąt w tym wybranym wierzchołku jest ostry.
Powtarzając to rozumowanie dla każdego z $50$ wierzchołków otrzymamy ogółem $50 \cdot 552 = 27600$ możliwości. Zwróćmy uwagę, że ponieważ w trójkącie rozwartokątnym przy dwóch wierzchołkach są kąty ostre, więc otrzymana wartość jest dwukrotnie większa od poszukiwanej liczby trójkątów rozwartokątnych. Wobec tego trójkątów rozwartokątnych, których wierzchołki można wybrać spośród wierzchołków $50$ –kąta foremnego jest $\frac{27600}{2} = 13800$ .

Polecenie 5

Zapoznaj się z przedstawioną poniżej animacją.
Przeanalizuj zaprezentowane w niej rozwiązanie zadania, w którym należy ustalić, na ile części można podzielić koło za pomocą prostych przechodzących przez punkty leżące na okręgu tego koła.

R1bRj5dUSoIGW

Polecenie 6

Korzystając z przykładu omówionego powyżej rozwiąż samodzielnie następujące zadanie.

W jedenastokącie foremnym poprowadzono wszystkie przekątne.
Wiadomo, że nie istnieją wśród tych przekątnych takie trzy, które mają wspólny punkt (zobacz rysunek).

RSP3eKrIBhVzA

Ilustracja przedstawia jedenastokąt foremny. Przeprowadzono przez niego wszystkie przekątne.

Oblicz, na ile części został podzielony ten wielokąt.

Korzystamy ze spostrzeżenia poczynionego w animacji, w II sposobie rozwiązania prezentowanego tam zadania.

Rozpatrzmy okrąg opisany na jedenastokącie foremnym.
Ponieważ w jedenastokącie foremnym żadne trzy przekątne nie przecinają się w jednym punkcie, więc po narysowaniu wszystkich odcinków łączących wierzchołki tego jedenastokąta podzielimy koło ograniczone rozpatrywanym okręgiem na $1 + (\begin{matrix} 11 \\ 2 \end{matrix}) + (\begin{matrix} 11 \\ 4 \end{matrix}) = 1 + 55 + 330 = 386$ części.
Zauważmy, że dokładnie $11$ z tych części leży poza wielokątem - są to mniejsze odcinki koła utworzone w omawianym kole przez boki jedenastokąta.

Zatem po poprowadzeniu wszystkich przekątnych podzielimy jedenastokąt foremny na $386 - 11 = 375$ części.

$375$

RfjBWT4s9SMGQ2

Ćwiczenie 1

R1GGVKRH4wvZd2

Ćwiczenie 2

Ćwiczenie 3

Dany jest prostokąt $A B C D$ , w którym $|A B| = 5$ oraz $|A D| = 8$ . Prostokąt ten podzielono liniami siatki na kwadraty jednostkowe (jak na rysunku poniżej).

R1U5GJFziJOjd

Ilustracja przedstawia prostokąt A B C D. W środku znajdują się jednakowe kwadraciki tworzące siatkę.

Oblicz, ile jest wszystkich najkrótszych dróg prowadzących po liniach siatki od punktu $A$ do punktu $C$ .

RthbrrjMAzZfT

R1Vb1Vf1deESM

RLV1J1TeIHB9E2

Ćwiczenie 4

R12k79jjteaf32

Ćwiczenie 5

RAhWcL9cXqU4Q2

Ćwiczenie 6

R9WmeBhqDVcnh2

Ćwiczenie 7

RNuywC6CXkveG3

Ćwiczenie 8

Ćwiczenie 9

W pewnej grze losowej należy zaznaczyć na kuponie wybrane $5$ liczb spośród $32$ początkowych dodatnich liczb całkowitych. Na ile sposobów można wytypować $5$ liczb w tej grze tak, aby nie było wśród nich dwóch kolejnych?

R1b3VQNlWc3Lz

R10Ku0x9fXPWk

RM4jQerxjzgkR2

Ćwiczenie 10

Rk4IZMxaW7kty21

Ćwiczenie 11

W kopercie znajdują się dwadzieścia cztery kartki, ponumerowane od jeden do dwadzieścia cztery.
Oznaczamy przez:
A – liczbę sposobów, na które wszystkie te kartki rozdzielimy po równo do dwóch pudełek ponumerowanych od jeden do dwa.
B – liczbę sposobów, na które wszystkie te kartki rozdzielimy po równo do trzech pudełek ponumerowanych od jeden do trzy,
C – liczbę sposobów, na które wszystkie te kartki rozdzielimy po równo do czterech pudełek ponumerowanych od jeden do cztery,
D – liczbę sposobów, na które wszystkie te kartki rozdzielimy po równo do sześciu pudełek ponumerowanych od jeden do sześć,
Dopasuj do siebie pary równych liczb. moc zbioru A Możliwe odpowiedzi: 1. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, dwadzieścia po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, szesnaście po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, dwanaście po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, osiem po cztery, zamknięcie nawiasu, 2. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po osiem, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, szesnaście po osiem, zamknięcie nawiasu, 3. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po sześć, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, osiemnaście po sześć, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, dwanaście po sześć, zamknięcie nawiasu, 4. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po dwanaście, zamknięcie nawiasu moc zbioru B Możliwe odpowiedzi: 1. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, dwadzieścia po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, szesnaście po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, dwanaście po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, osiem po cztery, zamknięcie nawiasu, 2. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po osiem, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, szesnaście po osiem, zamknięcie nawiasu, 3. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po sześć, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, osiemnaście po sześć, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, dwanaście po sześć, zamknięcie nawiasu, 4. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po dwanaście, zamknięcie nawiasu moc zbioru C Możliwe odpowiedzi: 1. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, dwadzieścia po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, szesnaście po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, dwanaście po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, osiem po cztery, zamknięcie nawiasu, 2. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po osiem, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, szesnaście po osiem, zamknięcie nawiasu, 3. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po sześć, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, osiemnaście po sześć, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, dwanaście po sześć, zamknięcie nawiasu, 4. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po dwanaście, zamknięcie nawiasu moc zbioru D Możliwe odpowiedzi: 1. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, dwadzieścia po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, szesnaście po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, dwanaście po cztery, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, osiem po cztery, zamknięcie nawiasu, 2. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po osiem, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, szesnaście po osiem, zamknięcie nawiasu, 3. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po sześć, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, osiemnaście po sześć, zamknięcie nawiasu, razy, symbol Newtona, otwarcie nawiasu, dwanaście po sześć, zamknięcie nawiasu, 4. symbol Newtona, otwarcie nawiasu, dwadzieścia cztery po dwanaście, zamknięcie nawiasu

R1c5z95gXDIfH2

Ćwiczenie 12

RoPWPNokHSzfe2

Ćwiczenie 13

RHx2NyYE2aOds2

Ćwiczenie 14

R1oDt35m7a4Ud2

Ćwiczenie 15

RQSngRr3YHHmU3

Ćwiczenie 16

RMZW0wRHtiEwb3

Ćwiczenie 17

RwGQFS2tmQWbp1

Ćwiczenie 18

Ćwiczenie 19

Na płaszczyźnie narysowano kwadrat. Rozpatrzmy $13$ następujących punktów:

cztery wierzchołki narysowanego kwadratu,
punkt przecięcia przekątnych tego kwadratu,
osiem punktów, które rozmieszczono na bokach kwadratu po dwa tak, że dzielą one każdy z tych boków na trzy odcinki równej długości.

RGr5DWQAhk8vA

Ilustracja przedstawia kwadrat. Zaznaczono punktami cztery wierzchołki. Przekątną oraz punkt przecięcia oraz osiem punktów, które rozmieszczono na bokach kwadratu po dwa tak, że dzielą one każdy z tych boków na trzy odcinki równej długości.

RmEKXoCqWER4G

RJRY6OUyFLN1J2

Ćwiczenie 20

RJpxdrcsCLlbx2

Ćwiczenie 21

R3RURK5bQJbsO2

Ćwiczenie 22

RbrbwBIxEEhFy2

Ćwiczenie 23

Ćwiczenie 24

Równoległobok $A B C D$ przecinamy dwoma grupami prostych:

$9$ prostymi równoległymi do boku $A B$ ,
$7$ prostymi równoległymi do boku $A D$ .

R14qLd4h5ayd3

Ilustracja przedstawia równoległobok A B C D. przecinają go dwie grupy prostych . 9 prostych równoległych do boku AB oraz 7 prostych równoległych do boku AD.

Rfr7JmhJctBHr

RGojWf8CjsEz63

Ćwiczenie 25

do usunięcia

R1MO8ozdIExsi3

Ćwiczenie 26

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 \leq k \leq 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 \leq k \leq n$ , jest równa

$(\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{k! \cdot (n - k)!} = \frac{n \cdot (n - 1) \cdot \dots \cdot (n - k + 1)}{1 \cdot 2 \cdot \dots \cdot k}$

permutacja zbioru

n

–elementowego

permutacja zbioru

n

–elementowego

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

k‑elementowa kombinacja zbioru n‑elementowego

każdy $k$ –elementowy podzbiór zbioru $n$ –elementowego, gdzie $0 \leq k \leq 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, gdzie $0 \leq k \leq n$ , jest równa

$(\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{k! \cdot (n - k)!} = \frac{n \cdot (n - 1) \cdot \dots \cdot (n - k + 1)}{1 \cdot 2 \cdot \dots \cdot k}$

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 $k_{1}$ sposobów, druga – na jeden z $k_{2}$ sposobów, trzecia – na jeden z $k_{3}$ sposobów i tak dalej do $n$ –tej czynności, która może zakończyć się na jeden z $k_{n}$ sposobów, jest równa

$k_{1} \cdot k_{2} \cdot \dots \cdot k_{n}$

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$

4. Permutacje

6. Kombinatoryka – zadania różne

5. Kombinacje

Słownik