Variace, permutace a kombinace s opakováním

Permutace s opakováním

Definice

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

Vztah mezi \(k\) a \(n\) je následující:

Přirozené číslo \(n\) udává počet různých prvků.
Jednotlivé prvky se mohou opakovat: je zvykem označovat počet opakování prvního prvku \(k_1\), počet opakování druhého prvku \(k_2\), a tak dál, až počet opakování posledního, tj. \(n\)-tého prvku, je zvykem označovat \(k_n\).

Přirozené číslo \(k\) označuje počet všech prvků, jejichž různá pořadí zkoumáme, proto platí \(k = k_1 + k_2 + \ldots + k_n\).

Jestliže máme např. \(30\) bílých kostek, \(40\) modrých kostek a \(50\) černých kostek a chceme je srovnat do řady, jedná se o permutace s opakováním ze tří prvků, kde první prvek se opakuje třicetkrát, druhý čtyřicetkrát a třetí padesátkrát:

\(n=3\) (bílá, modrá, černá kostka);

\(k_1 = 30\), \(k_2 = 40\), \(k_3 = 50\);

\(k = k_1 + k_2 + k_3 = 30 + 40 + 50 = 120\).

Příklad

Zkusme určit počet všech pořadí pěti prvků, v nichž se jeden prvek opakuje třikrát a další dva jsou různé \(n=3\), \(k_1 = 3\), \(k_2 = 1\), \(k_3 = 1\), \(k=5\)); označme je např. \(a, a, a, b, c\).
Protože umíme určit počet pořadí pěti různých prvků, přeznačíme nejprve tři stejné prvky na \(a_1, a_2, a_3\). Jak už víme, počet pořadí pěti různých prvků (bez opakování) je \(P(5) = 5! = 120\). Když smažeme indexy u prvků \(a_1, a_2, a_3\), počet pořadí bude menší než \(120\), protože některá pořadí budou stejná:

\((a_1, b, a_2, a_3, c)\) \((a_1, b, a_3, a_2, c)\) \((a_2, b, a_1, a_3, c)\) \((a_2, b, a_3, a_1, c)\) \((a_3, b, a_1, a_2, c)\) \((a_3, b, a_2, a_1, c)\)	\((c, a_1, b, a_2, a_3)\) \((c, a_1, b, a_3, a_2)\) \((c, a_2, b, a_1, a_3)\) \((c, a_2, b, a_3, a_1)\) \((c, a_3, b, a_1, a_2)\) \((c, a_3, b, a_2, a_1)\)	\((a_1, a_2, b, c, a_3)\) \((a_1, a_3, b, c, a_2)\) \((a_2, a_1, b, c, a_3)\) \((a_2, a_3, b, c, a_1)\) \((a_3, a_1, b, c, a_2)\) \((a_3, a_2, b, c, a_1)\)	\(\ldots\)
\((a, b, a, a, c)\)	\((c, a, b, a, a)\)	\((a, a, b, c, a)\)	…

Jak naznačuje tabulka, každé pořadí prvků \(a, a, a, b, c\) odpovídá šesti pořadím prvků \(a_1, a_2, a_3, b, c\), kde prvky \(b, c\) stojí na stejných místech a prvky \(a_1, a_2, a_3\) se prostřídají všemi způsoby. Prvky \(a_1, a_2, a_3\) lze na tři volná místa doplnit \(P(3) = 3! = 6\) způsoby, proto je počet pořadí prvků \(a, a, a, b, c\) šestkrát menší než počet pořadí prvků \(a_1, a_2, a_3, b, c\).
Počet pořadí prvků \(a, a, a, b, c\) je tedy \(120 / 3! = 120 / 6 = \boldsymbol{20}\).
Pro kontrolu je ještě vyjmenujeme:

\((\color{blue}{a},\color{blue}{a},\color{blue}{a},\color{green}{b},\color{red}{c}), (\color{blue}{a},\color{blue}{a},\color{blue}{a},\color{red}{c},\color{green}{b})\),
\((\color{blue}{a},\color{blue}{a},\color{green}{b},\color{blue}{a},\color{red}{c}), (\color{blue}{a},\color{blue}{a},\color{red}{c},\color{blue}{a},\color{green}{b})\),
\((\color{blue}{a},\color{blue}{a},\color{green}{b},\color{red}{c},\color{blue}{a}), (\color{blue}{a},\color{blue}{a},\color{red}{c},\color{green}{b},\color{blue}{a})\),
\((\color{blue}{a},\color{green}{b},\color{blue}{a},\color{blue}{a},\color{red}{c}), (\color{blue}{a},\color{red}{c},\color{blue}{a},\color{blue}{a},\color{green}{b})\),
\((\color{blue}{a},\color{green}{b},\color{blue}{a},\color{red}{c},\color{blue}{a}), (\color{blue}{a},\color{red}{c},\color{blue}{a},\color{green}{b},\color{blue}{a})\),
\((\color{blue}{a},\color{green}{b},\color{red}{c},\color{blue}{a},\color{blue}{a}), (\color{blue}{a},\color{red}{c},\color{green}{b},\color{blue}{a},\color{blue}{a})\),
\((\color{green}{b},\color{blue}{a},\color{blue}{a},\color{blue}{a},\color{red}{c}), (\color{red}{c},\color{blue}{a},\color{blue}{a},\color{blue}{a},\color{green}{b})\),
\((\color{green}{b},\color{blue}{a},\color{blue}{a},\color{red}{c},\color{blue}{a}), (\color{red}{c},\color{blue}{a},\color{blue}{a},\color{green}{b},\color{blue}{a})\),
\((\color{green}{b},\color{blue}{a},\color{red}{c},\color{blue}{a},\color{blue}{a}), (\color{red}{c},\color{blue}{a},\color{green}{b},\color{blue}{a},\color{blue}{a})\),
\((\color{green}{b},\color{red}{c},\color{blue}{a},\color{blue}{a},\color{blue}{a}), (\color{red}{c},\color{green}{b},\color{blue}{a},\color{blue}{a},\color{blue}{a})\).

Příklad

Mějme \(4\) krabice s pastelkami: jednu krabici s \(k_1\) žlutými pastelkami, jednu krabici s \(k_2\) červenými pastelkami, jednu krabici s \(k_3\) zelenými pastelkami a jednu krabici s \(k_4\) modrými pastelkami; \(k_1, k_2, k_3, k_4\)jsou přirozená čísla. Určete, kolika způsoby je možné seřadit všechny tyto pastelky.

(Jde o permutace ze čtyř prvků s opakováním, kde se první prvek opakuje \(k_1\)-krát, druhý prvek \(k_2\)-krát, třetí prvek \(k_3\)-krát a čtvrtý prvek \(k_4\)-krát.)

Řešení

Podobně jako v minulém příkladu určíme, kolika způsoby by bylo možné pastelky seřadit, kdyby byly každé dvě navzájem různé. Celkem je pastelek \(k_1 + k_2 + k_3 + k_4\), počet jejich seřazení by proto byl \[P(k_1 + k_2 + k_3 + k_4) = (k_1 + k_2 + k_3 + k_4)!\] Protože pastelky nejsou všechny navzájem různé, budou se některá pořadí opakovat:
Každých \(k_1!\) pořadí je stejných, protože se v nich mění jen pořadí žlutých pastelek.
Každých \(k_2!\) pořadí je stejných, protože se v nich mění jen pořadí červených pastelek.
Každých \(k_3!\) pořadí je stejných, protože se v nich mění jen pořadí zelených pastelek.
Každých \(k_4!\) pořadí je stejných, protože se v nich mění jen pořadí modrých pastelek.
Výsledný počet pořadí všech pastelek je proto

\[P'(k_1, k_2, k_3, k_4) = \dfrac{(k_1 + k_2 + k_3 + k_4)!}{k_1! k_2! k_3! k_4!}\]

Jestliže tento postup ještě zobecníme a místo čtyř krabic s pastelkami jich budeme uvažovat \(n\), dostaneme následující vzorec:

Počet \(P'(k_1, k_2, \ldots, k_n)\) permutací z \(n\) prvků, v nichž se jednotlivé prvky opakují \(k_1, k_2, \ldots, k_n\)-krát, je \[P'(k_1, k_2, \ldots, k_n) = \dfrac{(k_1 + k_2 + \ldots + k_n)!}{k_1! k_2! \ldots k_n!}.\]