Variace s opakováním
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 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, 266 = 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
-
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. $$
-
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. $$
-
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ž 28 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 210 bajtů, což je 1024 bajtů. Jeden megabajt pak byl 220 bajtů nebo též 210 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 210 = 1024 bajtů.
-
Další příklad se nachází v samostatném článku zabývající se bezpečností hesla.