Przeczytaj

Poniżej prezentujemy omówienie przykładowych zadań dotyczących rozmieszczeń.

Z zasady ilustracją dla omawianego typu problemu jest rozmieszczanie kul w pojemnikach.
Należy mieć na uwadze, że zadanie dotyczące rozmieszczeń może być też sformułowane w innym kontekście - kluczowa jest wtedy umiejętność przeprowadzenia analizy treści zadania tak, aby rozpoznać typ rozpatrywanego w nim rozmieszczenia.

Zaczynamy od problemów odwołujących się do doświadczeń polegających na rozmieszczaniu parami różnych obiektów (np. ponumerowanych kul) w parami różnych pojemnikach (np. różniących się kolorem).

Przykład 1

Rozmieszczamy $7$ kul ponumerowanych od $1$ do $7$ w czterech pojemnikach: białym, niebieskim, czerwonym oraz zielonym. Obliczymy, ile jest sposobów rozmieszczenia tych kul tak, aby spełniony był warunek:
a) w zielonym pojemniku znajdą się dokładnie $3$ kule,
b) pojemnik biały będzie pusty,
c) pojemnik biały będzie pusty lub pojemnik niebieski będzie pusty,
d) w każdym pojemniku będzie co najmniej $1$ kula.

Rozwiązanie

Oznaczmy:

przez $k_{i}$ – kulę z numerem $i$ , gdzie $i = 1, 2, 3, 4, 5, 6, 7$ ,
przez $b$ – pojemnik biały,
przez $n$ – pojemnik niebieski,
przez $cz$ – pojemnik czerwony,
przez $z$ – pojemnik zielony.

Zauważmy, że rozpatrywane doświadczenie możemy opisać w następujący sposób:
każdej kuli ze zbioru $\{k_{1}, k_{2}, k_{3}, k_{4}, k_{5}, k_{6}, k_{7}\}$ przypisujemy dokładnie jeden z pojemników ze zbioru $\{b, n, c z, z\}$ , do którego ta kula została wrzucona.
Wynika stąd, że każdy wynik rozpatrywanego rozmieszczenia kul możemy zapisać jako siedmioelementowy ciąg $(k_{1}, k_{2}, k_{3}, k_{4}, k_{5}, k_{6}, k_{7})$ , w którym $k_{i} \in \{b, n, c z, z\}$ , dla $i = 1, 2, 3, 4, 5, 6, 7$ (zatem wszystkich wyników rozpatrywanego rozmieszczenia kul jest $4^{7} = 16384$ ).

a) W zielonym pojemniku znajdą się dokładnie $3$ kule wtedy i tylko wtedy, gdy w ciągu $(k_{1}, k_{2}, k_{3}, k_{4}, k_{5}, k_{6}, k_{7})$ na dokładnie $3$ miejscach wystąpi element $z$ .
Ponieważ takie $3$ miejsca w ciągu wybierzemy z $7$ dostępnych na tyle sposobów, ile jest $3$ –elementowych kombinacjikombinacji zbioru $7$ –elementowego, czyli $(\begin{matrix} 7 \\ 3 \end{matrix}) = 35$ , a każdemu z pozostałych $4$ wyrazów ciągu przypiszemy jeden z trzech pojemników $b, n, c z$ na $3^{4} = 81$ sposobów, więc korzystając z reguły mnożeniareguła mnożeniareguły mnożenia obliczamy, że wszystkich możliwości jest w tym przypadku $(\begin{matrix} 7 \\ 3 \end{matrix}) \cdot 3^{4} = 35 \cdot 81 = 2835$ .

Uwaga. Gdybyśmy dodatkowo zażyczyli sobie, żeby w zielonym pojemniku znalazły się konkretne $3$ kule, np. te z numerami $1$ , $2$ oraz $3$ , to możliwości rozmieszczenia kul byłoby, oczywiście, $3^{4} = 81$ .

b) Pojemnik biały będzie pusty wtedy i tylko wtedy, gdy w ciągu $(k_{1}, k_{2}, k_{3}, k_{4}, k_{5}, k_{6}, k_{7})$ nie wystąpi element $b$ , czyli gdy każdemu z wyrazów tego ciągu przypiszemy jeden z elementów trzyelementowego zbioru $\{n, c z, z\}$ . Wynika stąd, że w tym przypadku jest $3^{7} = 2187$ możliwości.

c) Oznaczmy:

przez $A$ – zbiór wszystkich rozmieszczeń, w których pojemnik biały będzie pusty,
przez $B$ – zbiór wszystkich rozmieszczeń, w których pojemnik niebieski będzie pusty.

Mamy obliczyć $|A \cup B|$ - liczbę takich rozmieszczeń, że pojemnik biały będzie pusty lub pojemnik niebieski będzie pusty.

Z obliczeń przeprowadzonych w poprzednim podpunkcie wiemy, że $|A| = 3^{7} = 2187$ . Rozumując podobnie obliczymy, że $|B| = 3^{7} = 2187$ .
Ponadto, oba pojemniki: biały oraz niebieski będą puste wtedy i tylko wtedy, gdy w ciągu $(k_{1}, k_{2}, k_{3}, k_{4}, k_{5}, k_{6}, k_{7})$ nie wystąpi żaden z elementów $b$ , $n$ , czyli gdy każdemu z wyrazów tego ciągu przypiszemy jeden z elementów dwuelementowego zbioru $\{c z, z\}$ . Zatem $|A \cap B| = 2^{7} = 128$ .

Wobec tego
$|A \cup B| = |A| + |B| - |A \cap B| = 3^{7} + 3^{7} - 2^{7} = 2 \cdot 2187 - 128 = 4246$ .

d) Zauważmy, że wszystkie rozmieszczenia (a jest ich ogółem $4^{7}$ ) możemy podzielić na dwie rozłączne grupy:
grupa pierwsza – takie rozmieszczenia, że w każdym pojemniku będzie co najmniej jedna kula (ich liczbę mamy wyznaczyć),
grupa druga – takie rozmieszczenia, że co najmniej jeden z czterech pojemników będzie pusty.

Oznaczmy:

przez $A$ – zbiór wszystkich rozmieszczeń, w których pojemnik biały będzie pusty,
przez $B$ – zbiór wszystkich rozmieszczeń, w których pojemnik niebieski będzie pusty,
przez $C$ – zbiór wszystkich rozmieszczeń, w których pojemnik czerwony będzie pusty,
przez $D$ – zbiór wszystkich rozmieszczeń, w których pojemnik zielony będzie pusty.

Wówczas liczbę elementów drugiej grupy opiszemy jako $|A \cup B \cup C \cup D|$ , a więc szukana liczba elementów pierwszej grupy jest równa
$4^{7} - |A \cup B \cup C \cup D|$ .

Na podstawie spostrzeżeń poczynionych wcześniej obliczamy, że:
$|A| = |B| = |C| = |D| = 3^{7}$ , a więc $|A| + |B| + |C| + |D| = 4 \cdot 3^{7}$ ,
$|A \cap B| = |A \cap C| = |A \cap D| = |B \cap C| = |B \cap D| = |C \cap D| = 2^{7}$ , a więc $|A \cap B| + |A \cap C| + |A \cap D| + |B \cap C| + |B \cap D| + |C \cap D| = 6 \cdot 2^{7}$ .

Zauważamy ponadto, że:

jest tylko jedna możliwość rozmieszczenia kul w przypadku, gdy dokładnie $3$ pojemniki sa puste, skąd $|A \cap B \cap C| = |A \cap B \cap D| = |A \cap C \cap D| = |B \cap C \cap D| = 1$ , a więc $|A \cap B \cap C| + |A \cap B \cap D| + |A \cap C \cap D| + |B \cap C \cap D| = 4 \cdot 1$ ,
nie jest możliwe, żeby rozmieścić kule tak, aby każdy z $4$ pojemników był pusty, co oznacza, że $|A \cap B \cap C \cap D| = 0$ .

Zatem, korzystając z reguły włączeń i wyłączeńreguła włączeń i wyłączeńreguły włączeń i wyłączeń, otrzymujemy, że
$|A \cup B \cup C \cup D| = 4 \cdot 3^{7} - 6 \cdot 2^{7} + 4 \cdot 1 = 8748 - 768 + 4 = 7984$ .
Stąd $4^{7} - |A \cup B \cup C \cup D| = 16384 - 7984 = 8400$ .

Wobec tego otrzymujemy, że jest $8400$ takich rozmieszczeń rozpatrywanych kul, że w każdym pojemniku będzie co najmniej $1$ kula.

Uwaga. Rozwiązanie zadania w podpunktu d) można przeprowadzić rozpatrując rozłączne przypadki ze względu na rozkład liczby kul w pojemnikach.

Jeśli chcemy rozmieścić $7$ ponumerowanych kul w $4$ różnych pojemnikach tak, aby w każdym z nich znalazła się co najmniej $1$ kula, to możliwe są trzy następujące przypadki:
(1) w jednym z pojemników znajdą się $4$ kule (taki pojemnik wybierzemy na $4$ sposoby, a kule, które w nim umieścimy – na $(\begin{matrix} 7 \\ 4 \end{matrix}) = 35$ sposobów), a w każdym z pozostałych $3$ pojemników będzie po $1$ kuli (te $3$ kule rozmieścimy w trzech pozostałych pojemnikach na $3! = 6$ sposobów); korzystając z reguły mnożeniareguła mnożeniareguły mnożenia obliczamy, że w tym przypadku jest $4 \cdot (\begin{matrix} 7 \\ 4 \end{matrix}) \cdot 3! = 4 \cdot 35 \cdot 6 = 840$ możliwości,
(2) w jednym z pojemników znajdą się $3$ kule (taki pojemnik wybierzemy na $4$ sposoby, a kule, które w nim umieścimy – na $(\begin{matrix} 7 \\ 3 \end{matrix}) = 35$ sposobów), w innym znajdą się $2$ kule (taki pojemnik wybierzemy na $3$ sposoby, a kule, które w nim umieścimy – na $(\begin{matrix} 4 \\ 2 \end{matrix}) = 6$ sposobów), a w każdym z pozostałych $2$ pojemników będzie po $1$ kuli (te $2$ kule rozmieścimy w dwóch pozostałych pojemnikach na $2$ sposoby); korzystając z reguły mnożeniareguła mnożeniareguły mnożenia obliczamy, że w tym przypadku jest $4 \cdot (\begin{matrix} 7 \\ 3 \end{matrix}) \cdot 3 \cdot (\begin{matrix} 4 \\ 2 \end{matrix}) \cdot 2 = 4 \cdot 35 \cdot 3 \cdot 6 \cdot 2 = 5040$ możliwości,
(3) w jednym z pojemników znajdzie się $1$ kula (taki pojemnik wybierzemy na $4$ sposoby, a kulę, którą w nim umieścimy – na $7$ sposobów), a w każdym z pozostałych $3$ pojemników będą po $2$ kule (te $6$ kul rozmieścimy w trzech pozostałych pojemnikach na $(\begin{matrix} 6 \\ 2 \end{matrix}) \cdot (\begin{matrix} 4 \\ 2 \end{matrix}) = 15 \cdot 6 = 90$ sposobów); korzystając z reguły mnożeniareguła mnożeniareguły mnożenia obliczamy, że w tym przypadku jest $4 \cdot 7 \cdot (\begin{matrix} 6 \\ 2 \end{matrix}) \cdot (\begin{matrix} 4 \\ 2 \end{matrix}) = 4 \cdot 7 \cdot 15 \cdot 6 = 2520$ możliwości.

Korzystając z reguły dodawaniareguła dodawaniareguły dodawania, obliczamy, że jest $840 + 5040 + 2520 = 8400$ takich rozmieszczeń rozpatrywanych kul, że w każdym pojemniku będzie co najmniej $1$ kula.

Przykład 2

Rozmieszczamy $7$ kul, ponumerowanych od $1$ do $7$ , w siedmiu pojemnikach, ponumerowanych od $1$ do $7$ . Obliczymy, ile jest sposobów rozmieszczenia tych kul tak, aby:
a) dokładnie $4$ pojemniki pozostały puste,
b) dokładnie $2$ pojemniki pozostały puste.

Rozwiązanie

a) Zauważmy, że:

$4$ pojemniki, w których nie znajdzie się żadna kula wybierzemy spośród wszystkich siedmiu na tyle sposobów, ile jest $4$ –elementowych kombinacjikombinacji zbioru $7$ –elementowego, czyli $(\begin{matrix} 7 \\ 4 \end{matrix}) = 35$ ,
w każdym z pozostałych trzech pojemników musimy rozmieścić po co najmniej $1$ kuli spośród wszystkich $7$ dostępnych; rozumując podobnie, jak w poprzednim przykładzie i stosując regułę włączeń i wyłączeńreguła włączeń i wyłączeńregułę włączeń i wyłączeń obliczamy, że jest $3^{7} - 3 \cdot 2^{7} + 3 = 1806$ wszystkich takich rozmieszczeń.

Wobec tego, na podstawie reguły mnożeniareguła mnożeniareguły mnożenia obliczamy, że jest $(\begin{matrix} 7 \\ 4 \end{matrix}) \cdot (3^{7} - 3 \cdot 2^{7} + 3) = 35 \cdot 1806 = 63210$ rozmieszczeń, które spełniają warunki zadania.

b) Rozwiązanie przedstawimy dwoma sposobami.

$I$ sposób:

Zauważmy, że:

$2$ pojemniki, w których nie znajdzie się żadna kula wybierzemy spośród wszystkich siedmiu na tyle sposobów, ile jest $2$ –elementowych kombinacjikombinacji zbioru $7$ –elementowego, czyli $(\begin{matrix} 7 \\ 2 \end{matrix}) = 21$ ,
w każdym z pozostałych pięciu pojemników musimy rozmieścić po co najmniej $1$ kuli spośród wszystkich $7$ dostępnych; stosując regułę włączeń i wyłączeńreguła włączeń i wyłączeńregułę włączeń i wyłączeń obliczamy, że jest $5^{7} - 5 \cdot 4^{7} + 10 \cdot 3^{7} - 10 \cdot 2^{7} + 5 = 16800$ wszystkich takich rozmieszczeń.

Wobec tego, na podstawie reguły mnożeniareguła mnożeniareguły mnożenia obliczamy, że jest $(\begin{matrix} 7 \\ 2 \end{matrix}) \cdot (5^{7} - 5 \cdot 4^{7} + 10 \cdot 3^{7} - 10 \cdot 2^{7} + 5) = 21 \cdot 16800 = 352800$ rozmieszczeń, które spełniają warunki zadania.

$II$ sposób:

Dwa pojemniki, w których nie znajdzie się żadna kula wybierzemy spośród wszystkich siedmiu na tyle sposobów, ile jest $2$ –elementowych kombinacjikombinacji zbioru $7$ –elementowego, czyli $(\begin{matrix} 7 \\ 2 \end{matrix}) = 21$ .

Zauważmy, że rozmieszczenie $7$ kul w $5$ pojemnikach zgodnie z warunkami zadania możliwe jest w następujących dwóch rozłącznych przypadkach:
(1) w jednym z pojemników znajdą się $3$ kule (ten pojemnik wybierzemy na $5$ sposobów, a kule – na $(\begin{matrix} 7 \\ 3 \end{matrix}) = 35$ sposobów), a w pozostałych $4$ pojemnikach rozmieścimy po $1$ kuli (co można zrobić na $4! = 24$ sposoby); w tym przypadku jest więc $5 \cdot (\begin{matrix} 7 \\ 3 \end{matrix}) \cdot 4! = 5 \cdot 35 \cdot 24 = 4200$ możliwych rozmieszczeń,
(2) w dwóch pojemnikach znajdą się po $2$ kule (te pojemniki wybierzemy na $(\begin{matrix} 5 \\ 2 \end{matrix}) = 10$ sposobów, a kule rozmieścimy w nich na $(\begin{matrix} 7 \\ 2 \end{matrix}) \cdot (\begin{matrix} 5 \\ 2 \end{matrix}) = 21 \cdot 10 = 210$ sposobów), a w pozostałych $3$ pojemnikach rozmieścimy po $1$ kuli (co można zrobić na $3! = 6$ sposobów); w tym przypadku jest więc $(\begin{matrix} 5 \\ 2 \end{matrix}) \cdot (\begin{matrix} 7 \\ 2 \end{matrix}) \cdot (\begin{matrix} 5 \\ 2 \end{matrix}) \cdot 3! = 10 \cdot 21 \cdot 10 \cdot 6 = 12600$ możliwych rozmieszczeń.

Na podstawie reguły mnożeniareguła mnożeniareguły mnożenia oraz reguły dodawaniareguła dodawaniareguły dodawania obliczamy, że jest $(\begin{matrix} 7 \\ 2 \end{matrix}) \cdot (5 \cdot (\begin{matrix} 7 \\ 3 \end{matrix}) \cdot 4! + (\begin{matrix} 5 \\ 2 \end{matrix}) \cdot (\begin{matrix} 7 \\ 2 \end{matrix}) \cdot (\begin{matrix} 5 \\ 2 \end{matrix}) \cdot 3!) = 21 \cdot (4200 + 12600) = 352800$ rozmieszczeń, które spełniają warunki zadania

Przykład 3

Mamy do dyspozycji $15$ żetonów, ponumerowanych od $1$ do $15$ . Rozdzielamy te żetony losowo między trzy osoby: Marka, Jarka i Darka tak, żeby każdy z nich dostał $5$ żetonów.
Obliczymy, ile jest możliwości rozdzielenia żetonów w taki sposób, aby u każdego z chłopców suma numerów zapisanych na otrzymanych żetonach była parzysta.

Rozwiązanie

Zauważmy, że chłopiec otrzyma $5$ żetonów, na których są zapisane numery dające w sumie liczbę parzystą wtedy i tylko wtedy, gdy dostanie parzystą liczbę żetonów z numerem nieparzystym. Ponieważ wszystkich żetonów z numerem nieparzystym jest $8$ , więc są dwa rozłączne przypadki podziału żetonów, spełniające powyższy warunek:
(1) jeden z chłopców otrzyma $5$ żetonów z numerami parzystymi (czyli nie otrzyma żadnego żetonu z numerem nieparzystym), a pozostali dwaj otrzymają po $4$ żetony z numerami nieparzystymi i po $1$ żetonie z numerem parzystym,
(2) jeden z chłopców otrzyma $4$ żetony z numerami nieparzystymi i $1$ żeton z numerem parzystym, a pozostali dwaj otrzymają po $2$ żetony z numerami nieparzystymi i po $3$ żetony z numerami parzystymi.

Obliczamy liczbę możliwości rozdzielenia żetonów w przypadku (1):

na $3$ sposoby wybierzemy chłopca, który otrzyma $5$ żetonów z numerami parzystymi i wybierzemy dla niego te $5$ żetonów z $7$ dostępnych na $(\begin{matrix} 7 \\ 5 \end{matrix}) = 21$ sposobów, co daje ogółem $3 \cdot 21 = 63$ możliwości,
drugiemu z chłopców przydzielimy $4$ żetony z numerami nieparzystymi (z dostępnych $8$ ) na $(\begin{matrix} 8 \\ 4 \end{matrix}) = 70$ sposobów i jeden żeton z numerem parzystym (spośród pozostałych do wyboru $2$ ) na $2$ sposoby, co daje ogółem $70 \cdot 2 = 140$ możliwości,
dla trzeciego chłopca zostały $4$ żetony z numerami nieparzystymi i $1$ żeton z numerem parzystym.

Podsumowując: w pierwszym przypadku liczba możliwości przydziału żetonów jest równa $63 \cdot 140 = 8820$ .

Obliczamy liczbę możliwości rozdzielenia żetonów w przypadku (2):

na $3$ sposoby wybierzemy chłopca, który otrzyma $4$ żetony z numerami nieparzystymi i jeden żeton z numerem parzystym. Wybierzemy dla niego żetony z numerem nieparzystym ( $4$ żetony z $8$ dostępnych) na $(\begin{matrix} 8 \\ 4 \end{matrix}) = 70$ sposobów i jeden żeton z numerem parzystym (z $7$ dostępnych) na $7$ sposobów, co daje ogółem $3 \cdot 70 \cdot 7 = 1470$ możliwości,
drugiemu z chłopców przydzielimy $2$ żetony z numerami nieparzystymi (z dostępnych $4$ ) na $(\begin{matrix} 4 \\ 2 \end{matrix}) = 6$ sposobów i trzy żetony z numerem parzystym (spośród pozostałych do wyboru $6$ ) na $(\begin{matrix} 6 \\ 3 \end{matrix}) = 20$ sposobów, co daje ogółem $6 \cdot 20 = 120$ możliwości,
dla trzeciego chłopca zostały $2$ żetony z numerami nieparzystymi i $3$ żetony z numerami parzystymi.

Podsumowując: w przypadku (2) liczba możliwości przydziału żetonów jest równa $1470 \cdot 120 = 176400$ .

Ostatecznie obliczamy (korzystając z reguły dodawaniareguła dodawaniareguły dodawania ), że wszystkich możliwości rozdzielenia żetonów zgodnie z warunkami zadania jest $8820 + 176400 = 185220$ .

W kolejnych przykładach pokazujemy, jak rozwiązywać zadania dotyczące rozmieszczania nieodróżnialnych obiektów (np. jednakowych kul) w parami różnych pojemnikach.

Przykład 4

Obliczymy, na ile sposobów możemy rozmieścić $8$ jednakowych kul w trzech pudełkach: białym, niebieskim i zielonym.

Rozwiązanie

Ponieważ tym razem kule są jednakowe, więc dwa rozmieszczenia uznamy za różne, jeżeli odróżniają się one rozkładem liczby kul w poszczególnych pojemnikach.

Aby ustalić, ile jest wszystkich takich rozkładów liczby kul wprowadźmy oznaczenia:

$x_{1}$ – liczba kul, które zostały umieszczone w białym pudełku,
$x_{2}$ – liczba kul, które zostały umieszczone w niebieskim pudełku,
$x_{3}$ – liczba kul, które zostały umieszczone w zielonym pudełku.

Zauważmy, że z warunków zadania otrzymujemy następujące zależności:

$x_{1} \geq 0$ ,
$x_{1} + x_{2} + x_{3} = 8$ .

Korzystając z twierdzenia o liczbie rozwiązań równania $x_{1} + x_{2} + \dots + x_{n} = k$ twierdzenia o liczbie rozwiązań równania $x_{1} + x_{2} + \dots + x_{n} = k$ otrzymujemy, że rozwiązań równania
$x_{1} + x_{2} + x_{3} = 8$ (w przypadku otrzymanego równania przyjmujemy $n = 3$ i $k = 8$ )
w liczbach nieujemnych $x_{1}, x_{2}, x_{3}$ jest
$(\begin{matrix} 8 + 3 - 1 \\ 8 \end{matrix}) = (\begin{matrix} 10 \\ 8 \end{matrix}) = 45$ .

Oznacza to, że jest $45$ sposobów, na które możemy rozmieścić $8$ jednakowych kul w trzech pudełkach: białym, niebieskim i zielonym.

Uwaga. Innym pomysłem na rozwiązanie tego zadania jest rozpatrzenie $10$ rozłącznych przypadków ze względu na możliwe rozkłady liczby kul w pojemnikach. Przy założonej liczbie $8$ kul rozmieszczanych w $3$ pudełkach przypadki takich rozkładów są następujące:
(1) $[8, 0, 0]$ – w tym przypadku są $3$ sposoby rozmieszczenia kul (tyle jest możliwości wyboru pudełka, do którego wrzucimy $8$ kul),
(2) $[7, 1, 0]$ – w tym przypadku jest $3! = 6$ sposobów rozmieszczenia kul,
(3) $[6, 2, 0]$ – w tym przypadku jest $3! = 6$ sposobów rozmieszczenia kul,
(4) $[6, 1, 1]$ – w tym przypadku są $3$ sposoby rozmieszczenia kul,
(5) $[5, 3, 0]$ – w tym przypadku jest $3! = 6$ sposobów rozmieszczenia kul,
(6) $[5, 2, 1]$ – w tym przypadku jest $3! = 6$ sposobów rozmieszczenia kul,
(7) $[4, 4, 0]$ – w tym przypadku są $3$ sposoby rozmieszczenia kul,
(8) $[4, 3, 1]$ – w tym przypadku jest $3! = 6$ sposobów rozmieszczenia kul,
(9) $[4, 2, 2]$ – w tym przypadku są $3$ sposoby rozmieszczenia kul,
(10) $[3, 3, 2]$ – w tym przypadku są $3$ sposoby rozmieszczenia kul.

Ogółem otrzymujemy więc $5 \cdot 6 + 5 \cdot 3 = 30 + 15 = 45$ sposobów rozmieszczenia $8$ jednakowych kul w trzech pudełkach: białym, niebieskim i zielonym.

Przykład 5

Rozmieszczamy $10$ jednakowych kul w czterech pudełkach: białym, niebieskim, czerwonym i zielonym. Obliczymy, na ile sposobów możemy je rozmieścić tak, aby spełniony był warunek:
a) w każdym pudełku znajdzie się co najmniej jedna kula,
b) dokładnie jedno pudełko pozostanie puste.

Rozwiązanie

Mamy do rozmieszczenia jednakowe kule w różnych pojemnikach - pozostaje ustalić, ile jest różnych rozkładów liczby kul w poszczególnych pojemnikach.

a) Ponieważ w każdym z pudełek ma znaleźć się co najmniej jedna kula, więc wprowadzimy takie oznaczenia liczby kul w pojemnikach, które spełnią ten warunek.
Przyjmijmy, że:

$x_{1} + 1$ , gdzie $x_{1} \geq 0$ - liczba kul, które zostały umieszczone w białym pudełku,
$x_{2} + 1$ , gdzie $x_{2} \geq 0$ - liczba kul, które zostały umieszczone w niebieskim pudełku,
$x_{3} + 1$ , gdzie $x_{3} \geq 0$ - liczba kul, które zostały umieszczone w czerwonym pudełku,
$x_{4} + 1$ , gdzie $x_{4} \geq 0$ - liczba kul, które zostały umieszczone w zielonym pudełku.

Ponieważ do rozmieszczenia mamy $10$ jednakowych kul, więc otrzymujemy następującą zależność
$(x_{1} + 1) + (x_{2} + 1) + (x_{3} + 1) + (x_{4} + 1) = 10$ ,
skąd dostajemy, że liczby nieujemne $x_{1}, x_{2}, x_{3}, x_{4}$ spełniają równanie
$x_{1} + x_{2} + x_{3} + x_{4} = 6$ .

Korzystając z twierdzenia o liczbie rozwiązań równania $x_{1} + x_{2} + \dots + x_{n} = k$ twierdzenia o liczbie rozwiązań równania $x_{1} + x_{2} + \dots + x_{n} = k$ (w przypadku otrzymanego równania przyjmujemy $n = 4$ oraz $k = 6$ ) otrzymujemy, że są $(\begin{matrix} 6 + 4 - 1 \\ 6 \end{matrix}) = (\begin{matrix} 9 \\ 6 \end{matrix}) = 84$ takie rozmieszczenia, że w każdym pudełku znajdzie się co najmniej jedna kula.

b) Załóżmy bez straty ogólności, że puste będzie pudełko białe (i od razu zauważmy, że zamieniając kolor pustego pudełka z białego na każdy z pozostałych trzech kolorów dostaniemy za każdym razem tę samą liczbę rozmieszczeń).

Aby zapewnić sobie rozmieszczenie, w którym każde z pozostałych pudełek nie będzie puste wprowadzamy następujące oznaczenia:

$x_{1} + 1$ , gdzie $x_{1} \geq 0$ – liczba kul, które zostały umieszczone w niebieskim pudełku,
$x_{2} + 1$ , gdzie $x_{2} \geq 0$ – liczba kul, które zostały umieszczone w czerwonym pudełku,
$x_{3} + 1$ , gdzie $x_{3} \geq 0$ – liczba kul, które zostały umieszczone w zielonym pudełku.

Ponieważ do rozmieszczenia mamy $10$ jednakowych kul, więc otrzymujemy następującą zależność
$(x_{1} + 1) + (x_{2} + 1) + (x_{3} + 1) = 10$ ,
skąd dostajemy, że liczby nieujemne $x_{1}, x_{2}, x_{3}$ spełniają równanie
$x_{1} + x_{2} + x_{3} = 7$ .

Korzystając z twierdzenia o liczbie rozwiązań równania $x_{1} + x_{2} + \dots + x_{n} = k$ twierdzenia o liczbie rozwiązań równania $x_{1} + x_{2} + \dots + x_{n} = k$ (w którym przyjmujemy $n = 3$ oraz $k = 7$ ) otrzymujemy, że w tym przypadku jest
$(\begin{matrix} 7 + 3 - 1 \\ 7 \end{matrix}) = (\begin{matrix} 9 \\ 7 \end{matrix}) = 36$ możliwych rozmieszczeń.

Oznacza to, że ogółem jest $4 \cdot (\begin{matrix} 9 \\ 7 \end{matrix}) = 4 \cdot 36 = 144$ takich rozmieszczeń, że jedno pudełko pozostanie puste.

Ostatni przykład jest prezentacją metody rozwiązywania zadań, w których parami różne obiekty (np. ponumerowane kule) rozmieszczamy w nieodróżnialnych pojemnikach (np. takich samych pudełkach).

Przykład 6

a) Mamy do dyspozycji $9$ kul, ponumerowanych od $1$ do $9$ . Rozmieszczamy te kule w trzech takich samych białych pudełkach.
Obliczymy, ile jest możliwości rozdzielenia kul w taki sposób, aby w każdym pudełku znalazły się $3$ kule.

Rozwiązanie

Zauważmy, że jeżeli pudełka ponumerujemy od $1$ do $3$ , to możemy rozmieszczanie kul rozłożyć na $3$ etapy:
(1) wybieramy $3$ kule spośród wszystkich $9$ (co możemy zrobić na $(\begin{matrix} 9 \\ 3 \end{matrix}) = 84$ sposoby) i umieszczamy je w pudełku numer $1$ ,
(2) z pozostałych $6$ kul wybieramy $3$ (co możemy zrobić na $(\begin{matrix} 6 \\ 3 \end{matrix}) = 20$ sposobów) i umieszczamy je w pudełku numer $2$ ,
(3) pozostałe $3$ kule umieszczamy w pudełku numer $3$ .

Wynika stąd, że rozpatrywana liczba rozmieszczeń w trzech pudełkach, które odróżniliśmy numerami, jest równa $(\begin{matrix} 9 \\ 3 \end{matrix}) \cdot (\begin{matrix} 6 \\ 3 \end{matrix}) = 84 \cdot 20 = 1680$ .

