PRUMYSL.CZ KONSTRUKTER.CZ 3D-TISK.CZ MATEMATIKA.CZ NOVAMEDIA.CZ

Variace s opakováním

Zobrazit kapitoly článku
  1. Kombinatorika
  2. Variace
  3. Permutace
  4. Kombinace
  5. Variace s opakováním
  6. Kombinace 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, 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 #

  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ž 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ů.

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

Zdroje a další čtení #

 

Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace