Przeczytaj

W poniższych przykładach pokażemy wykorzystanie własności wariacji bez powtórzeńwariacja bez powtórzeńwariacji bez powtórzeń.

W rozwiązaniach tych przykładów będziemy stosować twierdzenie o liczbie wariacji bez powtórzeńtwierdzenie o liczbie wariacji bez powtórzeń.

Jeżeli proponowana metoda rozwiązania będzie polegała na analizie rozłącznych przypadków, to przy obliczaniu liczby wszystkich możliwości z zasady będziemy odwoływać się do reguły dodawaniareguła dodawaniareguły dodawania.

Natomiast jeżeli obliczanie liczby wszystkich możliwości będziemy rozkładali na kolejne etapy, to zazwyczaj odwołamy się przy tym do reguły mnożeniareguła mnożeniareguły mnożenia.

W rozwiązaniu pierwszego przykładu pokażemy też, że jeden ze sposobów uzyskania wyniku opiera się na zastosowaniu reguły równolicznościreguła równolicznościreguły równoliczności.

Przykład 1

Obliczymy, ile jest pięciocyfrowych liczb naturalnych o różnych cyfrach, które są podzielne przez $5$ .

Rozwiązanie

Przypomnijmy, że liczba naturalna jest podzielna przez $5$ wtedy i tylko wtedy, gdy jej ostatnią cyfrą jest $0$ lub $5$ .

Rozpatrzmy więc dwa rozłączne przypadki:

(1) gdy ostatnią cyfrą szukanej liczby pięciocyfrowej jest $0$ ; wtedy rozmieszczeń bez powtórzeń $4$ cyfr z pozostałych dziewięciu na czterech pierwszych miejscach jest $V_{9}^{4} = \frac{9!}{(9 - 4)!} = \frac{9!}{5!} = 9 \cdot 8 \cdot 7 \cdot 6 = 3024$ ,

(2) gdy ostatnią cyfrą szukanej liczby pięciocyfrowej jest $5$ ; wtedy - ponieważ na pierwszym miejscu nie możemy zapisać cyfry $0$ - cyfrę na pierwszym miejscu z pozostałych do wypełnienia czterech możemy wybrać na $8$ sposobów, a cyfry na pozostałych $3$ miejscach możemy rozmieścić bez powtórzeń na $V_{8}^{3}$ sposobów. Zatem na podstawie reguły mnożeniareguła mnożeniareguły mnożenia stwierdzamy, że wszystkich możliwości jest w tym przypadku $8 \cdot V_{8}^{3} = 8 \cdot \frac{8!}{(8 - 3)!} = 8 \cdot \frac{8!}{5!} = 8 \cdot 8 \cdot 7 \cdot 6 = 2688$ .

Korzystamy z reguły dodawaniareguła dodawaniareguły dodawania, skąd dostajemy ostatecznie, że wszystkich pięciocyfrowych liczb naturalnych o różnych cyfrach, które są podzielne przez $5$ jest $3024 + 2688 = 5712$ .

Uwaga!

Liczbę wszystkich możliwości w przypadku (2) można również obliczyć, korzystając z:

reguły równolicznościReguła równolicznościreguły równoliczności; zauważmy mianowicie, że po wstawieniu na ostatnim miejscu cyfry $5$ pozostałe $4$ cyfry można wybrać na $V_{9}^{4}$ sposobów. Ponadto cyfra $0$ to jedyna z dostępnych dziewięciu, której nie możemy wstawić na pierwszym miejscu. Zatem na pierwszym miejscu można wpisać osiem z dziewięciu dostępnych cyfr, więc wszystkich liczb pięciocyfrowych, które w tym przypadku spełniają warunki zadania jest $\frac{8}{9} \cdot V_{9}^{4} = \frac{8}{9} \cdot \frac{9!}{5!} = \frac{8}{9} \cdot 9 \cdot 8 \cdot 7 \cdot 6 = 8 \cdot 8 \cdot 7 \cdot 6 = 2688$ ,

reguły dodawaniareguła dodawaniareguły dodawania; zauważmy mianowicie, że po wstawieniu na ostatnim miejscu cyfry $5$ pozostałe $4$ cyfry można wybrać na $V_{9}^{4}$ sposobów. Ponieważ cyfra $0$ nie może wystąpić na pierwszym miejscu, więc wszystkie przypadki z cyfrą $0$ zapisaną na pierwszym miejscu należy odrzucić. Jest ich tyle, ile wyborów $3$ cyfr spośród $8$ na trzech środkowych miejscach, czyli $V_{8}^{3}$ . Oznacza to, że wszystkich liczb pięciocyfrowych, które w tym przypadku spełniają warunki zadania jest $V_{9}^{4} - V_{8}^{3} = \frac{9!}{5!} - \frac{8!}{5!} = 9 \cdot 8 \cdot 7 \cdot 6 - 8 \cdot 7 \cdot 6 = (9 - 1) \cdot 8 \cdot 7 \cdot 6 =$ $= 8 \cdot 8 \cdot 7 \cdot 6 = 2688$ .

Przykład 2

Kwadrat $A B C D$ o boku $4$ podzielono na $16$ kwadracików o boku $1$ - te kwadraciki będziemy nazywać polami.

R121JeqGSKxL5

Ilustracja przestawiająca kwadrat A B C D. W środku kwadratu umieszczono 16 mniejszych jednakowych kwadratów.

Następnie w każde spośród szesnastu pól kwadratu $A B C D$ wpisujemy jedną liczbę wybraną ze zbioru $A = \{1, 2, 3, \dots, 19\}$ , przy czym wybrana liczba może być wpisana co najwyżej raz. Wymagamy ponadto, żeby pola, które przecina przekątna $A C$ były wypełnione wyłącznie liczbami parzystymi, a pola, które przecina przekątna $B D$ były wypełnione wyłącznie liczbami nieparzystymi.

Wykażemy, że wszystkich sposobów wypełnienia pól kwadratu według powyższych warunków jest więcej niż $10^{14}$ .

Dowód

Obliczenia przeprowadzimy w trzech etapach.

W pierwszym etapie rozmieścimy różne liczby parzyste na czterech polach, które przecina przekątna $A C$ .

Ponieważ dostępnych jest $9$ liczb parzystych, więc wszystkich możliwości w tym etapie jest $V_{9}^{4} = \frac{9!}{5!} = 9 \cdot 8 \cdot 7 \cdot 6 = 3024$ .

W drugim etapie rozmieścimy różne liczby nieparzyste na czterech polach, które przecina przekątna $B D$ .

Ponieważ dostępnych jest $10$ liczb nieparzystych, więc wszystkich możliwości w tym etapie jest $V_{10}^{4} = \frac{10!}{6!} = 10 \cdot 9 \cdot 8 \cdot 7 = 5040$ .

W trzecim etapie rozmieścimy różne liczby spośród pozostałych $11$ na $8$ polach, które jeszcze nie zostałe wypełnione - wszystkich możliwości w tym etapie jest $V_{11}^{8} = \frac{11!}{3!} = 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 = 6652800$ .

Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia otrzymujemy ostatecznie, że wszystkich sposobów wypełnienia pól kwadratu według powyższych warunków jest

$V_{9}^{4} \cdot V_{10}^{4} \cdot V_{11}^{8} = 3024 \cdot 5040 \cdot 6652800 = 101395058688000 =$

$= 1, 01395058688 \cdot 10^{14} > 10^{14}$ .

To spostrzeżenie kończy dowód.

Przykład 3

Obliczymy, ile jest wszystkich siedmiocyfrowych liczb naturalnych o różnych cyfrach, których trzy pierwsze cyfry są nieparzyste, pozostałe cztery cyfry są parzyste oraz w ich zapisie dziesiętnym występuje dokładnie jedna cyfra podzielna przez $7$ .

Rozwiązanie

Na wstępie zauważmy, że:

wśród cyfr zapisu dziesiętnego jest pięć nieparzystych: $1$ , $3$ , $5$ , $7$ , $9$ , przy czym jedna z nich, $7$ , dzieli się przez $7$ ,

wśród cyfr zapisu dziesiętnego jest pięć parzystych: $0$ , $2$ , $4$ , $6$ , $8$ , przy czym jedna z nich, $0$ , dzieli się przez $7$ .

Rozpatrujemy grupy cyfr określone warunkami zadania.

Trzy pierwsze cyfry mają być nieparzyste i różne, zatem można je zapisać na $V_{5}^{3} = \frac{5!}{2!} = 5 \cdot 4 \cdot 3 = 60$ sposobów. Jeśli nie będzie wśród nich cyfry $7$ , to wtedy trzy pierwsze cyfry można zapisać na $V_{4}^{3} = \frac{4!}{1!} = 4 \cdot 3 \cdot 2 = 24$ sposoby. Wobec tego trzy pierwsze cyfry wśród których jest cyfra 7 można - korzystając z reguły dodawaniareguła dodawaniareguły dodawania - zapisać na $V_{5}^{3} - V_{4}^{3} = 60 - 24 = 36$ sposobów.

Cztery ostatnie cyfry mają być parzyste i różne, więc można je zapisać na $V_{5}^{4} = \frac{5!}{1!} = 5 \cdot 4 \cdot 3 \cdot 2 = 120$ sposobów. Jeśli nie będzie wśród nich cyfry $0$ , to wtedy cztery ostatnie cyfry można zapisać na $V_{4}^{4} = \frac{4!}{0!} = 4 \cdot 3 \cdot 2 \cdot 1 = 24$ sposoby. Oznacza to, że cztery ostatnie cyfry wśród których jest cyfra $0$ można zapisać na $V_{5}^{4} - V_{4}^{4} = 120 - 24 = 96$ sposobów.

