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 30200, 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?
5 gru 19:29
Satan: Poprawka: tam ma być 30200, w (a)
5 gru 19:30
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
5 gru 19:53
Pytający: Rozwiązanie jest skomplikowane, o ile na siłę je sobie utrudniamy, przecież:
 
nawias
200
nawias
nawias
k
nawias
 
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).
5 gru 20:51
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 20030, (b) masz dobrze Satanie.
5 gru 20:52
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".
5 gru 21:03
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:
 
nawias
200 − 1 + 30
nawias
nawias
30
nawias
 
(a')
  
 
nawias
200
nawias
nawias
30
nawias
 
(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ą.
5 gru 21:10
Satan: PW, fakt, to ładniej brzmi, a raczej jednoznacznie, więc poniekąd mogłem Cię wprowadzić w błąd.
5 gru 21:13
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. x1+x2+...+x200=30 liczba rozwiązań tego równania w zbiorze liczb całkowitych nieujemnych będzie odpowiedzią. Ta liczba to:
nawias
30+200−1
nawias
nawias
200−1
nawias
 
nawias
229
nawias
nawias
199
nawias
 
nawias
229
nawias
nawias
30
nawias
 
=
=
   
 
nawias
n
nawias
nawias
k
nawias
 
nawias
n
nawias
nawias
n−k
nawias
 
=
   
5 gru 21:20
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! 
 
nawias
200−1+30
nawias
nawias
200−1
nawias
 
nawias
200−1+30
nawias
nawias
30
nawias
 
=
=
.
   
5 gru 21:32
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 emotka
5 gru 21:33
Satan: O, takie zobrazowanie Pytającego jest nawet lepsze, choć spotkałem się już z zapisem sumy od x1 do x200. Problem był po prostu myślowy − powinienem ponumerować osoby, a tego nie zrobiłem.
5 gru 21:37