rozmieszczenie kul w pudełkach

[tralalala]

Mam takie oto zadanie:
Na ile sposobów można rozmieścić \(\displaystyle{ 5}\) kul w czterech ponumerowanych pudełkach
a. jeżeli kule są rozróżnialne
b. jeżeli kule są nierozróżnialne
c. jeżeli kule są identyczne i żadne pudełko nie pozostaje puste

I teraz nie wiem do końca kiedy stosować wzory na wariacje, a kiedy na kombinacje;
ktoś mi doradził żebym w a. zastosowała \(\displaystyle{ n^{k}}\) czyli \(\displaystyle{ 4 ^{5}}\) ale powie mi ktoś dlaczego stosujemy tu wzór na wariacje z powtórzeniami, a nie bez?
jak rozgryźć b i c?

[Gouranga]

a) skoro jedna kula może być tylko w jednym pudełku, ale w jednym pudełku może być wiele kul, to masz funkcję \(\displaystyle{ f: kule \rightarrow pudełka}\)
każdej z 5 kul przyporządkowujesz numer pudełka stąd \(\displaystyle{ 4^5}\)

b)
to można ugryźć dwojako, albo funkcją generującą (ale to jak to ktoś tutaj mawiał "strzelanie z armaty do muchy") albo na separatorach
do podziału na 4 pudełka potrzebujemy 3 separatorów (zawsze o 1 mniej niż pudełek)
taki podział może wyglądać np. tak:
\(\displaystyle{ oo|o|o|o}\) gdzie \(\displaystyle{ o}\) to kula, \(\displaystyle{ |}\) separator
widać tu, że w pierwszym pudełku będą dwie, w pozostałych po jednej
można równie dobrze rozmieścić tak:
\(\displaystyle{ ||ooo|oo}\) gdzie w 3 będą 3, w 4 będą dwie a pierwsze 2 pudła puste
to prowadzi nas do tego, że jest 8 miejsc (5 kul + 3 separatory) i wybieramy z nich 5 miejsc na kule, na pozostałe wstawiamy separatory, ten podział \(\displaystyle{ k}\) kul do \(\displaystyle{ n}\) pudełek określamy wzorem:
\(\displaystyle{ \left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose k}}\)
w twoim przykładzie:
\(\displaystyle{ \left\langle \begin{array}{c}5\\4\end{array}\right\rangle = {8 \choose 5}}\)

c) tu wystarczy zastosować prosty myk, wrzucamy po 1 kuli do każdego pudełka, zostaje \(\displaystyle{ 1}\) kula do \(\displaystyle{ 4}\) pudełek i to rozpracowujesz tym samym wzorem co b)


a jeśli chodzi o rozwiązanie b) funkcją generującą to mamy do rozwiązania równanie:
\(\displaystyle{ x_1 + x_2 + x_3 + x_4 = 5}\)
gdzie \(\displaystyle{ x_i}\) to ilość kul w i-tym pudełku
w każdym pudełku może być od 0 do 5 kul co daje nam funkcję:
\(\displaystyle{ \left(z^0 + z^1 + z^2 + z^3 + z^4 + z^5\right)^4}\)
po przemnożeniu wszystkiego dostajemy
\(\displaystyle{ z^{20}+4 z^{19}+10 z^{18}+20 z^{17}+35 z^{16}+56 z^{15}+80 z^{14}+104 z^{13}+125 z^{12}+140 z^{11}+146 z^{10}+140 z^9+125 z^8+104 z^7+80 z^6+56 z^5+35 z^4+20 z^3+10 z^2+4 z+1}\)

patrzymy teraz tylko, że wystąpiło \(\displaystyle{ 56z^5}\) (bo interesuje nas rozwiązanie 5) i mamy wynik \(\displaystyle{ 56}\) sposobów

przy czym jeśli przemnożenie wszystkiego wykracza poza nasze możliwości akceptowanym rozwiązaniem jest podanie samej funkcji w postaci:
\(\displaystyle{ \left(z^0 + z^1 + z^2 + z^3 + z^4 + z^5\right)^4\quad \left[z^5\right]}\)

czyli że rozwiązaniem jest współczynnik przy \(\displaystyle{ z^5}\) w rozwinięciu tej funkcji

[tralalala]

ok dzięki wielkie, a jak mam zadanie, w którym i kule i pudełka są rozróżnialne ale w każdym mają być po dwie to robię tak samo z tymi separatorami tylko że zamiast tamtego wzoru postawiam pod \(\displaystyle{ (n+k-1)!/k! \cdot (n-1)!}\) ? np jeśli jest \(\displaystyle{ 6}\) rozróżnialnych kul i \(\displaystyle{ 3}\) rozróżnialne pudełka to będę miała \(\displaystyle{ 2}\) separatory więc \(\displaystyle{ 8}\) miejsc wobec tego wstawiam w miejsce \(\displaystyle{ k}\) kule i pod \(\displaystyle{ n}\) ogólną liczbę miejsc?

[Gouranga]

Nie. Separatory tylko jak nierozróżnialne kule do rozróżnialnych pudełek.
jak masz \(\displaystyle{ k}\) kul do \(\displaystyle{ n}\) pudeł oba rozróżnialne i w każdym pudle po dwie kule to masz
\(\displaystyle{ {k \choose 2}{k-2 \choose 2}\ldots {k-2(n-1) \choose 2}\cdot n^{k-2n} = n^{k-2n} \prod_{i=0}^{n-1}{k-2i \choose 2}}\)
bo wybierasz dwie kule do pierwszego pudełka, z tego co zostało 2 kule do drugiego itd. i na końcu jak coś zostanie to tak jak w podpunkcie a) dowolnie