Na ile sposobów...

[restarcik]

1. Święty Mikołaj chce rozdać \(\displaystyle{ m}\) czekoladek \(\displaystyle{ n}\) dzieciom. Na ile sposobów może to zrobić, jeśli:
a) czekoladki są różne oraz dokładnie \(\displaystyle{ k}\) dzieci ma dostać co najmniej jedną czekoladkę,
b) czekoladki są jednego rodzaju i dokładnie \(\displaystyle{ k}\) dzieci ma dostać co najmniej jedną czekoladkę,
c) czekoladki są różne, a każde dziecko może dostać ich dowolną liczbę?

2. Na ile sposobów Święty Mikołaj może włożyć \(\displaystyle{ k}\) spośród l ciastek do dokładnie \(\displaystyle{ m}\) spośród \(\displaystyle{ n}\) pudełek, jeśli:
a) ciastka są nierozróżnialne, a pudelka rozróżnialne,
b) ciastka są rozróżnialne, a pudełka rozróżnialne,
c) ciastka są rozróżnialne, a pudełka nierozróżnialne,
d) ciastka są nierozróżnialne, a pudełka nierozróżnialne.

[MrCommando]

A jakieś własne próby?

[restarcik]

Trochę ich było, ale nigdy nie wiedziałem co zrobić z dziećmi \(\displaystyle{ n-k}\) w pierwszym i wszystkie moje pomysły utykały :/

A co do drugiego to miałem odpowiednio takie pomysły:
a)skoro ciastka są nierozróżnialne to mamy ich po prostu k na 1 sposób, do \(\displaystyle{ {n\choose m}}\) pudełek,
czyli dzielimy \(\displaystyle{ k }\) ciastek na \(\displaystyle{ m}\) pudełek (ale żadne nie może być puste) \(\displaystyle{ P(k,m)}\) tzn podział \(\displaystyle{ k}\) na \(\displaystyle{ m}\) składników =>\(\displaystyle{ {n\choose m}~\cdot~P(k,m)}\)

b)wybieramy \(\displaystyle{ {l\choose k}}\) ciastek, \(\displaystyle{ {n\choose m}}\) pudełek i z liczb Sterlinga drugiego rodzaju mamy:
\(\displaystyle{ {l\choose k} ~\cdot~{n\choose m}~\cdot~S_2(k,m)~\cdot~m!}\)

c) tu podobnie ale zostaje nam tylko wybór ciastek bez pudełek i ich permutacji tzn:
\(\displaystyle{ {l\choose k} ~\cdot~S_2(k,m)}\)

d) skoro nic nie jest rozróżnialne to po prostu podział \(\displaystyle{ k}\) na \(\displaystyle{ m}\) składników => \(\displaystyle{ P(k,m)}\)

[MrCommando]

Rzuciłem okiem i podpunkty b) i d) wyglądają na dobrze zrobione. Mam nadzieję, że nigdzie niżej się nie pomyliłem, bo dość na szybko to robiłem:

a)skoro ciastka są nierozróżnialne to mamy ich po prostu k na 1 sposób, do \(\displaystyle{ {n\choose m}}\) pudełek,
czyli dzielimy \(\displaystyle{ k }\) ciastek na \(\displaystyle{ m}\) pudełek (ale żadne nie może być puste) \(\displaystyle{ P(k,m)}\) tzn podział \(\displaystyle{ k}\) na \(\displaystyle{ m}\) składników =>\(\displaystyle{ {n\choose m}~\cdot~P(k,m)}\)

Ale tutaj przecież pudełka są rozróżnialne, więc metoda z tymi podziałami nie jest dobra, bo w takim przypadku traktujesz pudełka jak nierozróżnialne i nie precyzujesz ile ciastek ma być w którym pudełku. Zamiast tego lepiej wyznaczyć liczbę rozwiązań równania \(\displaystyle{ x_1+\dots+x_m=k}\) w liczbach całkowitych nieujemnych. Tutaj \(\displaystyle{ x_i}\) oznacza liczbę ciastek w \(\displaystyle{ i}\)-tym pudełku. Metoda wykorzystująca podziały raczej lepiej się przyda w d).

Natomiast w przypadku c) otrzymujesz za mało możliwości. O ile mi wiadomo to liczby Stirlinga drugiego rodzaju mówią ile jest podziałów jakiegoś zbioru na pewną liczbę NIEPUSTYCH podzbiorów. Ale pamiętajmy, że niektóre pudełka mogą być puste. Więc trzeba wysumować jeszcze przypadki, gdy pusta jest jedna, dwie, trzy itd. szuflady.

Jeśli chodzi o pierwsze to może tak:

a) Najpierw wybieramy \(\displaystyle{ k}\) dzieci i dajemy im po jednej czekoladzie. Zostaje nam \(\displaystyle{ m-k}\) czekolad, które mamy już rozdzielić w dowolny sposób.

b) Ponownie wybieramy \(\displaystyle{ k}\) dzieci spośród \(\displaystyle{ n}\) i szukamy liczby rozwiązań równania \(\displaystyle{ x_1+\dots+x_n=m}\) w liczbach całkowitych nieujemnych, przy czym zakładamy, że \(\displaystyle{ x_1,x_2,\dots,x_k\geq 1}\).

c) Popatrz na to tak jak na przypisywanie każdej czekoladce dziecka, które ją otrzyma. Wynik to liczba funkcji ze zbioru czekoladek w zbiór dzieci, czyli liczba funkcji ze zbioru \(\displaystyle{ m}\)-elementowego w \(\displaystyle{ n}\)-elementowy.

[rivit]

a) Najpierw wybieramy \(\displaystyle{ k}\) dzieci i dajemy im po jednej czekoladzie. Zostaje nam \(\displaystyle{ m-k}\) czekolad, które mamy już rozdzielić w dowolny sposób.

To jak w takim razie to będzie wyglądać? :/
Bo musimy uwzględnić dzieci, które nic nie dostają. Czy to będzie suma jakaś?

[Rafsaf]

Up, 1 a)

\(\displaystyle{ {n \choose k } \cdot n ^{m-k} }\)

[rivit]

@up
A dlaczego nie będzie tu liczby Stirlinga?
Podzielimy pozostałe czekolady na \(\displaystyle{ n}\) grup i każdemu dziecku przypiszemy jakaś czekoladę (\(\displaystyle{ n!}\) Permutacja tych grup)

[MrCommando]

Liczby Stirlinga tu niezbyt pasują, bo przecież niektóre dzieci mogły nie dostać żadnej czekolady. Rozważmy nasze \(\displaystyle{ m-k}\) czekolad. Pierwszą z nich możemy rozdać na \(\displaystyle{ n}\) sposobów, drugą też, trzecią też i tak dalej, zatem ostatecznie \(\displaystyle{ n^{m-k}}\). Formalnie liczność funkcji ze zbioru \(\displaystyle{ [m-k]}\) w zbiór \(\displaystyle{ [n]}\).