Výběr z množiny předmětů

Úloha číslo: 3425

Z \(n\) předmětů vybíráme \(k\). Do následující tabulky doplňte počty možných výběrů:

Výběry Záleží na pořadí (variace) Nezáleží na pořadí (kombinace)
bez opakování
s opakováním
  • Řešení

    Záleží-li na pořadí, lze výběr popsat jako zobrazení \(f\), kde \(f(i)\) označuje předmět vybraný v \(i\)-tém kole. Jde tedy o zobrazení z množiny pořadových čísel vybíraných předmětů \(\{1,…,k\}\) do množiny předmětů.

    Nemají-li se předměty opakovat, jde o prosté zobrazení. Pokud se opakovat mohou, jde o libovolné zobrazení.

    Nezáleží-li na pořadí a předměty se opakovat nemohou, vybíráme \(k\)-prvkovou množinu z \(n\)-prvkové.

    Pokud se předměty opakovat mohou, zapíšeme si výběr jako \(n\)-tici \((x_1,…,x_n)\), kde \(x_i\) značí počet opakování \(i\)-tého předmětu ve výběru. Zřejmě platí \(x_1+… +x_n=k\). Zapíšeme-li si v součtu čísla v unární soustavě, dostaneme posloupnost s \(k\) jedničkami a \(n-1\) plusy. Každá taková posloupnost kóduje jednoznačně nějaký výběr a naopak.

  • Odpověď

    Výběry Záleží na pořadí (variace) Nezáleží na pořadí (kombinace)
    bez opakování \(\frac{n!}{(n-k)!}\) \(\binom{n}{k}\)
    s opakováním \(n^k\) \(\binom{n+k-1}{k}\)
Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze