Przeczytaj

W poniższych przykładach będziemy korzystali z zależności opisującej liczbę elementów sumy pewnych zbiorów. Podchodząc do tego zadania w ogólnym przypadku będziemy zakładali, że zbiory składające się na taką sumę nie muszą być rozłączne.

Przypomnijmy na początku twierdzenie o liczbie elementów sumy dwóch zbiorów.

o liczbie elementów sumy dwóch zbiorów skończonych

Twierdzenie: o liczbie elementów sumy dwóch zbiorów skończonych

Dla dowolnych dwóch zbiorów skończonych $A$ oraz $B$ prawdziwa jest równość:

|A \cup B| = |A| + |B| - |A \cap B|

Przykład 1

a) Rozpatrzmy zbiór $A$ mający milion elementów, którymi są dodatnie liczby całkowite od $1$ do $1000000$ .
Obliczymy, ile spośród elementów tego zbioru to liczby, które dadzą się zapisać w postaci kwadratu liczby naturalnej lub w postaci sześcianu liczby naturalnej.

Rozwiązanie

Oznaczmy:

przez $A_{2}$ – zbiór tych elementów $A$ , które dadzą się zapisać w postaci kwadratu liczby naturalnej,

przez $A_{3}$ – zbiór tych elementów $A$ , które dadzą się zapisać w postaci sześcianu liczby naturalnej.

Zauważmy, że:

liczba $n$ należy do zbioru $A_{2}$ wtedy i tylko wtedy, gdy spełnia warunek $1 = 1^{2} \leq n = k^{2} \leq 1000000 = 1000^{2}$ . Stąd $k = 1$ , $2$ , $3$ , $. . .$ , $1000$ a więc $|A_{1}| = 1000$ ;

liczba $m$ należy do zbioru $A_{3}$ wtedy i tylko wtedy, gdy spełnia warunek $1 = 1^{3} \leq m = l^{3} \leq 1000000 = 100^{3}$ . Stąd $l = 1$ , $2$ , $3$ , $. . .$ , $100$ , a więc $|A_{2}| = 100$ ;

liczba $p$ należy do zbioru $A_{2} \cap A_{3}$ wtedy i tylko wtedy, gdy jest szóstą potęgą liczby naturalnej, czyli gdy spełnia warunek $1 = 1^{6} \leq p = q^{6} \leq 1000000 = 10^{6}$ . Stąd $q = 1$ , $2$ , $3$ , $. . .$ , $10$ , a więc $|A_{2} \cap A_{3}| = 10$ .

Korzystając z twierdzenia o liczbie elementów sumy dwóch zbiorów otrzymujemy zatem
$|A_{2} \cup A_{3}| = |A_{2}| + |A_{3}| - |A_{2} \cap A_{3}| = 1000 + 100 - 10 = 1090$ .
Ogółem jest więc $1090$ elementów zbioru $A$ , które dadzą się zapisać w postaci kwadratu liczby naturalnej lub w postaci sześcianu liczby naturalnej.

b) Rzucamy cztery razy symetryczną sześcienną kostką do gry. Obliczymy ile jest takich wyników tego doświadczenia, że największą wyrzuconą liczbą oczek jest $6$ i najmniejszą jest $2$ .

Rozwiązanie

Rozpatrzmy wszystkie wyniki czterokrotnego rzutu kostką sześcienną, w których ani razu nie wypadła liczba oczek równa $1$ . Wtedy każdy wynik tego doświadczenia można zapisać jako $4$ –elementowy ciąg $(w_{1}, w_{2}, w_{3}, w_{4})$ , gdzie $w_{1}$ , $w_{2}$ , $w_{3}$ , $w_{4} \in \{2, 3, 4, 5, 6\}$ . Zatem wszystkich takich wyników jest tyle, ile jest $4$ –elementowych wariacji z powtórzeniamiwariacja z powtórzeniamiwariacji z powtórzeniami zbioru $5$ –elementowego, czyli $5^{4}$ .

Mamy obliczyć, ile jest ciągów $(w_{1}, w_{2}, w_{3}, w_{4})$ , w których największy element to $6$ i najmniejszy element to $2$ , co oznacza, że w takim ciągu każdy spośród elementów ze zbioru $\{2, 6\}$ ma wystąpić co najmniej raz.

Obliczymy, ile wśród rozpatrywanych ciągów jest takich, które nie spełniają tego warunku.
Oznaczmy w tym celu:

przez $A$ – zbiór tych ciągów, w których nie występuje liczba $6$ (wtedy największa wyrzucona liczba oczek jest mniejsza od $6$ ),

przez $B$ – zbiór tych ciągów, w których nie występuje liczba $2$ (wtedy najmniejsza wyrzucona liczba oczek jest większa od $2$ ).

Wynika stąd, że:

$|A| = 4^{4}$ (tyle jest ciągów, w których zapisie mogą wystąpić jedynie liczby $2$ , $3$ , $4$ , $5$ ),

$|B| = 4^{4}$ (tyle jest ciągów, w których zapisie mogą wystąpić jedynie liczby $3$ , $4$ , $5$ , $6$ )

$|A \cap B| = 3^{4}$ (tyle jest ciągów, w których zapisie mogą wystąpić jedynie liczby $3$ , $4$ , $5$ ).

Zatem takich wśród rozpatrywanych ciągów, w których nie występuje liczba $6$ lub nie występuje liczba $2$ jest tyle, ile jest elementów zbioru $A \cup B$ .
Korzystając ze wzoru na liczbę elementów sumy dwóch zbiorów otrzymujemy zatem, że
$|A \cup B| = |A| + |B| - |A \cap B| = 4^{4} + 4^{4} - 3^{4}$ .
Oznacza to, że ciągów $(w_{1}, w_{2}, w_{3}, w_{4})$ , w których największy element to $6$ i najmniejszy element to $2$ jest
$5^{4} - (4^{4} + 4^{4} - 3^{4}) = 625 - (256 + 256 - 81) = 194$ .
Wobec tego są $194$ wyniki $4$ –krotnego rzutu kostką, w których największą liczbą wyrzuconych oczek jest $6$ i najmniejszą liczbą wyrzuconych oczek jest $2$ .

Uwaga. Wszystkie wyniki $4$ –krotnego rzutu kostką, które spełniają warunki zadania można podzielić na sześć rozłącznych przypadków:

dokładnie raz wypadły $2$ oczka i dokładnie raz wypadło $6$ oczek, a w pozostałych dwóch rzutach wypadały liczby oczek równe $3$ , $4$ lub $5$ ,

dokładnie dwa razy wypadły $2$ oczka i dokładnie raz wypadło $6$ oczek, a w pozostałym rzucie wypadała liczba oczek równa $3$ , $4$ lub $5$ ,

dokładnie dwa razy wypadło $6$ oczek i dokładnie raz wypadły $2$ oczka, a w pozostałym rzucie wypadała liczba oczek równa $3$ , $4$ lub $5$ ,

dokładnie dwa razy wypadły $2$ oczka i dokładnie dwa razy wypadło $6$ oczek,

dokładnie trzy razy wypadło $6$ oczek i dokładnie raz wypadły $2$ oczka,

dokładnie trzy razy wypadły $2$ oczka i dokładnie raz wypadło $6$ oczek.

W każdym z przypadków liczbę możliwości obliczamy stosując regułę mnożeniareguła mnożeniaregułę mnożenia, a następnie – stosując regułę dodawaniareguła dodawaniaregułę dodawania – obliczamy liczbę wszystkich możliwości. Otrzymujemy tym sposobem, że jest ich
$(\begin{matrix} 4 \\ 1 \end{matrix}) \cdot (\begin{matrix} 3 \\ 1 \end{matrix}) \cdot 3^{2} + 2 \cdot (\begin{matrix} 4 \\ 2 \end{matrix}) \cdot (\begin{matrix} 2 \\ 1 \end{matrix}) \cdot 3 + (\begin{matrix} 4 \\ 2 \end{matrix}) + 2 \cdot (\begin{matrix} 4 \\ 3 \end{matrix}) = 194$ .

W kolejnym przykładzie skorzystamy z poznanego twierdzenia o liczbie elementów sumy trzech zbiorów.

o liczbie elementów sumy trzech zbiorów skończonych

Twierdzenie: o liczbie elementów sumy trzech zbiorów skończonych

Dla dowolnych trzech zbiorów skończonych $A$ , $B$ oraz $C$ prawdziwa jest równość:

|A \cup B \cup C| =

= |A| + |B| + |C| - (|A \cap B| + |B \cap C| + |A \cap C|) + |A \cap C \cap B|

Przykład 2

Rozpatrujemy wszystkie pięciocyfrowe liczby naturalne, w których zapisie dziesiętnym występują jedynie cyfry $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ .
Obliczymy, ile jest wśród nich takich liczb, które mają cyfrę parzystą na pierwszym lub na drugim, lub na trzecim miejscu zapisu dziesiętnego.

Rozwiązanie

Oznaczmy:

przez $A_{1}$ – zbiór tych liczb, w których cyfra parzysta występuje na pierwszym miejscu zapisu dziesiętnego,

przez $A_{2}$ – zbiór tych liczb, w których cyfra parzysta występuje na drugim miejscu zapisu dziesiętnego,

przez $A_{3}$ – zbiór tych liczb, w których cyfra parzysta występuje na trzecim miejscu zapisu dziesiętnego.

Wtedy:
$|A_{1}| = 3 \cdot 7^{4}$ (tyle jest liczb, w których cyfra parzysta występuje na pierwszym miejscu zapisu dziesiętnego),
$|A_{2}| = 3 \cdot 7^{4}$ (tyle jest liczb, w których cyfra parzysta występuje na drugim miejscu zapisu dziesiętnego),
$|A_{3}| = 3 \cdot 7^{4}$ (tyle jest liczb, w których cyfra parzysta występuje na trzecim miejscu zapisu dziesiętnego),
$|A_{1} \cap A_{2}| = 3^{2} \cdot 7^{3}$ (tyle jest liczb, w których cyfra parzysta występuje na pierwszym i na drugim miejscu zapisu dziesiętnego),
$|A_{1} \cap A_{3}| = 3^{2} \cdot 7^{3}$ (tyle jest liczb, w których cyfra parzysta występuje na pierwszym i na trzecim miejscu zapisu dziesiętnego),
$|A_{2} \cap A_{3}| = 3^{2} \cdot 7^{3}$ (tyle jest liczb, w których cyfra parzysta występuje na drugim i na trzecim miejscu zapisu dziesiętnego),
$|A_{1} \cap A_{2} \cap A_{3}| = 3^{3} \cdot 7^{2}$ (tyle jest liczb, w których cyfra parzysta występuje na pierwszym i na drugim, i na trzecim miejscu zapisu dziesiętnego).

Korzystając ze wzoru na liczbę elementów sumy trzech zbiorów otrzymujemy zatem, że
$|A_{1} \cup A_{2} \cup A_{3}| =$

$= |A_{1}| + |A_{2}| + |A_{3}| - (|A_{1} \cap A_{2}| + |A_{1} \cap A_{3}| + |A_{2} \cap A_{3}|) +$

$+ |A_{1} \cap A_{2} \cap A_{3}| = 3 \cdot 3^{1} \cdot 7^{4} - 3 \cdot 3^{2} \cdot 7^{3} + 3^{3} \cdot 7^{2} =$

$= 21609 - 9261 + 1323 = 13671$ .

Jest zatem $13671$ szukanych liczb.

Uwaga 1. Zbiór wszystkich liczb $5$ –cyfrowych, które spełniają warunki zadania można podzielić na trzy rozłączne podzbiory:

tych liczb, w których na dokładnie jednym z początkowych trzech miejsc zapisano cyfrę parzystą (jest ich ogółem $(\begin{matrix} 3 \\ 1 \end{matrix}) \cdot 3 \cdot 4^{2} \cdot 7^{2}$ ),

tych liczb, w których na dokładnie dwóch spośród początkowych trzech miejsc zapisano cyfrę parzystą (jest ich ogółem $(\begin{matrix} 3 \\ 2 \end{matrix}) \cdot 3^{2} \cdot 4 \cdot 7^{2}$ ),

tych liczb, w których na każdym z trzech początkowych miejsc zapisano cyfrę parzystą (jest ich ogółem $(\begin{matrix} 3 \\ 3 \end{matrix}) \cdot 3^{3} \cdot 7^{2}$ ).

Korzystając z reguły dodawaniareguła dodawaniareguły dodawania obliczamy liczbę wszystkich możliwości: $(\begin{matrix} 3 \\ 1 \end{matrix}) \cdot 3^{1} \cdot 4^{2} \cdot 7^{2} + (\begin{matrix} 3 \\ 2 \end{matrix}) \cdot 3^{2} \cdot 4^{1} \cdot 7^{2} + (\begin{matrix} 3 \\ 3 \end{matrix}) \cdot 3^{3} \cdot 7^{2} = 13671$ .

Uwaga 2. Można też od razu zauważyć, że jeśli rozpatrywana liczba pięciocyfrowa nie spełnia warunków zadania, to na każdym z początkowych trzech miejsc zapisu dziesiętnego ma cyfrę nieparzystą. Oznacza to, że wszystkich takich liczb jest $4^{3} \cdot 7^{2}$ .
Ponieważ wszystkich pięciocyfrowych liczb naturalnych, w których zapisie dziesiętnym występują jedynie cyfry $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ jest $7^{5}$ , więc liczb spełniających warunki zadania jest $7^{5} - 4^{3} \cdot 7^{2} = 7^{2} \cdot (7^{3} - 4^{3}) = 13671$ .

Przykład 3

W pudełku znajdują się trzy kule ponumerowane od $1$ do $3$ . Losujemy z tego pudełka pięć razy po jednej kuli, przy czym za każdym razem wrzucamy wylosowaną kulę z powrotem do pudełka.
Obliczymy, ile jest wszystkich wyników takiego losowania, w których każdą z możliwych do wylosowania kul wylosowano co najmniej raz.

Rozwiązanie

Zauważmy, że każdy wynik losowania opisanego w treści zadania można zapisać jako $5$ –elementowy ciąg $(w_{1}, w_{2}, w_{3}, w_{4}, w_{5})$ , gdzie $w_{1}$ , $w_{2}$ , $w_{3}$ , $w_{4}$ , $w_{5} \in \{1, 2, 3\}$ .
Zatem wszystkich możliwych wyników tego doświadczenia jest $3^{5}$ .

Mamy obliczyć, ile jest ciągów $(w_{1}, w_{2}, w_{3}, w_{4}, w_{5})$ , w których każdy spośród elementów zbioru $\{1, 2, 3\}$ wystąpił co najmniej raz.

Obliczymy, ile jest takich wyników losowania, które nie spełniają tego warunku. W tym celu oznaczmy:

przez $A_{1}$ – zbiór tych ciągów, w których nie występuje liczba $1$ ,

przez $A_{2}$ – zbiór tych ciągów, w których nie występuje liczba $2$ ,

przez $A_{3}$ – zbiór tych ciągów, w których nie występuje liczba $3$ .

Wynika stąd, że:
$|A_{1}| = |A_{2}| = |A_{3}| = 2^{5}$ (tyle jest ciągów, w których zapisie mogą wystąpić dokładnie dwa spośród trzech dopuszczalnych numerów: albo tylko $2$ lub $3$ , albo tylko $1$ lub $3$ , albo tylko $1$ lub $2$ ),
$|A_{1} \cap A_{2}| = |A_{1} \cap A_{3}| = |A_{2} \cap A_{3}| = 1^{5}$ (tyle jest ciągów, w których zapisie może wystąpić tylko jedna z dopuszczalnych liczb: albo tylko $1$ , albo tylko $2$ , albo tylko $3$ ),
$|A_{1} \cap A_{2} \cap A_{3}| = 0$
(nie ma takiego ciągu, w którym nie wystąpi ani $1$ , ani $2$ , ani $3$ ).

Wyników losowania, w których nie występuje liczba $1$ lub nie występuje liczba $2$ , lub nie występuje liczba $3$ jest tyle, ile jest elementów zbioru $A_{1} \cup A_{2} \cup A_{3}$ .
Korzystając z zasady włączeń i wyłączeń otrzymujemy zatem, że
$|A_{1} \cup A_{2} \cup A_{3}| =$

$= |A_{1}| + |A_{2}| + |A_{3}| - (|A_{1} \cap A_{2}| + |A_{1} \cap A_{3}| + |A_{2} \cap A_{3}|) +$

$+ |A_{1} \cap A_{2} \cap A_{3}| = 3 \cdot 2^{5} - 3 \cdot 1^{5} + 0 = 93$ .

Oznacza to, że ciągów $(w_{1}, w_{2}, w_{3}, w_{4}, w_{5})$ , w których każda z liczb $1$ , $2$ , $3$ wystąpiła co najmniej raz jest
$3^{5} - (3 \cdot 2^{5} - 3 \cdot 1^{5} + 0) = 243 - 93 = 150$ .
Zatem jest $150$ wyników losowania opisanego warunkami zadania.

Wykażemy teraz, że istnieje zależność opisująca liczbę elementów sumy dowolnych czterech zbiorów skończonych.

o liczbie elementów sumy czterech zbiorów skończonych

Twierdzenie: o liczbie elementów sumy czterech zbiorów skończonych

Dla dowolnych czterech zbiorów skończonych $A$ , $B$ , $C$ oraz $D$ prawdziwa jest równość:

|A \cup B \cup C \cup D| = |A| + |B| + |C| + |D| +

- (|A \cap B| + |A \cap C| + |A \cap D| + |B \cap C| + |B \cap D| + |C \cap D|) +

+ (|A \cap B \cap C| + |A \cap B \cap D| + |A \cap C \cap D| + |B \cap C \cap D|) +

- |A \cap B \cap C \cap D|

Dowód

Dla dowodu wystarczy pokazać, że dowolny element sumy $A \cup B \cup C \cup D$ został po prawej stronie policzony dokładnie raz.
Rozpatrzmy więc cztery rozłączne przypadki.

$(1)$ Weźmy pod uwagę taki element $x$ , który należy do dokładnie jednego ze zbiorów $A$ , $B$ , $C$ lub $D$ .
Wtedy:

do wartości sumy $|A| + |B| + |C| + |D|$ wnosi on dokładnie $1$ ,

nic nie wnosi do wartości sumy $|A \cap B| + |A \cap C| + |A \cap D| + |B \cap C| + |B \cap D| + |C \cap D|$ ,

nic nie wnosi do wartości sumy $|A \cap B \cap C| + |A \cap B \cap D| + |A \cap C \cap D| + |B \cap C \cap D|$ ,

nic nie wnosi do wartości wyrażenia $|A \cap B \cap C \cap D|$ .

Zatem taki element $x$ został policzony dokładnie raz.

$(2)$ Weźmy pod uwagę taki element $y$ , który należy do dokładnie dwóch zbiorów spośród $A$ , $B$ , $C$ , $D$ .
Wtedy:

do wartości sumy $|A| + |B| + |C| + |D|$ wnosi on $2$ ,

do wartości sumy $|A \cap B| + |A \cap C| + |A \cap D| + |B \cap C| + |B \cap D| + |C \cap D|$ wnosi on $1$ ,

nic nie wnosi do wartości sumy $|A \cap B \cap C| + |A \cap B \cap D| + |A \cap C \cap D| + |B \cap C \cap D|$ ,

nic nie wnosi do wartości wyrażenia $|A \cap B \cap C \cap D|$ .

Zatem taki element do wyrażenia po prawej stronie wnosi wartość $2 - 1 = 1$ , czyli $y$ został policzony dokładnie raz.

$(3)$ Weźmy pod uwagę taki element $z$ , który należy do dokładnie trzech zbiorów spośród $A$ , $B$ , $C$ , $D$ .
Wtedy:

do wartości sumy $|A| + |B| + |C| + |D|$ wnosi on $3$ ,

do wartości sumy $|A \cap B| + |A \cap C| + |A \cap D| + |B \cap C| + |B \cap D| + |C \cap D|$ wnosi on $3$ ,

do wartości sumy $|A \cap B \cap C| + |A \cap B \cap D| + |A \cap C \cap D| + |B \cap C \cap D|$ wnosi on $1$ ,

nic nie wnosi do wartości wyrażenia $|A \cap B \cap C \cap D|$ .

Zatem taki element do wyrażenia po prawej stronie wnosi wartość $3 - 3 + 1 = 1$ , czyli $z$ został policzony dokładnie raz.

$(4)$ Weźmy pod uwagę taki element $t$ , który należy do każdego z czterech zbiorów spośród $A$ , $B$ , $C$ , $D$ .
Wtedy:

do wartości sumy $|A| + |B| + |C| + |D|$ wnosi on $4$ ,

do wartości sumy $|A \cap B| + |A \cap C| + |A \cap D| + |B \cap C| + |B \cap D| + |C \cap D|$ wnosi on $6$ ,

do wartości sumy $|A \cap B \cap C| + |A \cap B \cap D| + |A \cap C \cap D| + |B \cap C \cap D|$ wnosi on $4$ ,

do wartości wyrażenia $|A \cap B \cap C \cap D|$ element $t$ wnosi $1$ .

Zatem taki element do wyrażenia po prawej stronie wnosi wartość $4 - 6 + 4 - 1 = 1$ , czyli $t$ również został policzony dokładnie raz.

W ten sposób dowód został zakończony.

Przykład 4

a) Rozpatrzmy wszystkie czterocyfrowe liczby naturalne. Obliczymy, ile jest wśród nich takich liczb, które nie dzielą się ani przez $2$ , ani przez $3$ , ani przez $4$ , ani przez $5$ .

Rozwiązanie

Zaczynamy od ustalenia, że czterocyfrowych liczb naturalnych jest $9000$ .
Następnie obliczymy, ile jest takich liczb czterocyfrowych, które nie spełniają zadanego warunku.
W tym celu oznaczmy:

przez $A$ – zbiór czterocyfrowych liczb naturalnych podzielnych przez $2$ ,

przez $B$ – zbiór czterocyfrowych liczb naturalnych podzielnych przez $3$ ,

przez $C$ – zbiór czterocyfrowych liczb naturalnych podzielnych przez $4$ ,

przez $D$ – zbiór czterocyfrowych liczb naturalnych podzielnych przez $5$ .

Korzystając z reguły równolicznościreguła równolicznościreguły równoliczności obliczamy, że:
$|A| = \frac{1}{2} \cdot 9000 = 4500$ ,
$|B| = \frac{1}{3} \cdot 9000 = 3000$ ,
$|C| = \frac{1}{4} \cdot 9000 = 2250$ ,
$|D| = \frac{1}{5} \cdot 9000 = 1800$ ,
$|A \cap B| = \frac{1}{6} \cdot 9000 = 1500$ ,
$|A \cap C| = |C| = 2250$ ,
$|A \cap D| = \frac{1}{10} \cdot 9000 = 900$ ,
$|B \cap C| = \frac{1}{12} \cdot 9000 = 750$ ,
$|B \cap D| = \frac{1}{15} \cdot 9000 = 600$ ,
$|C \cap D| = \frac{1}{20} \cdot 9000 = 450$ ,
$|A \cap B \cap C| = |B \cap C| = 750$ ,
$|A \cap B \cap D| = \frac{1}{30} \cdot 9000 = 300$ ,
$|A \cap C \cap D| = |C \cap D| = 450$ ,
$|B \cap C \cap D| = \frac{1}{60} \cdot 9000 = 150$ ,
$|A \cap B \cap C \cap D| = |B \cap C \cap D| = 150$ .

Czterocyfrowych liczb naturalnych, które dzielą się przez $2$ lub przez $3$ lub przez $4$ lub przez $5$ jest tyle, ile jest elementów zbioru $A \cup B \cup C \cup D$ .
Korzystając ze wzoru na sumę czterech zbiorów skończonych otrzymujemy zatem, że
$|A \cup B \cup C \cup D| = |A| + |B| + |C| + |D| +$

$- (|A \cap B| + |A \cap C| + |A \cap D| + |B \cap C| + |B \cap D| + |C \cap D|) +$

$+ (|A \cap B \cap C| + |A \cap B \cap D| + |A \cap C \cap D| + |B \cap C \cap D|) +$

$- |A \cap B \cap C \cap D| = 4500 + 3000 + 2250 + 1800 +$

$- (1500 + 2250 + 900 + 750 + 600 + 450) +$

$+ (750 + 300 + 450 + 150) - 150 = 6600$ .

Oznacza to, że czterocyfrowych liczb naturalnych, które nie dzielą się ani przez $2$ , ani przez $3$ , ani przez $4$ , ani przez $5$ jest $9000 - 6600 = 2400$ .

