✖

Variace

Kapitoly: Kombinatorika, Variace, Permutace, Kombinace, Variace s opakováním, Kombinace s opakováním, Kolik existuje různých PINů, Kalkulačka: Kombinační číslo

Variace využijeme, pokud z nějaké množiny objektů vybíráme určitý počet objektů, přičemž záleží na pořadí, v jakém tyto objekty vybíráme.

Odvození vzorce

Začneme typickou úlohou na variace: na vsi se každoročně pořádá soutěž v pojídání švestkových knedlíků. Do finálového kola postoupilo celkem sedm umaštěných závodníků. Spočítejte, kolik celkem existuje možností, jak těchto sedm účastníků může obsadit první tři místa.

Je důležité si uvědomit, že v tomto příkladě záleží na pořadí. Například pokud víme, že se na prvních třech místech umístí Tonda, Matěj a Koloděj, pak tato trojice nám vygeneruje celkem šest různých umístění:

  • Tonda, Matěj, Koloděj;
  • Tonda, Koloděj, Matěj;
  • Matěj, Tonda, Koloděj;
  • Matěj, Koloděj, Tonda;
  • Koloděj, Tonda, Matěj;
  • Koloděj, Matěj, Tonda.

Toto jsou všechno různé umístění a my chceme spočítat, kolik celkem různých umístění dokážeme sestavit, když je těch závodníků 7.

Použijeme k tomu kombinatorické pravidlo součinu. Řekneme, že vybíráme trojice tvaru [x1, x2, x3], kde x1 je závodník, který skončil na prvním místě atd. Které závodníky můžeme dosadit za x1? Všechny, tedy za x1 můžeme dosadit 7 závodníků. Které můžeme dosadit za x2? Všechny, kromě toho, kterého jsme už dosadili na první místo, takže za x2 můžeme dosadit 7 − 1 = 6 závodníků. Za x3 pak můžeme dosadit ty závodníky, kteří nejsou na prvním nebo druhém místě, máme tak 7 − 2 = 5 možností. Aplikujeme kombinatorické pravidlo součinu a získáme celkový počet možností: 7 · 6 · 5 = 210.

Můžeme pozorovat, že když budeme chtít znát počet všech možností na prvních 4 místech, tak za x4 můžeme dosadit 7 − 3 = 4 závodníků, takže celkový počet možností bude 7 · 6 · 5 · 4 = 840. Co z toho můžeme odvodit?

Pokud máme množinu o n prvcích (zde v příkladě 7 jedlíků) a vybíráme 3 prvky, přičemž záleží na pořadí, tak výsledek je roven n · (n − 1) · (n − 2). Na prvním místě se mohou umístit všichni, na dalším o jednoho méně atd. Z toho můžeme odvodit obecný vzorec pro to, když vybíráme k prvků z množiny o n prvcích: počet možností bude roven n · (n − 1) · (n − 2) · … · (n − k + 1).

Tenhle vzorec ještě dále upravíme a to pomocí faktoriálu. Když se podíváme, jak vypadá faktoriál sedmi: 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 a jak jsme počítali počet všech medailových umístění 7 · 6 · 5, tak vidíme jistou podobnost. Potřebujeme se jen zbavit toho konce, tj. potřebujeme 7! podělit 4 · 3 · 2 · 1, čímž nám zůstane jen 7 · 6 · 5. A čemu je roven výraz 4 · 3 · 2 · 1? Je rovný 4!.

Můžeme tak napsat, že máme-li množinu o n prvcích a vybíráme-li celkem k prvků, přičemž záleží na pořadí, máme celkem

$$ V(k, n) = \frac{n!}{(n-k)!} $$

možností. Když si do toho vzorce dosadíme čísla ze švestkového závodu:

$$ V(3, 7) = \frac{7!}{(7-3)!}=\frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{4 \cdot 3 \cdot 2 \cdot 1} = 7 \cdot 6 \cdot 5 = 210. $$

Počítačka

Následující počítačka vám vypočítá počet variací pro dané n a k, včetně postupu.

k:n:

Řešené příklady

  1. Zůstaneme u závodu v jezení knedlíků. Jak by se změnil počet možných medailových umístění, kdybychom věděli, že na závod přijel Ludva Schnitzell, který je machr a vždy vyhraje? Tj. kolik existuje různých medailových umístění, pokud máme 7 závodníků a Ludva jistě vyhraje?

To je opět jednoduchá variace, první příčka je jistá a ze zbývajících 6 závodníků nám zbývá určit, jak mohou zaplnit druhé a třetí místo. Vybíráme tak 2 prvky z 6prvkové množiny, což vede na variaci

$$ V(2, 6) = \frac{6!}{(6-2)!}=30 $$

  1. Kdysi dávno, když ještě Ludva Schnitzell nebyl takový machr, se pravidelně umisťoval mezi prvními třemi. Kolik existuje různých medailových umístění, pokud máme 7 závodníků a Ludva jistě dostane nějakou medaili?

    Tento příklad se od předchozího liší v tom, že nevíme, na kterém místě se Ludva umístil; mohl se umístit až druhý nebo dokonce třetí, za což se dosud stydí. Proto tedy musíme spočítat celkově tři různé variace: v případě, kdy Ludva vyhrál, poté kdyby Ludva dosáhl stříbrné medaile a nakonec bronzové medaile. Ovšem pokaždé zbývají pouze dvě místa, kde se může umístit někdo jiný. Pokud byl například Ludva druhý, ostatní účastníci se mohli umístit buď na prvním anebo na třetím místě. Tedy počítáme opět dvoučlennou variaci z šesti, pouze ji musíme spočítat třikrát, pro tři různé umístění Ludvy. Počet všech umístění je tak roven:

    $$ 3 \cdot V(2, 6) = 3 \cdot \frac{6!}{(6-2)!} = 3 \cdot 30 = 90 $$

    Všimněte si, že tu trojku před variací můžeme napsat jako V(1, 3), protože ve skutečnosti vybíráme jeden prvek (jedno konkrétní umístění) z tříprvkové množiny (tři medailové pozice).

  2. Ve škole je celkem 20 učitelů. Za chvíli budou maturity a je potřeba sestavit komisi v tomto složení: jeden předseda, jeden hodný přísedící a jeden zlý přísedící. Kolik existuje celkem možností?

    Jako první musíme zodpovědět otázku, zda záleží na pořadí — ano záleží, tři učitele můžeme opět rozházet šesti různými způsoby. Teď už je to jednoduché — vybíráme 3člennou variaci z 20 prvků:

    $$ V(3, 20) = \frac{20!}{17!}=6840. $$

  3. Kolik trojciferných čísel můžeme poskládat z číslic {0, 1, 2, 3, 4, 5}, pokud se žádná číslice nesmí opakovat?

    Záleží na pořadí? Ano, záleží, 123 je jiné číslo než 321. Kolik existuje různých trojic? To je jednoduchá 3členná variace z 6:

    $$ V(3, 6) = \frac{6!}{3!}=120. $$

    Ale musíme ještě odečíst ty variace, které mají na prvním místě nulu, protože 012 není trojciferné číslo. Otázka tak nyní zní — kolik existuje různých trojic, které začínají nulou? V takovém případě se střídají číslice pouze na zbývajících dvou místech (trojice mají tvar [0, x2, x3]), takže hledáme, kolik různých dvojic můžeme vytvořit za použití čísel {1, 2, 3, 4, 5}. To je opět jednoduché: V(2, 5) = 5!/3! = 20. Existuje tak 20 trojic, které začínají nulou.

    Celkový počet trojciferných čísel, které jsou složené z číslic {0, 1, 2, 3, 4, 5}, je tak 120 − 20 = 100.

  4. Kolik různých tříciferných čísel dokážeme sestavit z číslic {1, 2, 3, 4, 5}, pokud se žádná číslice nesmí opakovat a výsledné číslo má být liché?

    Na pořadí záleží, protože 123 je jiné číslo než 321. Skládáme tříciferné číslo, které je liché, což znamená, že na prvních dvou pozicích může být libovolná číslice, ale na posledním musí být jedno z číslic {1, 3, 5}. Nejprve spočítáme počet všech trojic, které jsme schopni poskládat z pěti číslic: V(3, 5) = 5! / 2! = 60.

    Každá číslice se na bude na poslední místě vyskytovat stejně často, takže pokud máme 5 číslic, tak se každá číslice bude na posledním místě vyskytovat 60 / 5 = 12krát. Máme tři číslice {1, 3, 5}, které se mohou objevit na posledním místě, takže máme 12 různých čísel, které končí na 1, 12 čísel, které končí na 3 na 12 čísel, které končí na 5. Použijeme kombinatorické pravidlo součtu a získáme celkem 12 + 12 + 12 = 36 možností.

  5. Vypočítejte x, pokud víte, že V(2, x) = 72. Jinak řečeno: z množiny o velikosti x vybíráme dvojice a víme, že jsme schopni vybrat celkem 72 různých dvojic. Jak velká byla množina, ze které jsme dvojice vybírali? Rozepíšeme si to:

    $$ V(2, x) = \frac{x!}{(x-2)!} = 72 $$

    Dále upravíme:

    $$\begin{eqnarray} \frac{x!}{(x-2)!} &=& 72\\ \frac{x \cdot (x-1)\cdot(x-2)!}{(x-2)!} &=& 72 \\ x \cdot (x-1) &=&72\\ x^2-x&=&72\\ x^2-x-72&=&0 \end{eqnarray}$$

    Toto už je klasická kvadratická rovnice, takže ji vyřešíme pomocí diskriminantu nebo můžeme rovnici přepsat do tvaru

    $$ (x+8)\cdot(x-9)=0 $$

    z kterého už můžeme vyčíst řešení: x1 = −8 a x2 = 9. Záporné řešení nás nezajímá, protože množina nemůže mít zápornou velikost, takže řešením původní rovnice je x = 9, množina měla devět prvků.

Zdroje a další čtení