Permutace s opakováním

Při počítání s permutacemi bez opakování jsme počítali, kolik různých uspořádání můžeme utvořit ze všech předem daných prvků, kde se každý vyskytoval právě jednou.

I nyní nás bude zajímat počet všech různých uspořádání ze všech předem daných prvků s tím rozdílem, že se některé prvky se mohou opakovat.

Definice: Permutace s opakováním z n prvků je uspořádaná n-tice sestavená z těchto prvků tak, že se v ní každý vyskytuje aspoň jednou.

Počet P´(k_1, k_2, ..., k_n) všech permutací z n prvků je:

P´(k_1, k_2, …, k_n)=\frac{(k_1+k_2+...+k_n)!}{k_1! \cdot k_2! \cdot ... \cdot k_n!}


Příklad č. 1: Strojvedoucí chce za lokomotivu připojit 3 vagóny, 1 je nákladní a 2 jsou osobní. Kolik různých možností má strojvedoucí, jak vagóny zapojit? (Osobní vagóny mezi sebou nerozlišujeme.) [3]


Příklad č. 2: Určete počet způsobů, jimiž lze přemístit písmena slova ABRAKADABRA. [83160]


Příklad č. 3: Určete počet způsobů, jimiž lze umístit všechny bílé šachové figurky (král, dáma, 2 věže, 2 jezdci, 2 střelci, 8 pěšáků)

  • na dvě pevně zvolené řady šachovnice 8 x 8; [64864800]
  • na libovolné dvě řady šachovnice 8 x 8. [1362160800]

Příklad č. 4: Jistě jste poznali, že v anagramech AABIIKKMNOORT resp. MINIKABAROTOK je zašifrováno slovo KOMBINATORIKA. Určete počet všech anagramů, jež lze ze slova KOMBINATORIKA utvořit. [389188800]


Příklad č. 5: Určete počet všech pěticiferných přirozených čísel, jež lze sestavit z číslic 5 a 7, má-li v každém z nich být číslice 5.

  • právě třikrát; [10]
  • nejvýše třikrát; [26]
  • aspoň třikrát. [16]

Příklad č. 6: Určete počet všech čtyřciferných přirozených čísel dělitelných devíti, v jejichž dekadickém zápisu nejsou jiné číslice než 0, 1, 5, 7. [54]


Příklad č. 7: Určete počet všech anagramů, které lze získat z písmen slova ROKOKO, nesmějí-li v takovém anagramu stát všechna tři písmena O vedle sebe. [48]


Příklad č. 8: Určete počet všech anagramů, které lze vytvořit z písmen slova PARABOLA, požadujeme-li, aby se ve vytvořeném anagramu pravidelně střídaly samohlásky a souhlásky. [192]


Příklad č. 9: Pro osm studentů je připraveno v koleji ubytování ve 3 pokojích, z nichž 2 jsou třílůžkové, jeden dvoulůžkový. Kolik je způsobů rozdělení studentů do jednotlivých pokojů? [560]


Příklad č. 10: Rychlíková souprava bude tvořena ze dvou zavazadlových vozů, jednoho jídelního vozu, čtyřech vozů lůžkových a tří lehátkových. Kolik různých typů souprav lze sestavit? [12600]


Příklad č. 11: Když Christian Huygens objevil Saturnův prstenec, zašifroval svůj objev, jak bylo v té době časté, do následujícího anagramu:

aaaaaaa ccccc d eeeee g h iiiiiii llll mm nnnnnnnnn
oooo pp q rr s ttttt uuuuu

Náležitým uspořádáním písmen dostaneme zprávu Annulo cingitur tenui, plano, nusquam cohaerente, ad eclipticam inclinato. Česky: Obklopen prstencem tenkým, plochým, nikde nezavěšeným, nakloněným k ekliptice.

Určete, za jak dlouho by počítač, který by vypsal milión permutací Huygensova anagramu za sekundu, vypsal všechny permutace.

Výsledek: [číslo je rovno přibližně 3,573 \cdot 10^{60}, Počítač by potřeboval více jak 10^{54} sekund. Pro srovnání, vesmír je starý 15 miliard let, což je méně než 10^{17} sekund.]


Příklad č. 12: Poznáte zprávu Gaia Iulia Caesara zaslanou do Říma po vítězství nad pontským králem Farnakem, která se skrývá v anagramu CDEIIIIINVVV? Kolika způsoby lze v ní přemístit písmena? [665280]


Příklad č. 13: Určete počet všech deseticiferných přirozených čísel, jejichž ciferný součet je roven třem. Kolik z nich je sudých? [46]


Příklad č. 14: Určete, kolik čtyřciferných čísel lze sestavit z číslic čísla 238 832. [54]

Aktuality

Písemná práce

Test třídy ___

Termín:

Téma:

 

Písemná práce

Test třídy ___

Termín:

Téma:

 

Písemná práce

Test třídy ___

Termín:

Téma:

 

Písemná práce

Test třídy ___

Termín:

Téma:

 

Písemná práce

Test třídy ___

Termín:

Téma: