kombinacje z powtórzeniami
PuRXUTM:
hej
wytłumaczyłby mi ktoś kombinacje z powtórzeniami ?
Mam takie zadanie, mam wybrać n ciastek z k rodzajów ciastek. Na ile sposobów mogę to zrobić.
Wiem jaka jest odpowiedź i mniej więcej schemat działania, ale nie rozumiem dlaczego tak jest
robimy to tak że robimy przegrody pomiędzy ciastkami które wybraliśmy, te przegrody odpowiadają
za to że różne odmiany ciastek są osobno.
Dlaczego rozwiązanie jest takie jakie jest
| | | | | |
wiem że | = | i tu chyba chodzi o to że wybieramy k−1 przegród ale |
| | | |
dlaczego tak jest
PW: Przedstawienie liczby n w postaci sumy k składników:
(1) x
1 + x
2 + ... + x
k = n,
x
i∊{0,1,...,n}. Składnik "i" oznacza liczbę ciastek wziętych z rodzaju "i". Zakładamy, że
każdy rodzaj ciastek ma liczność co najmniej n (żeby można było wziąć np. tylko ciastka
pierwszego rodzaju). Rozróżniamy kolejność składników. Wtedy rozumowanie może wyglądać tak:
Do zbioru n kulek białych dorzucamy k−1 kulek czarnych i losujemy po jednej kuli. Dopóki
losowane kule są białe − ich liczba oznacza pierwszy składnik. W momencie wylosowania kuli
czarnej odkładamy ją na bok i rozpoczynamy następne losowanie. Dopóki losowane kule są białe,
ich liczba oznacza drugi składnik. W momencie wylosowania kuli czarnej odkładamy ją na bok i
rozpoczynamy następne losowanie. I tak dalej, aż do losowania o numerze k. Takie losowanie
spełnia warunki zadania − w skrajnych przypadkach można wylosować tak, że składnik nr p jest
zerem (za pierwszym razem w losowaniu nr p wylosowana kula jest czarna), ale może też być tak,
że jeden ze składników jest równy n, a pozostałe są zerami (w losowaniu nr p wyciągamy same
białe kule, a w poprzednich i następnych czarne). Liczba sum postaci (1) jest więc równa
liczbie permutacji z powtórzeniami n+k−1 elementów, wśród których jest n jednakowych i k−1
innych − też jednakowych. Permutacji takich jest jak wiadomo
