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
    jsou
    V 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}\)
Obtížnost: Středně těžká úloha
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze