Na ile sposobów

[max123321]

Na ile sposobów można rozdać trojgu dzieciom 10 jednakowych baloników oraz 10 różnych zabawek, tak, aby każde dziecko coś dostało?

Jak to zrobić?

[MrCommando]

Niech \(\displaystyle{ X}\) będzie zbiorem wszystkich możliwych rozdań trójce dzieci dziesięciu nierozróżnialnych batoników i dziesięciu rozróżnialnych zabawek. Wtedy \(\displaystyle{ |X|=\binom{10+3-1}{3-1}\cdot 3^{10}}\). Niech \(\displaystyle{ A_i}\) oznacza zbiór takich rozdań, że \(\displaystyle{ i}\)-te dziecko coś dostaje dla \(\displaystyle{ i\in[3]}\). Chcemy obliczyć \(\displaystyle{ |A_1 \cap A_2 \cap A_3|}\). Z praw de Morgana otrzymujemy
\(\displaystyle{ |A_1 \cap A_2 \cap A_3|=|X|-|A_1' \cup A_2' \cup A_3'|}\) (gdzie oczywiście dopełniamy w zbiorze \(\displaystyle{ X}\)). Zauważmy, że mamy \(\displaystyle{ |A_i'|=\binom{10-1}{2-1} \cdot \left(2^{10}-2\right)}\) dla \(\displaystyle{ i\in[3]}\) oraz \(\displaystyle{ |A_i' \cap A_j'|=1}\) dla \(\displaystyle{ i\neq j}\) oraz \(\displaystyle{ |A_1' \cap A_2' \cap A_3'|=0}\). Zatem z zasady włączeń i wyłączeń otrzymujemy:

\(\displaystyle{ |A_1 \cap A_2 \cap A_3|=|X|-|A_1' \cup A_2' \cup A_3'|=|X|-\sum_{k=1}^{3}(-1)^{k+1}\sum_{I \subseteq [3], |I|=k} \left| \bigcap_{i\in I} A_i' \right|=\\=\binom{10+3-1}{3-1}\cdot 3^{10}-\binom{3}{1}\binom{10-1}{2-1}\cdot (2^{10}-2)+\binom{3}{2}\cdot 1-\binom{3}{3}\cdot 0=\\=\binom{12}{2}\cdot 3^{10}-27\cdot(2^{10}-2)+3}\).

Korzystałem tutaj między innymi z tego, że liczba rozwiązań równania \(\displaystyle{ x_1+x_2+\dots+x_k=n}\) w liczbach całkowitych dodatnich to \(\displaystyle{ \binom{n-1}{k-1}}\), a w liczbach całkowitych nieujemnych \(\displaystyle{ \binom{n+k-1}{k-1}}\). Przykładowo liczba rozdań trójce dzieci dziesięciu nierozróżnialnych cukierków jest równa właśnie liczbie rozwiązań równania \(\displaystyle{ x_1+x_2+x_3=10}\) w liczbach całkowitych nieujemnych, czyli właśnie \(\displaystyle{ \binom{10+3-1}{3-1}}\).

[max123321]

Tak zgadzam się, ale skąd jest to \(\displaystyle{ -2}\) ? Chodzi mi o drugi składnik. Z zasady włączeń i wyłączeń mamy, że od wszystkich możliwości odejmujemy, te, że jeden smarkacz nic nie dostanie, reszta dowolnie i dodajemy, że dwóch smarkaczy nic nie dostaje, więc czy to nie powinno być:

\(\displaystyle{ \binom{12}{2}\cdot 3^{10}-3 {11 \choose 1} \cdot2^{10}+3}\)

Ten środkowy czynnik to jest, że na \(\displaystyle{ 3}\) sposoby możemy wybrać bachora, który nic nie dostaje i pomiędzy pozostałych dwóch rozdzielamy baloniki, które możemy pomiędzy nich rozdzielić na \(\displaystyle{ {11 \choose 1}}\) sposobów. Następnie wybieramy pierwszą zabawkę i możemy jej przydzielić jednego z dwóch smarkaczy czyli zabawki możemy rozdać na \(\displaystyle{ 2^{10}}\) sposobów. Dlaczego tak jest źle?

[MrCommando]

max123321, zgadzam się z tym. Wybacz, w trakcie pisania obliczeń na moment wyłączyłem myślenie i nie wiedzieć dlaczego założyłem, że \(\displaystyle{ A_i'}\) oznacza, że dokładnie jedno dziecko (i-te) nic nie dostaje i napisałem coś innego niż myślałem (a rzecz jasna tak nie jest).