Rozmisťování kuliček
Úloha číslo: 3426
Rozmísťujeme \(k\) kuliček do \(n\) přihrádek. Do následující tabulky doplňte počty možných výběrů:
Kuličky jsou |
V každé přihrádce je | ||
---|---|---|---|
nejvýše jedna | libovolně mnoho | alespoň jedna | |
různobarevné | |||
stejnobarevné |
Řešení
Výběry různobarevných kuliček odpovídají zobrazením \(f\), kde \(f(i)\) určuje přihrádku, kam padla \(i\)-tá kulička. Je-li v každé přihrádce nejvýše jedna kulička, jde o prostá zobrazení.
Zobrazení na se spočítají pomocí principu inkluze a exkluze a to tak, že spočítáme snáze zobrazení, která nejsou na. Pokud \(A_j\) značí množinu zobrazení \(f\), kde prvek \(j\) není v obrazu \(f\), dostaneme \(\left|\bigcap\limits_{j\in I} A_j\right|=(n-|I|)!\). Výsledný vzorec je aplikací principu inkluze a exkluze na průniky s indexovou množinou \(I\) velikosti \(i\).
Vybíráme-li stejnobarevné kuličky a do každé přihrádky přijde nejvýše jedna, odpovídá to volbě \(k\) prvkové podmnožiny přihrádek, kde přihrádky ve vevybrané množině budou ty s kuličkami.
Pokud do přihrádky může přijít více kuliček, odpovídá to součtu \(x_1+…+x_n=k\), kde \(x_i\) značí počet kuliček v \(i\)-té přihrádce.
Má-li být v každé přihrádce alespoň jedna kulička, oddělíme nejprve \(n\) kuliček, do každé přihrádky dáme po jedné a zbytek rozdělíme jako v předchozím případě.
Odpověď
Kuličky
jsouV každé přihrádce je nejvýše jedna libovolně mnoho alespoň jedna různobarevné \(\frac{n!}{(n-k)!}\) \(n^k\) \(\sum\limits_{i=0}^{n-1} (-1)^i \binom{n}{i} (n-i)^k \) stejnobarevné \(\binom{n}{k}\) \(\binom{n+k-1}{k}\) \(\binom{k-1}{n-1}\)