Kombinatoryka Satan: Mamy 30 nagród i 200 osób, przy czym nagrody są rozróżnialne. (a) Na ile sposobów można rozdać nagrody, jeśli każdy może dostać dowolną liczbę nagród? Czyli do każdej nagrody można przypisać 200 osób, więc to będzie 30²00, tak? (b) Każda osoba może otrzymać co najwyżej jedną nagrodę Czyli każdej nagrodzie można przypisać o jedną osobę mniej, niż poprzedniej nagrodzie: 200 * 199 * ... * 172 * 171 A jak to rozwiązać, gdy nagrody są nierozróżnialne? Jak to sobie wyobrazić, jak to działa?

Satan: Poprawka: tam ma być 30²⁰⁰, w (a)

PW: Rozumowanie "każdej nagrodzie można przypisać 200 osób" jest błędne. To ludziom przypisujemy nagrody, a nie odwrotnie. Funkcje f:{1, 2, 3, ..., 200} → {1, 2, 3, ..., 30} też nie opisują dobrze tego co się dzieje. Rozwiązanie jest dość skomplikowane − trzeba podzielić zbiór nagród na wszystkie możliwe podzbiory, a następnie każdemu podziałowi przyporządkować wybraną grupę osób o odpowiedniej liczności i jeszcze permutować te osoby

Pytający: Rozwiązanie jest skomplikowane, o ile na siłę je sobie utrudniamy, przecież:

	200 k
∑k=130(S(30,k)*		*k!)=20030

I nie rozumiem, co jest błędnego w rozumowaniu "każdej nagrodzie można przypisać 200 osób", toć taka nagroda sobie leży i czeka, aż przypisze się ją jakiemuś człowiekowi (czy też przypisze się jej człowieka, ot to samo inaczej sformułowane).

Pytający: https://www.wolframalpha.com/input/?i=200%5E30-(sum+k%3D1..30+of+(stirlings2(30,k)*binomial(200,k)*k!)) Znaczy w (a) poprawna odpowiedź to 200³⁰, (b) masz dobrze Satanie.

PW: Miałem jakieś zaćmienie, na zasadzie "zbyt duża wiedza czasami przeszkadza", dziękuję za naprostowanie. A sformułowanie mnie zmyliło od samego początku, "każdej nagrodzie można przypisać 200 osób" źle brzmi, powinno być "każdej nagrodzie można przypisać jedną z 200 osób".

Satan: Tak, racja, w (a) podałem inny wynik, niż wyraziłem słowami. A co w przypadku, gdy nagrody są nierozróżnialne? Takie mam zadanie i dość to dla mnie ciężkie do zobrazowania. Nie mam pojęcia jak przypisać do nagrody osobę lub na odwrót, gdy wszystko jest jednakowe. W odpowiedziach mam kolejno:

	200 − 1 + 30 30
(a')

	200 30
(b')

O ile jeszcze (b') mogę tłumaczyć, że spośród 200 osób wybieramy 30, które nagrodę dostanie, o tyle (a') jest już pewną dla mnie abstrakcją.

Satan: PW, fakt, to ładniej brzmi, a raczej jednoznacznie, więc poniekąd mogłem Cię wprowadzić w błąd.

Mila: 1) Nagrody nierozróżnialne. Osoby rozróżnialne 200− liczba osób 30 liczba nagród Na ile sposobów możemy przydzielić nagrody? Stosujemy kombinacje z powtórzeniami. x₁+x₂+...+x₂₀₀=30 liczba rozwiązań tego równania w zbiorze liczb całkowitych nieujemnych będzie odpowiedzią. Ta liczba to:

30+200−1 200−1		229 199		229 30
	=		=

	n k		n n−k
		=

Pytający: PW, też mi się zdarzyło tak (sumą z liczbami Stirlinga itd.) odpowiedzieć jakiemuś licealiście. Zdaje mi się, że wtedy Mila napisała to "nieco prostsze" rozwiązanie. Dla nierozróżnialnych nagród można tak: wyobraź sobie, że wszystkie 200 osób stoi w rządku i pomiędzy każdą parą osób jest ścianka. Takich ścianek jest 200−1=199. Gdy nagrody każdej osoby ustawisz przed nią też w rządku (też pomiędzy tymi ściankami), to patrząc z przodu masz 199 ścianek i 30 nagród w jakiejś kolejności. Każda różna kolejność odpowiada oczywiście innemu przyznaniu nagród (nagrody przed pierwszą ścianką są pierwszej osoby, między pierwszą i drugą ścianką są nagrody drugiej osoby itd.). A takich różnych kolejności jest (jak kto woli liczyć):

(200−1+30)!
	= // odpowiednio ścianki i nagrody są nierozróżnialne między sobą
(200−1)!*30!

	200−1+30 200−1		200−1+30 30
=		=		.

Satan: Hm, czyli tu tkwił szkopuł. Brałem osoby za nierozróżnialne od samego początku, kiedy one powinny być rozróżnialne. Co do rozwiązania − wszystko już jasne. Dziękuję Wam

Satan: O, takie zobrazowanie Pytającego jest nawet lepsze, choć spotkałem się już z zapisem sumy od x₁ do x₂00. Problem był po prostu myślowy − powinienem ponumerować osoby, a tego nie zrobiłem.