Uwaga. Rozpatrując wszystkie reszty z dzielenia przez liczbę $60$ (jest to najmniejsza wspólna wielokrotność liczb $2$ , $3$ , $4$ oraz $5$ ), stwierdzimy, że wśród nich jest dokładnie $16$ reszt względnie pierwszych z każdą z liczb $2$ , $3$ , $4$ oraz $5$ . Stąd na podstawie reguły równoliczności wnioskujemy, że czterocyfrowych liczb naturalnych, które nie dzielą się ani przez $2$ , ani przez $3$ , ani przez $4$ , ani przez $5$ jest $\frac{16}{60} \cdot 9000 = 2400$ .

b) Rozpatrzmy wszystkie permutacjepermutacja zbioru $n$ –elementowegopermutacje sześcioelementowego zbioru $\{1, 2, 3, 4, 5, 6\}$ . Obliczymy, ile spośród tych permutacji spełnia następujący warunek: wśród dowolnych trzech kolejnych wyrazów permutacji nie ma takiej trójki, która jest zapisana w porządku rosnącym.

Rozwiązanie

Każdą permutacjępermutacja zbioru $n$ –elementowegopermutację sześcioelementowego zbioru $\{1, 2, 3, 4, 5, 6\}$ można zapisać w postaci $(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6})$ .
Wszystkich takich permutacjiWszystkich takich permutacji jest $6! = 720$ .
Mamy obliczyć, ile spośród tych permutacjipermutacja zbioru $n$ –elementowegopermutacji spełnia następujący warunek: wśród dowolnych trzech kolejnych wyrazów permutacjipermutacja zbioru $n$ –elementowegopermutacji nie ma takiej trójki, która jest zapisana w porządku rosnącym.

Najpierw obliczymy, ile jest takich ciągów, które nie spełniają tego warunku.
W tym celu oznaczmy:

przez $A$ – zbiór tych permutacjipermutacja zbioru $n$ –elementowegopermutacji, w których pierwsze trzy wyrazy są zapisane w porządku rosnącym,

przez $B$ – zbiór tych permutacjipermutacja zbioru $n$ –elementowegopermutacji, w których wyrazy drugi, trzeci i czwarty są zapisane w porządku rosnącym,

przez $C$ – zbiór tych permutacjipermutacja zbioru $n$ –elementowegopermutacji, w których wyrazy trzeci, czwarty i piąty są zapisane w porządku rosnącym,

przez $D$ – zbiór tych permutacjipermutacja zbioru $n$ –elementowegopermutacji, w których wyrazy czwarty, piąty i szósty są zapisane w porządku rosnącym.

Zauważmy, że:

ponieważ trzy liczby ze zbioru $\{1, 2, 3, 4, 5, 6\}$ możemy wybrać na $(\begin{matrix} 6 \\ 3 \end{matrix}) = 20$ sposobów, następnie zapisać je w permutacjipermutacja zbioru $n$ –elementowegopermutacji w porządku rosnącym na ustalonych trzech miejscach można tylko na jeden sposób, a uzupełnić pozostałe trzy miejsca w ciągu można na $3! = 6$ sposobów, więc $|A| = |B| = |C| = |D| = (\begin{matrix} 6 \\ 3 \end{matrix}) \cdot 3! = 20 \cdot 6 = 120$ ;

ponieważ trzy liczby ze zbioru $\{1, 2, 3, 4, 5, 6\}$ możemy wybrać na $(\begin{matrix} 6 \\ 3 \end{matrix}) = 20$ sposobów, zapisać je w permutacjipermutacja zbioru $n$ –elementowegopermutacji w porządku rosnącym na ustalonych trzech miejscach można tylko na jeden sposób, a liczby na pozostałych trzech miejscach można ustawić w porządku rosnącym również na jeden sposób, więc $|A \cap D| = (\begin{matrix} 6 \\ 3 \end{matrix}) = 20$ ;

ponieważ cztery liczby ze zbioru $\{1, 2, 3, 4, 5, 6\}$ możemy wybrać na $(\begin{matrix} 6 \\ 4 \end{matrix}) = 15$ sposobów, zapisać je w permutacjipermutacja zbioru $n$ –elementowegopermutacji na ustalonych czterech miejscach w porządku rosnącym można tylko na jeden sposób, a uzupełnić pozostałe dwa miejsca w ciągu można na $2! = 2$ sposoby, więc $|A \cap B| = |B \cap C| = |C \cap D| = (\begin{matrix} 6 \\ 4 \end{matrix}) \cdot 2! = 15 \cdot 2 = 30$ ;

ponieważ pięć liczb ze zbioru $\{1, 2, 3, 4, 5, 6\}$ możemy wybrać na $(\begin{matrix} 6 \\ 5 \end{matrix}) = 6$ sposobów, zapisać je w permutacjipermutacja zbioru $n$ –elementowegopermutacji na ustalonych pięciu miejscach w porządku rosnącym można tylko na jeden sposób, a również na jeden sposób można uzupełnić pozostałe jedno miejsce w ciągu, więc $|A \cap C| = |B \cap D| = |A \cap B \cap C| = |B \cap C \cap D| = (\begin{matrix} 6 \\ 5 \end{matrix}) = 6$ ;

ponieważ wszystkie liczby ze zbioru $\{1, 2, 3, 4, 5, 6\}$ możemy zapisać w permutacjipermutacja zbioru $n$ –elementowegopermutacji w porządku rosnącym na jeden sposób, więc $|A \cap B \cap D| = |A \cap C \cap D| = |A \cap B \cap C \cap D| = 1$ .

Ponieważ wszystkich ciągów, w których co najmniej jedna trójka kolejnych wyrazów jest zapisana w porządku rosnącym jest tyle, ile jest elementów zbioru $A \cup B \cup C \cup D$ , więc korzystając ze wzoru na sumę czterech zbiorów skończonych otrzymujemy, że
$|A \cup B \cup C \cup D| = |A| + |B| + |C| + |D| +$

$- (|A \cap B| + |A \cap C| + |A \cap D| + |B \cap C| + |B \cap D| + |C \cap D|) +$

$+ (|A \cap B \cap C| + |A \cap B \cap D| + |A \cap C \cap D| + |B \cap C \cap D|) +$

$- |A \cap B \cap C \cap D| = 4 \cdot 120 - (3 \cdot 30 + 20 + 2 \cdot 6) + (2 \cdot 6 + 2 \cdot 1) - 1 = 371$

Zatem takich permutacjipermutacja zbioru $n$ –elementowegopermutacji danego zbioru, że wśród ich dowolnych trzech kolejnych wyrazów nie ma trójki zapisanej w porządku rosnącym jest $720 - 371 = 349$ .

Podamy teraz wzór, który pozwala obliczać liczbę elementów sumy $n$ zbiorów skończonych $A_{1}$ , $A_{2}$ , $. . .$ , $A_{n}$ .
(w rozwiązaniach powyższych przykładów wzór ten wystąpił w szczególnych przypadkach, gdy $n = 2$ , $3$ , $4$ ).

Zasada włączeń i wyłączeń

Twierdzenie: Zasada włączeń i wyłączeń

Dla dowolnych zbiorów skończonych $A_{1}$ , $A_{2}$ , $. . .$ , $A_{n}$ prawdziwa jest równość

|A_{1} \cup A_{2} \cup \dots \cup A_{n}| = |A_{1}| + |A_{2}| + . . . + |A_{n}| +

- (|A_{1} \cap A_{2}| + |A_{1} \cap A_{3}| + . . . + |A_{1} \cap A_{n}| + . . . + |A_{n - 1} \cap A_{n}|) +

- (|A_{1} \cap A_{2} \cap A_{3}| + |A_{1} \cap A_{2} \cap A_{4}| + . . . + |A_{n - 2} \cap A_{n - 1} \cap A_{n}|) +

+ . . . + {(- 1)}^{n - 1} \cdot |A_{1} \cap A_{2} \cap . . . \cap A_{n}|

Dowód

W powyższym wzorze zapisujemy:

z plusem – liczby elementów każdego z pojedynczo rozpatrywanych zbiorów,

z minusem – liczby elementów każdego z możliwych iloczynów par rozpatrywanych zbiorów,

z plusem – liczby elementów każdego z możliwych iloczynów trójek rozpatrywanych zbiorów,

itd. aż do iloczynu wszystkich zbiorów, przy czym dla kolejnej grupy znak plus stawiamy wyłącznie wtedy, gdy zapisujemy iloczyny nieparzystej liczby rozpatrywanych zbiorów, a znak minus – wyłącznie wtedy, gdy zapisujemy iloczyny parzystej liczby rozpatrywanych zbiorów.