Przy ustalonym rozmieszczeniu kul opisanym powyżej zamiana trójki numerów zapisanych na pudełkach (zauważmy, że różnych ponumerowań tych trzech pudełek jest $3! = 6$ ) opisuje już inne rozmieszczenie. Jednakże pudełka, w których rozmieszczamy kule są jednakowe, zatem każde rozmieszczenie opisane w treści zadania w wyniku numerowania (odróżniania) pudełek jest liczone dokładnie $6$ razy. Wynika stąd, że jest $\frac{(\begin{matrix} 9 \\ 3 \end{matrix}) \cdot (\begin{matrix} 6 \\ 3 \end{matrix})}{3!} = \frac{1680}{6} = 280$ wszystkich rozmieszczeń $9$ kul, ponumerowanych od $1$ do $9$ , w trzech takich samych białych pudełkach w taki sposób, aby w każdym pudełku znalazły się $3$ kule.

Uwaga. Problem z powyższego przykładu warto sformułować następująco.
Ile jest sposobów podziału $9$ –elementowego zbioru $X = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ na $3$ podzbiory $3$ –elementowe?
Jeżeli założymy, że w wyniku podziału zbioru $X$ otrzymaliśmy trzy podzbiory: $A$ , $B$ oraz $C$ , to podział ten jest dla nas zbiorem $\{A, B, C\}$ , którego elementami są opisane podzbiory.
Jeżeli natomiast elementy do tych podzbiorów będziemy przydzielali kolejno: najpierw $3$ elementy ze zbioru $X$ przydzielimy do zbioru $A$ , następnie z pozostałych $6$ wybierzemy $3$ elementy do zbioru $B$ , a ostatnie $3$ elementy przydzielimy do zbioru $C$ (co, jak pokazaliśmy powyżej, można zrobić na $(\begin{matrix} 9 \\ 3 \end{matrix}) \cdot (\begin{matrix} 6 \\ 3 \end{matrix}) = 84 \cdot 20 = 1680$ sposobów), to podział otrzymany w ten sposób opiszemy jako uporządkowaną trójkę $(A, B, C)$ , która jest $3$ –elementową permutacjąpermutacja zbioru $n$ –elementowegopermutacją zbioru $\{A, B, C\}$ .
Ponieważ jest $3! = 6$ takich permutacji, więc wszystkich permutacji $(A, B, C)$ jest $6$ razy więcej, niż podziałów $\{A, B, C\}$ .
Oznacza to, że jest $\frac{1680}{6} = 280$ podziałów $9$ –elementowego zbioru $X = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ na $3$ podzbiory $3$ –elementowe.

b) Mamy do dyspozycji $9$ kul, ponumerowanych od $1$ do $9$ . Rozmieszczamy te kule w czterech takich samych białych pudełkach.
Obliczymy, ile jest możliwości rozdzielenia kul w taki sposób, aby w jednym pudełku znalazły się $3$ kule, a w pozostałych trzech pudełkach znalazły się po $2$ kule.

Rozwiązanie

Jeśli rozważymy wszystkie podziały $9$ –elementowego zbioru $X = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ na $4$ podzbiory, przy czym jeden z nich ma być $3$ –elementowy (oznaczymy go jako $A$ ), natomiast pozostałe trzy (oznaczone jako $B$ , $C$ oraz $D$ ) mają być $2$ –elementowe, to tych podziałów jest tyle, ile zbiorów postaci $\{A, \{B, C, D\}\}$ .
Rozumując podobnie jak to jest zapisane w Uwadze do poprzedniego podpunktu, obliczymy, że jest $(\begin{matrix} 9 \\ 3 \end{matrix}) \cdot \frac{(\begin{matrix} 6 \\ 2 \end{matrix}) \cdot (\begin{matrix} 4 \\ 2 \end{matrix})}{3!} = \frac{7460}{6} = 1260$ możliwości podziału zbioru $9$ –elementowego na cztery podzbiory, z których jeden jest $3$ –elementowy, a pozostałe dwa są $2$ –elementowe.

Wobec tego jest $1260$ możliwości rozmieszczenia $9$ kul ponumerowanych od $1$ do $9$ w czterech takich samych białych pudełkach w taki sposób, aby w jednym pudełku znalazły się $3$ kule, a w każdym z pozostałych trzech pudełek znalazły się po $2$ kule.

Słownik

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

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

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

twierdzenie o liczbie rozwiązań równania

x_{1} + x_{2} + \dots + x_{n} = k

twierdzenie o liczbie rozwiązań równania

x_{1} + x_{2} + \dots + x_{n} = k

liczba wszystkich rozwiązań równania

x_{1} + x_{2} + \dots + x_{n} = k

w nieujemnych liczbach całkowitych $x_{1}, x_{2}, \dots, x_{n}$ , gdzie $n$ oraz $k$ to ustalone dodatnie liczby całkowite, jest równa

(\begin{matrix} k + n - 1 \\ k \end{matrix})

Wprowadzenie

Test samosprawdzający

Słownik