Variace s opakováním

Variace s opakováním se podobají klasickým variacím, pouze dovolujeme, aby se mohly prvky z nosné množiny M opakovat.

Definice a vzorec

Začneme klasickým příkladem: kolik různých slov dokážeme vytvořit z písmen anglické abecedy (abc … xyz, je jich 26), pokud má mít slovo délku 6? Šest písmen není moc, přesto těch slov bude poměrně hodně. Nezajímáme se o význam slov, takže i „weqrww“ bereme jako platné slovo délky šest.

K výpočtu potřebujeme znát pouze kombinatorické pravidlo součinu. Máme celkem 26 různých písmen, která můžeme použít. Na prvním místo tak můžeme dát jedno z 26 písmen. Na druhé místo ale také můžeme dát jedno z 26 písmen, protože jsme si nekladli podmínka, že se písmena nesmí opakovat. Tím se dostáváme k tomu, že na každé pozici vybíráme z 26 písmen a celkový počet variací tak je, dle pravidla součinu, 26⁶ = 308 915 776. To je poměrně dost na to, že jsme použili jen 26 písmen.

Řekneme, že k-členná variace s opakováním z množiny M o velikost n je každá uspořádaná k-tice, jejíž prvky jsou z množiny M a každý prvek se v k-tici může vyskytovat až k-krát. Máme-li tak množinu M = {1, 2, 3}, pak toto všechno jsou platné 4členné variace s opakováním: [1, 1, 1, 1], [1, 2, 3, 1], [2, 2, 3, 3]. Počet takových variací s opakováním, značíme V'(k, n) je pak roven

$$ V'(k, n) = n^k. $$

Řešené příklady

1. Kolik šesticiferných čísel lze sestavit z číslic {2, 4, 6, 8}, jestliže se číslice mohou opakovat? Zkrátka jen dosadíme do vzorce, množina má velikost 4 a vybíráme šestice:

   $$ V'(6, 4) = 4^6=4096. $$

2. V počítače se běžně používá binární číselná soustava, tj. soustava, která používá pouze číslice 0 a 1. Zavádí se tam nové jednotky, např. jeden bit představuje jakousi buňku, do které člověk uloží právě buď nulu nebo jedničku. Větší je bajt (anglicky byte), který obsahuje 8 bitů. Takže 1 je jeden bit, zatímco 01110001 je jeden bajt. Kolik existuje různých způsobů, jak zaplnit jeden bajt 8 bity?

   Vybíráme z množiny {0, 1}, tj. ze dvou prvků. Vybíráme k-tici o velikosti k = 8, takže počet všech možností je roven

   $$ V'(8, 2) = 2^8 = 256. $$

3. Z předchozího příkladu víme, že jeden bajt je schopen rozlišit až 256 různých hodnot. Kolik existuje způsobů, jak zaplnit 4 bajty?

   Čtyři bajty obsahují 4 · 8 = 32 bitů, stále vybíráme z množiny o velikost 2. Takže výsledek je:

   $$ V'(32, 2) = 2^{32} = 4{,}294,967{,}296. $$

   Vidíme, že pouhopouhé čtyři bajty dokáží rozlišit přes čtyři miliardy hodnot. Pro představu: dnešní počítače mají disky o velikosti stovek gigabajtů případně rovnou terabajtů. Jeden terabajt obsahuje 1 000 000 000 000 bajtů a tedy 8 000 000 000 000 bitů. Na terabajtový disk jsme tak schopni uložit až 2^{8 000 000 000 000} různých hodnot.

   Poznámka: v současné době panuje mírný zmatek v pojmu kilobajt (megabajt atd.). Z technologických důvodů platilo, že jeden kilobajt neobsahuje 1000 bajtů, jak bývá zvykem v ostatních jednotkách (jeden kilogram je roven jednomu tisíci gramů), ale jeden kilobajt byl roven 2¹⁰ bajtů, což je 1024 bajtů. Jeden megabajt pak byl 2²⁰ bajtů nebo též 2¹⁰ kilobajtů.

   V současné době tak rozlišujeme dva druhy zápisů: 1 kB (čteme kilobajt) je 1000 bajtů a 1 KiB (čteme kibibajt) je 2¹⁰ = 1024 bajtů.

4. Další příklad se nachází v samostatném článku zabývající se bezpečností hesla.

Zdroje a další čtení

• Kombinatorika na cuni.cz
• Bělohlávek, Vychodil: Diskrétní matematika [PDF]