Dla dowodu wystarczy pokazać, że dowolny element sumy $A_{1} \cup A_{2} \cup . . . \cup A_{n}$ został po prawej stronie policzony dokładnie raz.

Weźmy taki element sumy rozpatrywanych zbiorów, który należy do dokładnie $k$ spośród nich ( $1 \leq k \leq n$ ).
Pokażemy, że niezależnie od wartości $k$ taki element został po prawej stronie wzoru policzony dokładnie raz.

Zauważmy, że:
$(1)$ element ten nie występuje w żadnym z iloczynów rozpatrywanych zbiorów, w którym zapisano więcej niż $k$ z nich,
$(2)$ dla ustalonego $i$ , gdzie $1 \leq i \leq k$ , do wartości sumy, w której zapisane są wszystkie możliwe iloczyny $i$ spośród rozpatrywanych zbiorów wyróżniony element wnosi $(\begin{matrix} k \\ i \end{matrix})$ .

W szczególności ten element:

do wartości sumy $|A_{1}| + |A_{2}| + \dots + |A_{n}|$ (w której występują liczby elementów każdego z pojedynczo rozpatrywanych zbiorów) wnosi $(\begin{matrix} k \\ 1 \end{matrix})$ ,

do wartości sumy $|A_{1} \cap A_{2}| + |A_{1} \cap A_{3}| + . . . + |A_{1} \cap A_{n}| + . . . + |A_{n - 1} \cap A_{n}|$ (w której występują liczby elementów każdego z możliwych iloczynów par rozpatrywanych zbiorów) wnosi $(\begin{matrix} k \\ 2 \end{matrix})$ ,

do wartości sumy $|A_{1} \cap A_{2} \cap A_{3}| + |A_{1} \cap A_{2} \cap A_{4}| + \dots + |A_{n - 2} \cap A_{n - 1} \cap A_{n}|$ (w której występują liczby elementów każdego z możliwych iloczynów trójek rozpatrywanych zbiorów) wnosi dokładnie $(\begin{matrix} k \\ 3 \end{matrix})$ ,

$. . .$

do wartości sumy $|A_{1} \cap A_{2} \cap . . . \cap A_{k}| + . . . + |A_{n - k + 1} \cap A_{n - k + 2} \cap . . . \cap A_{n}|$ (w której występują liczby elementów każdego z możliwych iloczynów $k$ spośród wszystkich rozpatrywanych zbiorów) wnosi $(\begin{matrix} k \\ k \end{matrix}) = 1$ .

Zatem liczba po prawej stronie wzoru jest równa
$(\begin{matrix} k \\ 1 \end{matrix}) - (\begin{matrix} k \\ 2 \end{matrix}) + (\begin{matrix} k \\ 3 \end{matrix}) - . . . + {(- 1)}^{k - 1} \cdot (\begin{matrix} k \\ k \end{matrix}) =$
$= 1 + (- 1) + (\begin{matrix} k \\ 1 \end{matrix}) - (\begin{matrix} k \\ 2 \end{matrix}) + (\begin{matrix} k \\ 3 \end{matrix}) - . . . + {(- 1)}^{k - 1} \cdot (\begin{matrix} k \\ k \end{matrix}) =$
$= 1 - (1 - (\begin{matrix} k \\ 1 \end{matrix}) + (\begin{matrix} k \\ 2 \end{matrix}) - (\begin{matrix} k \\ 3 \end{matrix}) + . . . + {(- 1)}^{k} \cdot (\begin{matrix} k \\ k \end{matrix})) =$
$= 1 - {(1 + (- 1))}^{k} = 1 - 0 = 1$ .

To spostrzeżenie kończy dowód.

Przykład 5

a) Rozpatrzmy losowe rozmieszczenie $7$ kul (ponumerowanych od $1$ do $7$ ) w $5$ różnych pudełkach (ponumerowanych od $1$ do $5$ ).
Na ile różnych sposobów można kule rozmieścić tak, aby w każdym pudełku znalazła się przynajmniej jedna z nich?

Rozwiązanie

Zauważmy, że każdy wynik losowania opisanego w treści zadania można zapisać jako $7$ –elementowy ciąg $(k_{1}, k_{2}, k_{3}, k_{4}, k_{5}, k_{6}, k_{7})$ , przy czym przez $k_{i}$ , gdzie $i = 1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ , oznaczyliśmy numer pudełka do którego wpadła kula o numerze $i$ .
Stąd $k_{i} \in \{1, 2, 3, 4, 5\}$ , a więc wszystkich możliwych rozmieszczeń $7$ różnych kul w $5$ różnych pudełkach jest $5^{7}$ .

Mamy obliczyć, ile jest takich ciągów $(k_{1}, k_{2}, k_{3}, k_{4}, k_{5}, k_{6}, k_{7})$ , w których każdy spośród elementów ze zbioru $\{1, 2, 3, 4, 5\}$ wystąpi co najmniej raz.

Obliczymy, ile jest takich wyników losowania, które nie spełniają tego warunku. W tym celu oznaczmy:

przez $A_{1}$ – zbiór tych ciągów, w których nie występuje liczba $1$ ,

przez $A_{2}$ – zbiór tych ciągów, w których nie występuje liczba $2$ ,

przez $A_{3}$ – zbiór tych ciągów, w których nie występuje liczba $3$ ,

przez $A_{4}$ – zbiór tych ciągów, w których nie występuje liczba $4$ ,

przez $A_{5}$ – zbiór tych ciągów, w których nie występuje liczba $5$ .

Wobec tego wszystkich ciągów, w których nie występuje co najmniej jedna z liczb $1$ , $2$ , $3$ , $4$ , $5$ jest tyle, ile jest elementów zbioru $A_{1} \cup A_{2} \cup A_{3} \cup A_{4} \cup A_{5}$ .

Ponieważ:

$|A_{1}| = |A_{2}| = |A_{3}| = |A_{4}| = |A_{5}| = 4^{7}$

$|A_{1} \cap A_{2}| + |A_{1} \cap A_{3}| + |A_{1} \cap A_{4}| + |A_{1} \cap A_{5}| + . . . + |A_{4} \cap A_{5}| = 3^{7}$

$|A_{1} \cap A_{2} \cap A_{3}| + |A_{1} \cap A_{2} \cap A_{4}| + . . . + |A_{3} \cap A_{4} \cap A_{5}| = 2^{7}$

$|A_{1} \cap A_{2} \cap A_{3} \cap A_{4}| + |A_{1} \cap A_{2} \cap A_{3} \cap A_{5}| + . . . + |A_{2} \cap A_{3} \cap A_{4} \cap A_{5}| = 1^{7}$

$|A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap A_{5}| = 0$
(zbiór $A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap A_{5}$ jest, oczywiście, pusty),

więc korzystając z zasady włączeń i wyłączeń otrzymujemy, że
$|A_{1} \cup A_{2} \cup A_{3} \cup A_{4} \cup A_{5}| = |A_{1}| + |A_{2}| + |A_{3}| + |A_{4}| + |A_{5}| +$

$- (|A_{1} \cap A_{2}| + |A_{1} \cap A_{3}| + . . . + |A_{4} \cap A_{5}|) +$

$+ (|A_{1} \cap A_{2} \cap A_{3}| + |A_{1} \cap A_{2} \cap A_{4}| + . . . + |A_{3} \cap A_{4} \cap A_{5}|) +$

$- (|A_{1} \cap A_{2} \cap A_{3} \cap A_{4}| + |A_{1} \cap A_{2} \cap A_{3} \cap A_{5}| + . . . + |A_{2} \cap A_{3} \cap A_{4} \cap A_{5}|) +$

$+ |A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap A_{5}| = (\begin{matrix} 5 \\ 1 \end{matrix}) \cdot 4^{7} - (\begin{matrix} 5 \\ 2 \end{matrix}) \cdot 3^{7} + (\begin{matrix} 5 \\ 3 \end{matrix}) \cdot 2^{7} - (\begin{matrix} 5 \\ 4 \end{matrix}) \cdot 1^{7} +$

$+ (\begin{matrix} 5 \\ 5 \end{matrix}) \cdot 0 = 81920 - 21870 + 1280 - 5 + 0 = 61325$