Wynika stąd, że liczbę spełniającą warunki zadania możemy otrzymać w jednym z dwóch rozłącznych przypadków:

(1) kiedy wśród trzech pierwszych cyfr jest siódemka i wśród czterech ostatnich nie ma zera; korzystamy z reguły mnożeniareguła mnożeniareguły mnożenia i stwierdzamy, że wszystkich takich liczb siedmiocyfrowych jest $(V_{5}^{3} - V_{4}^{3}) \cdot V_{4}^{4} = 36 \cdot 24 = 864$ ,

(2) kiedy wśród trzech pierwszych cyfr nie ma siódemki i wśród czterech ostatnich jest zero; korzystamy z reguły mnożeniareguła mnożeniareguły mnożenia i stwierdzamy, że wszystkich takich liczb siedmiocyfrowych jest $V_{4}^{3} \cdot (V_{5}^{4} - V_{4}^{4}) = 24 \cdot 96 = 2304$ .

Korzystając z reguły dodawaniareguła dodawaniareguły dodawania otrzymujemy ostatecznie, że wszystkich liczb siedmiocyfrowych, które spełniają warunki zadania jest $864 + 2304 = 3168$ .

Uwaga!

Aby ustalić, na ile sposobów można zapisać trzy pierwsze cyfry wśród których jest cyfra $7$ można rozumować następująco: miejsce dla cyfry $7$ możemy wybrać na $3$ sposoby, a pozostałe dwie cyfry – na $V_{4}^{2}$ sposoby, więc wszystkich takich możliwości jest $3 \cdot V_{4}^{2} = 3 \cdot 4 \cdot 3 = 36$ .

Rozumując podobnie obliczymy, że liczba sposobów, na które można zapisać cztery ostatnie cyfry wśród których jest cyfra $0$ , jest równa $4 \cdot V_{4}^{3} = 4 \cdot 4 \cdot 3 \cdot 2 = 96$ .

Przykład 4

Wyznaczymy wszystkie pary $(k, n)$ liczb całkowitych takich, że $1 \leq k \leq n$ , które spełniają równanie

$42 \cdot V_{n}^{k} = V_{n + 2}^{k + 2}$ .

Rozwiązanie

Przekształcamy kolejno zadane równanie:

$42 \cdot V_{n}^{k} = V_{n + 2}^{k + 2}$

$42 \cdot \frac{n!}{(n - k)!} = \frac{(n + 2)!}{(n + 2 - k - 2)!}$

$42 \cdot \frac{n!}{(n - k)!} = \frac{n! \cdot (n + 1) \cdot (n + 2)}{(n - k)!}$

$42 = (n + 1) \cdot (n + 2)$ .

Ponieważ ciągciągciąg określony dla $n \geq 1$ wzorem ogólnym $a_{n} = (n + 1) \cdot (n + 2)$ jest rosnący oraz $a_{5} = 6 \cdot 7 = 42$ , więc równanie jest spełnione dla $n = 5$ oraz każdej liczby całkowitej $k$ , która spełnia warunek $1 \leq k \leq 5$ .

Oznacza to, że jest $5$ par $(k, n)$ spełniających warunki zadania: $(1, 5)$ , $(2, 5)$ , $(3, 5)$ , $(4, 5)$ , $(5, 5)$ .

Słownik

wariacja bez powtórzeń

$k$ –wyrazowy ciąg o elementach wybieranych bez powtórzeń ze zbioru $n$ –elementowego, gdzie $1 \leq k \leq n$

liczba wszystkich k‑elementowych wariacji bez powtórzeń zbioru n‑elementowego

Liczba $V_{n}^{k}$ wszystkich $k$ -elementowych wariacji bez powtórzeń zbioru $n$ -elementowego jest równa

$V_{n}^{k} = \frac{n!}{(n - k)!} = n \cdot (n - 1) \cdot \dots \cdot (n - k + 1)$

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$

reguła dodawania

jeżeli zbiory $A_{1}, A_{2}, \dots, A_{n}$ są parami rozłączne, to liczba elementów zbioru $A_{1} \cup A_{2} \cup \dots \cup A_{n}$ jest równa sumie liczb elementów każdego ze zbiorów $A_{1}, A_{2}, \dots, A_{n}$ : $|A_{1} \cup A_{2} \cup \dots \cup A_{n}| = |A_{1}| + |A_{2}| + \dots + |A_{n}|$

ciąg

funkcja, której dziedziną jest zbiór wszystkich dodatnich liczb całkowitych lub pewien jego podzbiór, a wartościami są liczby rzeczywiste

Wprowadzenie

Animacja

Słownik