Variace a permutace s opakováním

Doplněný obsah — není z archivu podkladů, napsáno podle ŠVP. Vhodné ověřit u vyučujícího.

Pozn. k obsahu: Zdrojová prezentace se při převodu ukázala jako prázdná (obsah byl výhradně v animacích/obrázcích, které konverze nezachytila vůbec). Celý obsah tohoto tématu je proto nově napsaný — teorie navazuje na Variace a permutace bez opakování, tentokrát pro případ, kdy se prvky smí opakovat.

Variace s opakováním

$k$ -členná variace s opakováním z $n$ prvků je uspořádaná $k$ -tice sestavená z těchto prvků tak, že se libovolný prvek může vyskytnout i vícekrát (klidně i všech $k$ pozic stejným prvkem).

Na rozdíl od variace bez opakování máme na každé z $k$ pozic k dispozici všech $n$ prvků (nic se „nespotřebovává”):

$V ’(k, n) = n k$

Příklad

Kolik různých čtyřmístných PIN kódů lze sestavit z číslic 0 až 9 (číslice se mohou opakovat, např. 0000 nebo 1111 jsou platné kódy)?

Máme $n = 10$ číslic, sestavujeme $k = 4$ -místné uspořádané kódy s opakováním:

$V ’(4, 10) = 104 = 10, 000$

Příklad 2

Kolika způsoby lze obarvit 3 pole v řadě, pokud máme k dispozici 5 barev a každé pole může mít libovolnou barvu (i stejnou jako sousední pole)?

$V ’(3, 5) = 53 = 125$

(Pro srovnání: bez opakování by to bylo jen $V (3, 5) = 5 \cdot 4 \cdot 3 = 60$ , viz předchozí téma — s opakováním možností přibývá, protože žádná barva se „nespotřebuje”.)

Permutace s opakováním

Pokud chceme uspořádat $n$ prvků, mezi kterými jsou skupiny navzájem stejných prvků (např. písmena ve slově, kde se některá písmena opakují), počet různých uspořádání je menší než $n!$ , protože záměna dvou stejných prvků nedává nové pořadí.

Máme-li $n$ prvků rozdělených do skupin o $n 1 , n 2 , \dots, n m $ stejných prvcích (přičemž $n 1 + n 2 + \dots + n m = n$ ), počet permutací s opakováním je:

$P ’(n 1 , n 2 , \dots, n m ) = n 1 ! \cdot n 2 ! \dots n m ! n! $

Příklad

Kolik různých „slov” (přesmyček, i bez smyslu) lze vytvořit přeskládáním písmen slova MAMA?

Slovo má 4 písmena, z toho 2× M a 2× A (dvě skupiny po 2 stejných písmenech), $n = 4$ , $n 1 = 2$ (M), $n 2 = 2$ (A):

$P ’(2, 2) = 2! \cdot 2! 4! = 424 = 6$

Vypsáním si to můžeme ověřit: MAMA, MAAM, MMAA, AMMA, AMAM, AAMM — přesně 6 různých přesmyček.

Příklad 2

Kolik různých přesmyček má slovo ANANAS?

Slovo má 6 písmen: 3× A, 2× N, 1× S ( $n = 6$ , $n 1 = 3$ , $n 2 = 2$ , $n 3 = 1$ ):

$P ’(3, 2, 1) = 3! \cdot 2! \cdot 1! 6! = 6 \cdot 2 \cdot 1 720 = 12720 = 60$

Shrnutí

Variace s opakováním z $n$ prvků, $k$ -členná: $V ’(k, n) = n k$ — na každé pozici je k dispozici všech $n$ prvků.
Permutace s opakováním $n$ prvků rozdělených do skupin stejných prvků: $P ’(n 1 , \dots, n m ) = n 1 ! \dots n m ! n! $ .

Zdroje

CALDA, Emil, DUPAČ, Václav. Matematika pro gymnázia. Kombinatorika, pravděpodobnost, statistika. Praha: Prometheus, 2006.