Oznacza to, że takich ciągów $(k_{1}, k_{2}, k_{3}, k_{4}, k_{5}, k_{6}, k_{7})$ , w których każdy spośród elementów ze zbioru $\{1, 2, 3, 4, 5\}$ wystąpi co najmniej raz jest
$5^{7} - 61325 = 78125 - 61325 = 16800$ .

Zatem jest $16800$ rozmieszczeń $7$ różnych kul w $5$ różnych pudełkach tak, aby w każdym pudełku znalazła się przynajmniej jedna kula.

b) Obliczymy, ile jest $7$ –cyfrowych liczb naturalnych, w których zapisie dziesiętnym występuje dokładnie $5$ różnych cyfr.

Rozwiązanie

I sposób.
Oznaczmy przez $x$ pierwszą (od lewej) cyfrę zapisu dziesiętnego siedmiocyfrowej liczby naturalnej, a jej kolejne cyfry przez – odpowiednio - $c_{2}, c_{3}, c_{4}, c_{5}, c_{6}, c_{7}$ .
Wtedy kolejne (od lewej) cyfry liczby spełniającej warunki zadania tworzą ciąg $(x, c_{2}, c_{3}, c_{4}, c_{5}, c_{6}, c_{7})$ .
Cyfrę $x$ możemy wybrać dowolnie ze zbioru $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ , czyli na $9$ sposobów.
Pozą nią na pozostałych 6 miejscach mamy zapisać $4$ inne cyfry - oznaczmy je przez $y, z, t, v$ .
Ponieważ wybierając je dopuszczamy wykorzystanie cyfry $0$ , więc te $4$ cyfry różne od $x$ możemy wybrać na $(\begin{matrix} 9 \\ 4 \end{matrix}) = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2} = 126$ sposobów.

Wszystkich możliwości zapisania tak wybranych $5$ cyfr na miejscach $c_{2}, c_{3}, c_{4}, c_{5}, c_{6}, c_{7}$ jest tyle, ile jest sześcioelementowych wariacji z powtórzeniamiwariacji z powtórzeniami ze zbioru $\{x, y, z, t, v\}$ , czyli $5^{6}$ .

Zauważmy, że do rozwiązania zadania wystarczy jeszcze obliczyć, ile jest ciągów $(c_{2}, c_{3}, c_{4}, c_{5}, c_{6}, c_{7})$ , w których każdy spośród elementów ze zbioru $\{y, z, t, v\}$ wystąpi co najmniej raz.

Obliczymy, ile jest wszystkich ciągów $(c_{2}, c_{3}, c_{4}, c_{5}, c_{6}, c_{7})$ , które nie spełniają tego warunku.

W tym celu oznaczmy:

przez $Y$ – zbiór tych ciągów, w których nie występuje cyfra $y$ ,
przez $Z$ – zbiór tych ciągów, w których nie występuje cyfra $z$ ,
przez $T$ – zbiór tych ciągów, w których nie występuje cyfra $t$ ,
przez $V$ – zbiór tych ciągów, w których nie występuje cyfra $v$ .

Wobec tego wszystkich ciągów, w których nie występuje co najmniej jedna z cyfr $y$ , $z$ , $t$ , $v$ jest tyle, ile jest elementów zbioru $Y \cup Z \cup T \cup V$ .

Ponieważ:
$|Y| = |Z| = |T| = |V| = 4^{6}$ ,
$|Y \cap Z| = |Y \cap T| = |Y \cap V| = |Z \cap T| = |Z \cap V| = |T \cap V| = 3^{6}$ ,
$|Y \cap Z \cap T| = |Y \cap Z \cap V| = |Y \cap T \cap V| = |Z \cap T \cap V| = 2^{6}$ ,
$|Y \cap Z \cap T \cap V| = 1^{6}$ ,
więc korzystając z zasady włączeń i wyłączeń otrzymujemy, że
$|Y \cup Z \cup T \cup V| =$
$+ (|Y| + |Z| + |T| + |V|) +$
$- (| Y \cap Z | + | Y \cap T | + | Y \cap V | + | Z \cap T | + | Z \cap V | + | T \cap V |) +$
$+ (|Y \cap Z \cap T| + |Y \cap Z \cap V| + |Y \cap T \cap V| + |Z \cap T \cap V|) +$
$- |Y \cap Z \cap T \cap V| =$
$= + (\begin{matrix} 4 \\ 1 \end{matrix}) \cdot 4^{6} - (\begin{matrix} 4 \\ 2 \end{matrix}) \cdot 3^{6} + (\begin{matrix} 4 \\ 3 \end{matrix}) \cdot 2^{6} - (\begin{matrix} 4 \\ 4 \end{matrix}) \cdot 1^{6} =$
$= 16384 - 4374 + 256 - 1 = 12265$ .

Oznacza to, że takich ciągów $(c_{2}, c_{3}, c_{4}, c_{5}, c_{6}, c_{7})$ , w których każdy spośród elementów ze zbioru $\{y, z, t, v\}$ wystąpi co najmniej raz jest
$5^{6} - ((\begin{matrix} 4 \\ 1 \end{matrix}) \cdot 4^{6} - (\begin{matrix} 4 \\ 2 \end{matrix}) \cdot 3^{6} + (\begin{matrix} 4 \\ 3 \end{matrix}) \cdot 2^{6} - (\begin{matrix} 4 \\ 4 \end{matrix}) \cdot 1^{6}) =$
$15625 - 12265 = 3360$ .

Ostatecznie stwierdzamy, że wszystkich siedmiocyfrowych liczb naturalnych, w których zapisie dziesiętnym występuje dokładnie $5$ różnych cyfr jest
$9 \cdot (\begin{matrix} 9 \\ 4 \end{matrix}) \cdot (5^{6} - ((\begin{matrix} 4 \\ 1 \end{matrix}) \cdot 4^{6} - (\begin{matrix} 4 \\ 2 \end{matrix}) \cdot 3^{6} + (\begin{matrix} 4 \\ 3 \end{matrix}) \cdot 2^{6} - (\begin{matrix} 4 \\ 4 \end{matrix}) \cdot 1^{6})) =$
$= 9 \cdot 126 \cdot 3360 = 3810240$ .

II sposób.
Podobnie jak w sposobie I, oznaczmy przez $x$ pierwszą (od lewej) cyfrę zapisu dziesiętnego siedmiocyfrowej liczby naturalnej. Cyfrę $x$ możemy wybrać dowolnie ze zbioru $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ , czyli na $9$ sposobów.

Cyfry na pozostałych $9$ miejscach możemy zapisać na jeden z czterech rozłącznych sposobów:
(1) na $2$ z tych $6$ miejsc zapisujemy cyfrę $x$ , następnie wybieramy $4$ cyfry z dostępnych $9$ i rozmieszczamy je na pozostałych $4$ miejscach;
ogółem jest w tym przypadku $(\begin{matrix} 6 \\ 2 \end{matrix}) \cdot (\begin{matrix} 9 \\ 4 \end{matrix}) \cdot 4! = 15 \cdot 126 \cdot 24 = 45360$ możliwości,
(2) na jednym z tych $6$ miejsc zapisujemy cyfrę $x$ , następnie wybieramy z $9$ dostępnych jedną cyfrę i zapisujemy ją na $2$ spośród pozostałych $5$ miejsc, na koniec wybieramy $3$ cyfry z $8$ pozostałych i rozmieszczamy je na $3$ miejscach;
ogółem jest w tym przypadku $(\begin{matrix} 6 \\ 1 \end{matrix}) \cdot (\begin{matrix} 9 \\ 1 \end{matrix}) \cdot (\begin{matrix} 5 \\ 2 \end{matrix}) \cdot (\begin{matrix} 8 \\ 3 \end{matrix}) \cdot 3! = 6 \cdot 9 \cdot 10 \cdot 56 \cdot 6 = 181440$ ,
(3) wybieramy jedną cyfrę z $9$ dostępnych i zapisujemy ją na $3$ spośród rozpatrywanych $6$ miejsc, następnie wybieramy $3$ cyfry z $8$ pozostałych i rozmieszczamy je na pozostałych $3$ miejscach;
ogółem jest w tym przypadku $(\begin{matrix} 9 \\ 1 \end{matrix}) \cdot (\begin{matrix} 6 \\ 3 \end{matrix}) \cdot (\begin{matrix} 8 \\ 3 \end{matrix}) \cdot 3! = 9 \cdot 20 \cdot 56 \cdot 6 = 60480$ możliwości,

