Rozdawanie 12 pączków 4 osobom.

[hakermatrix]

Na ile sposobów można podzielić 12 pączków między 4 osoby tak, by każda dostała"
a) przynajmniej jeden;
b) przynajmniej dwa?

[Xitami]

Pączki można rozdać na 455 sposobów, tak by każdy dostał choć jednego tylko na 165 sposobów,
a tak by każdy dostał minimum dwa już tylko na 35 sposobów.
Powinno się dać zrobić prościej niż przez wyliczenie wszystkich możliwości (z ograniczeniami) czy przez funkcje tworzące.

[hakermatrix]

A mógł byś napisać jak to policzyć? Bardziej interesuje mnie metoda niż gotowy wynik.

[UNIX_admin]

zastanow sie (lub poszukaj n aforum - bylo juz o tym wielokrotnie) na ile sposobow mozna wlozyc 12 kul do 4 koszy, lub rozwiazac rownanie a+b+c+d=12 w liczbach calkowitych dodatnich

[arek1357]

z funkcji tworzącej warunek a+b+c+d=12
przy założeniu że a>=1 b>=1 c>=1 d>=1

funkcja tworząca:

(a+aa+...)(b+bb+...)*...

zresztą w tym pierwszym przypadku będzie:

\(\displaystyle{ {12-1} \choose {4-1}}\)

[Qń]

Najłatwiej skorzystać z wzoru na liczbę podziałów liczby naturalnej \(\displaystyle{ n}\) na \(\displaystyle{ k}\) nieujemnych składników całkowitych (kolejność gra rolę) - \(\displaystyle{ {n+k-1 \choose k-1}}\).

W a) najpierw dajemy każdemu po pączku, a pozostałe 8 pączków rozdzielamy zgodnie z powyższym wzorem na \(\displaystyle{ {11 \choose 3}}\) sposobów (warto się zastanowić dlaczego możemy tu skorzystać z powyższego wzoru, to znaczy dlaczego jest to analogiczne zadanie). Natomiast w b) najpierw każdemu dajemy po dwa pączki, a pozostałe 4 pączki rozdzielamy na \(\displaystyle{ {7 \choose 3}}\) sposobów.

Q.

[arek1357]

Ale wzór na ilość rozwiązań równania tak żeby każada wartość była >=1 jest:

\(\displaystyle{ n-1 \choose k-1}\)

gdzie n to liczba a k to ilośc niewiadomych

[Qń]

A ogólniej: liczba rozwiązań rzeczonego równania w liczbach całkowitych większych bądź równych od \(\displaystyle{ a}\) wynosi \(\displaystyle{ {n+(1-a)k-1 \choose k-1}}\), co jest prostym wnioskiem z podstawowego wzoru.

Q.

[UNIX_admin]

tak sobie mysle, ze moze warto by bylo wrzucic do kompendium jakis watek (tak, zeby przy wyszukiwaniu byla latwy do znalenienia) z objasnieniem, ze dzielenie n kul na k koszy, czy szukanie liczby rozwiazan rownania, czy szukanie liczby najkrotszych drog z A do B i wiele innych problemow sprowadza sie do jednego i koresponduje z wyzej przytoczonym wzorem. bo przeciez co chwila pojawiaja sie takie zadania i za kazdym razem sa na nowo rozwiazywane

[hakermatrix]

Dzięki wielkie za pomoc można chyba powiedzieć, że to rozumiem.

[laser15]

może mi ktoś wytłumaczyć z czego wynika tutaj różnica: najpierw rozdaje po 1 pączku, a potem pozostałe 8 przydzielam losowo więc mam : \(\displaystyle{ 4!{11 \choose 3}}\) natomiast korzystając ze wzoru:\(\displaystyle{ {n+(1-a)k-1 \choose k-1}}\) gdzie a=1 otrzymuję samo \(\displaystyle{ {11 \choose 3}}\)
Gdzie leży błąd w moim rozumowaniu ?