kombinatoryka, rozmieszczenie kul w szufladach desperatos: Zadanie z kombinatorki które męczy mnie już drugi dzień. Na ile sposobów można rozmieścić "k" rozróżnialnych kul w "n" oznaczonych szufladach tak aby żadna szuflada nie była pusta. Oczywiście z założenia k > n.
2 paź 08:50
jc: Kulom przypisujesz szuflady, przy czym masz wykorzystać wszystkie szuflady. Każdemu wyborowi odpowiada podział kul na n niepustych grup według numerów szuflad. Liczbę takich podziałów nazywa się liczbą Stirlinga. Odwrotnie, jak podzielisz kule na n niepustych grup, to otrzymane grupy możesz włożyć do szuflad na n! sposobów. Nie ma zwartego wzoru. Możesz stosować zasadę włączania wyłączania. Spróbuję wyjaśnić na przykładzie. Załóżmy, że n=3 i k=5. Q = wszystkie rozmieszczenia, |Q| = 35 A = pierwsza szuflada pusta, |A|=25, mamy tylko 2 szuflady, |AB|=1, tylko 1 szuflada B = druga pusta C trzecia pusta Interesuje nas |Q−A−B−C| = |Q|−|A|−|B|−|C| + |AB| + |AC|+|BC|−|ABC| = 35 − 3*25 + 3*15 = 243−96+3
2 paź 09:07
Saizou : rysunek Albo tak mamy k kul i ustawiamy je w ciąg i teraz między kule ustawiamy patyczki, takich miejsc na patyczki jest k−1 i z nich wybieramy n−1 miejsc, ponieważ mamy n szuflad ale n−1 miejsc na patyczki
 
nawias
k−1
nawias
nawias
n−1
nawias
 
łącznie takich podziałów jest
  
2 paź 12:10
jc: Saizou, kule są rozróżnialne!
2 paź 12:33
desperatos: Dzięki za odpowiedzi, ale tak 1) jc: zdarzenia A i B nie są rozłączne (np. wszystkie kule mogą znajdować się w 3−ciej szulfadzie). Poza tym "zwarty wzór" istnieje, o niego jest pytanie w treści zadania. 2) Saizou: Nie wziąłeś pod uwagę że kule są rozróżnialne, podany wzór byłby poprawny dla identycznych kul
2 paź 12:37
desperatos: edit: jc doczytałem Twoją wypowiedź widzę że wziąłeś rozłączność zdarzeń pod uwagę. Zwracam Honor. Jednak w dalszym ciągu nie jest to odpowiedź na pytanie o wzórk dla n i k
2 paź 12:40
jc: Czy taki wzór nazwiesz zwartym wzorem?
 
nawias
n
nawias
nawias
j
nawias
 
Liczba możliwości = ∑j=0n (−1)j
(n−j)k
  
2 paź 14:05
desperatos: Jak najbardziej. Dziękuję za rozwiązanie
2 paź 15:33
Saizou : Faktycznie emotka nie doczytalem tego
3 paź 15:47