(4) wybieramy z $9$ dostępnych dwie cyfry i dla każdej z nich znajdujemy $2$ miejsca spośród $6$ miejsc, następnie wybieramy $2$ cyfry z $7$ pozostałych i rozmieszczamy je na $2$ miejscach;
ogółem jest w tym przypadku $(\begin{matrix} 9 \\ 2 \end{matrix}) \cdot (\begin{matrix} 6 \\ 2 \end{matrix}) \cdot (\begin{matrix} 4 \\ 2 \end{matrix}) \cdot (\begin{matrix} 7 \\ 2 \end{matrix}) \cdot 2! = 36 \cdot 15 \cdot 6 \cdot 21 \cdot 2 = 136080$ możliwości.

Wobec tego, korzystając z reguły mnożeniareguła mnożeniareguły mnożenia oraz z reguły dodawaniareguła dodawaniareguły dodawania otrzymujemy, że wszystkich liczb spełniających warunki zadania jest $9 \cdot (45360 + 181440 + 60480 + 136080) = 3810240$ .

Przykład 6

Obliczymy, ile jest dodatnich liczb całkowitych względnie pierwszych z liczbą $5544$ , które nie są większe od $5544$ .

Rozwiązanie

Oznaczmy przez $A$ zbiór wszystkich dodatnich liczb całkowitych, które nie są większe od $5544$ : $A = \{1, 2, 3, . . ., 5544\}$ .

Zapiszmy teraz liczbę $5544$ w postaci rozkładu na czynniki pierwsze:
$5544 = 2^{3} \cdot 3^{2} \cdot 7 \cdot 11$ .
Zatem liczba całkowita $d \in A$ jest względnie pierwsza z liczbą $5544$ wtedy i tylko wtedy, gdy $d$ nie dzieli się przez żadną z liczb: $2$ , $3$ , $7$ , $11$ .

Obliczymy, ile jest takich liczb w zbiorze $A$ , które nie są względnie pierwsze z liczbą $5544$ .
Zauważmy, że każda taka liczba dzieli się przez co najmniej jedną z liczb ze zbioru $\{2, 3, 7, 11\}$ .
Przyjmujemy oznaczenia:

$A_{2}$ – podzbiór zbioru $A$ , w którym znajdują się wszystkie liczby podzielne przez $2$ ,

$A_{3}$ – podzbiór zbioru $A$ , w którym znajdują się wszystkie liczby podzielne przez $3$ ,

$A_{7}$ – podzbiór zbioru $A$ , w którym znajdują się wszystkie liczby podzielne przez $7$ ,

$A_{11}$ – podzbiór zbioru $A$ , w którym znajdują się wszystkie liczby podzielne przez $11$ .

Korzystając z reguły równolicznościreguła równolicznościreguły równoliczności obliczamy:
$|A_{2}| = \frac{1}{2} \cdot 5544 = 2772$ ,
$|A_{3}| = \frac{1}{3} \cdot 5544 = 1848$ ,
$|A_{7}| = \frac{1}{7} \cdot 5544 = 792$ ,
$|A_{11}| = \frac{1}{11} \cdot 5544 = 504$ ,
$|A_{2} \cap A_{3}| = \frac{1}{2 \cdot 3} \cdot 5544 = 924$ ,
$|A_{2} \cap A_{7}| = \frac{1}{2 \cdot 7} \cdot 5544 = 396$ ,
$|A_{2} \cap A_{11}| = \frac{1}{2 \cdot 11} \cdot 5544 = 252$ ,
$|A_{3} \cap A_{7}| = \frac{1}{3 \cdot 7} \cdot 5544 = 264$ ,
$|A_{3} \cap A_{11}| = \frac{1}{3 \cdot 11} \cdot 5544 = 168$ ,
$|A_{7} \cap A_{11}| = \frac{1}{7 \cdot 11} \cdot 5544 = 72$ ,
$|A_{2} \cap A_{3} \cap A_{7}| = \frac{1}{2 \cdot 3 \cdot 7} \cdot 5544 = 132$ ,
$|A_{2} \cap A_{3} \cap A_{11}| = \frac{1}{2 \cdot 3 \cdot 11} \cdot 5544 = 84$ ,
$|A_{2} \cap A_{7} \cap A_{11}| = \frac{1}{2 \cdot 7 \cdot 11} \cdot 5544 = 36$ ,
$|A_{3} \cap A_{7} \cap A_{11}| = \frac{1}{3 \cdot 7 \cdot 11} \cdot 5544 = 24$ ,
$|A_{2} \cap A_{3} \cap A_{7} \cap A_{11}| = \frac{1}{2 \cdot 3 \cdot 7 \cdot 11} \cdot 5544 = 12$ .

Wobec tego korzystając z zasady włączeń i wyłączeń otrzymujemy, że
$|A_{2} \cup A_{3} \cup A_{7} \cup A_{11}| = |A_{2}| + |A_{3}| + |A_{7}| + |A_{11}| +$

$- (|A_{2} \cap A_{3}| + |A_{2} \cap A_{7}| + |A_{2} \cap A_{11}| + |A_{3} \cap A_{7}| + |A_{3} \cap A_{11}| +$

$+ |A_{7} \cap A_{11}|) + (|A_{2} \cap A_{3} \cap A_{7}| + |A_{2} \cap A_{3} \cap A_{11}| + |A_{2} \cap A_{7} \cap A_{11}| +$

$+ |A_{3} \cap A_{7} \cap A_{11}|) - |A_{2} \cap A_{3} \cap A_{7} \cap A_{11}| =$

$= (2772 + 1848 + 792 + 504) - (924 + 396 + 252 + 264 + 168 + 72) +$

$+ (132 + 84 + 36 + 24) - 12 = 5916 - 2076 + 276 - 12 = 4104$ .

Zatem dodatnich liczb całkowitych względnie pierwszych z liczbą $5544$ , które nie są większe od $5544$ jest $5544 - 4104 = 1440$ .

Warto sprawdzić, że odpowiedź do zadania można również zapisać w postaci
$5544 \cdot (1 - \frac{1}{2}) \cdot (1 - \frac{1}{3}) \cdot (1 - \frac{1}{7}) \cdot (1 - \frac{1}{11})$ ,

Uwaga. Rozpatrzmy dodatnią liczbę całkowitą $n$ , w której rozkładzie na czynniki pierwsze występują (z niezerowym wykładnikiem) wyłącznie parami różne liczby pierwsze $p_{1}$ , $p_{2}$ , $. . .$ , $p_{k}$ .
Oznaczamy wtedy przez $φ (n)$ funkcję (nazywaną funkcją Eulera lub tocjentem), która rozpatrywanej liczbie całkowitej $n$ przypisuje liczbę liczb względnie pierwszych z $n$ , które nie są większe od $n$ .
Wtedy
$φ (n) = n \cdot (1 - \frac{1}{p_{1}}) \cdot (1 - \frac{1}{p_{2}}) \cdot . . . \cdot (1 - \frac{1}{p_{k}})$ .
Dowód z wykorzystaniem zasady włączeń i wyłączeń przebiega podobnie, jak w rozwiązaniu powyższego przykładu.

Przykład 7

Rozpatrzmy losowe rozmieszczenie $7$ kul (ponumerowanych od $1$ do $7$ ) w $7$ różnych pudełkach (również ponumerowanych od $1$ do $7$ ).
Obliczymy, na ile różnych sposobów można dane kule rozmieścić w tych pudełkach tak, aby w każdym pudełku znalazła się dokładnie jedna kula, której numer jest różny od numeru pudełka.

Rozwiązanie

Zauważmy, że każdy wynik rozmieszczenia $7$ parami różnych kul w $7$ parami różnych pudełkach można zapisać jako $7$ –elementową permutacjępermutacja zbioru $n$ –elementowegopermutację $(k_{1}, k_{2}, k_{3}, k_{4}, k_{5}, k_{6}, k_{7})$ zbioru $\{1, 2, 3, 4, 5, 6, 7\}$ , gdzie przez $k_{i}$ , dla $i = 1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ oznaczyliśmy numer pudełka do którego wpadła kula o numerze $i$ .
Wobec tego wszystkich możliwych rozmieszczeń $7$ parami różnych kul w $7$ parami różnych pudełkach jest $7! = 5040$ .

Mamy obliczyć, ile jest permutacjipermutacja zbioru $n$ –elementowegopermutacji $(k_{1}, k_{2}, k_{3}, k_{4}, k_{5}, k_{6}, k_{7})$ , w których $k_{i} \neq i$ dla $i = 1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ .

Obliczymy, ile jest takich permutacjipermutacja zbioru $n$ –elementowegopermutacji, które nie spełniają tego warunku.
W tym celu oznaczmy:

przez $A_{1}$ – zbiór tych permutacjipermutacja zbioru $n$ –elementowegopermutacji, w których $k_{1} = 1$ (wtedy kula z numerem $1$ wpadła do pudełka numer $1$ ),

przez $A_{2}$ – zbiór tych permutacjipermutacja zbioru $n$ –elementowegopermutacji, w których $k_{2} = 2$ (wtedy kula z numerem $2$ wpadła do pudełka numer $2$ ),

przez $A_{3}$ – zbiór tych permutacjipermutacja zbioru $n$ –elementowegopermutacji, w których $k_{3} = 3$ (wtedy kula z numerem $3$ wpadła do pudełka numer $3$ ),

przez $A_{4}$ – zbiór tych permutacjipermutacja zbioru $n$ –elementowegopermutacji, w których $k_{4} = 4$ (wtedy kula z numerem $4$ wpadła do pudełka numer $4$ ),

przez $A_{5}$ – zbiór tych permutacjipermutacja zbioru $n$ –elementowegopermutacji, w których $k_{5} = 5$ (wtedy kula z numerem $5$ wpadła do pudełka numer $5$ ),

przez $A_{6}$ – zbiór tych permutacjipermutacja zbioru $n$ –elementowegopermutacji, w których $k_{6} = 6$ (wtedy kula z numerem $6$ wpadła do pudełka numer $6$ ),

przez $A_{7}$ – zbiór tych permutacjipermutacja zbioru $n$ –elementowegopermutacji, w których $k_{7} = 7$ (wtedy kula z numerem $7$ wpadła do pudełka numer $7$ ).

Zatem wszystkich permutacjipermutacja zbioru $n$ –elementowegopermutacji opisujących sytuację, gdy co najmniej jedna z kul wpadła do pudełka o tym samym numerze jest tyle, ile jest elementów zbioru $A_{1} \cup A_{2} \cup A_{3} \cup A_{4} \cup A_{5} \cup A_{6} \cup A_{7}$ .

Ponieważ:
$|A_{1}| = |A_{2}| = |A_{3}| = |A_{4}| = |A_{5}| = |A_{6}| = |A_{7}| = 6!$
$|A_{1} \cap A_{2}| = |A_{1} \cap A_{3}| = . . . = |A_{6} \cap A_{7}| = 5!$
$|A_{1} \cap A_{2} \cap A_{3}| = |A_{1} \cap A_{3} \cap A_{4}| = . . . = |A_{5} \cap A_{6} \cap A_{7}| = 4!$
$|A_{1} \cap A_{2} \cap A_{3} \cap A_{4}| = . . . = |A_{4} \cap A_{5} \cap A_{6} \cap A_{7}| = 3!$
$|A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap A_{5}| = . . . = |A_{3} \cap A_{4} \cap A_{5} \cap A_{6} \cap A_{7}| = 2!$
$|A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap A_{5} \cap A_{6}| = . . . = |A_{2} \cap A_{3} \cap A_{4} \cap A_{5} \cap A_{6} \cap A_{7}| = 1!$
$|A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap A_{5} \cap A_{6} \cap A_{7}| = 1$

więc korzystając z zasady włączeń i wyłączeń otrzymujemy stąd, że
$|A_{1} \cup A_{2} \cup A_{3} \cup A_{4} \cup A_{5} \cup A_{6} \cup A_{7}| =$
$= (|A_{1}| + |A_{2}| + |A_{3}| + |A_{4}| + |A_{5}| + |A_{6}| + |A_{7}|) +$
$- (|A_{1} \cap A_{2}| + |A_{1} \cap A_{3}| + . . . + |A_{6} \cap A_{7}|) +$
$+ (|A_{1} \cap A_{2} \cap A_{3}| + |A_{1} \cap A_{2} \cap A_{4}| + . . . + |A_{5} \cap A_{6} \cap A_{7}|) +$
$- (|A_{1} \cap A_{2} \cap A_{3} \cap A_{4}| + . . . + |A_{4} \cap A_{5} \cap A_{6} \cap A_{7}|) +$
$+ (|A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap A_{5}| + . . . + |A_{3} \cap A_{4} \cap A_{5} \cap A_{6} \cap A_{7}|) +$
$- (|A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap A_{5} \cap A_{6}| + . . . + |A_{2} \cap A_{3} \cap A_{4} \cap A_{5} \cap A_{6} \cap A_{7}|) +$
$+ |A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap A_{5} \cap A_{6} \cap A_{7}| =$
$= (\begin{matrix} 7 \\ 1 \end{matrix}) \cdot 6! - (\begin{matrix} 7 \\ 2 \end{matrix}) \cdot 5! + (\begin{matrix} 7 \\ 3 \end{matrix}) \cdot 4! - (\begin{matrix} 7 \\ 4 \end{matrix}) \cdot 3! + (\begin{matrix} 7 \\ 5 \end{matrix}) \cdot 2! - (\begin{matrix} 7 \\ 6 \end{matrix}) \cdot 1! + (\begin{matrix} 7 \\ 7 \end{matrix}) \cdot 1 =$
$= 7! - \frac{7!}{2!} + \frac{7!}{3!} - \frac{7!}{4!} + \frac{7!}{5!} - \frac{7!}{6!} + \frac{7!}{7!} =$
$= 5040 - 2520 + 840 - 210 + 42 - 7 + 1 = 3186$ .

Oznacza to, że wszystkich sposobów rozmieszczenia danych kul w pudełkach tak, aby w każdym pudełku znalazła się dokładnie jedna kula, która ma numer różny od numeru pudełka jest $5040 - 3186 = 1854$ .

Otrzymany wynik można również zapisać w postaci
$1854 = 5040 - 3186 = 7! - (7! - \frac{7!}{2!} + \frac{7!}{3!} - \frac{7!}{4!} + \frac{7!}{5!} - \frac{7!}{6!} + \frac{7!}{7!}) =$
$= \frac{7!}{2!} - \frac{7!}{3!} + \frac{7!}{4!} - \frac{7!}{5!} + \frac{7!}{6!} - \frac{7!}{7!} = 7! \cdot (\frac{1}{2!} + \frac{1}{3!} - \frac{1}{4!} + \frac{1}{5!} - \frac{1}{6!} + \frac{1}{7!})$ .

Uwaga. Permutacjapermutacja zbioru $n$ –elementowegoPermutacja $(k_{1}, k_{2}, . . ., k_{n})$ zbioru $\{1, 2, . . ., n\}$ , której wyrazy spełniają warunek $k_{i} \neq i$ dla $i = 1$ , $2$ , $. . .$ , $n$ nazywana jest nieporządkiem.

Liczbę nieporządków danego zbioru $n$ –elementowego oznacza się przez $D_{n}$ lub za pomocą symbolu $! n$ , nazywanego podsilnią (lub dolną silnią).
Wówczas
$D_{n} =! n = n! \cdot (\frac{1}{2!} + \frac{1}{3!} - \frac{1}{4!} + . . . + \frac{1}{n!})$

Dowód z wykorzystaniem zasady włączeń i wyłączeń przebiega podobnie, jak w rozwiązaniu powyższego przykładu.

Słownik

permutacja zbioru

n

–elementowego

permutacja zbioru

n

–elementowego

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

liczba wszystkich permutacji zbioru

n

-elementowego

liczba wszystkich permutacji zbioru

n

-elementowego

liczba wszystkich permutacji zbioru $n$ -elementowego jest równa $P_{n} = n!$

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}|$

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 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 . . . \cdot k_{n}$

wariacja z powtórzeniami

$k$ –wyrazowy ciąg o elementach wybieranych dowolnie (czyli z powtórzeniami) ze zbioru $n$ –elementowego

liczba wszystkich

k

–elementowych wariacji z powtórzeniami zbioru

n

-elementowego

liczba wszystkich

k

–elementowych wariacji z powtórzeniami zbioru

n

-elementowego

liczba wszystkich $k$ -elementowych wariacji z powtórzeniami zbioru
$n$ -elementowego jest równa $n^{k}$

Wprowadzenie

Animacja

Słownik