Variace, permutace a kombinace s opakováním

Permutace s opakováním

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₁, počet opakování druhého prvku k₂, 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₁ + k₂ + … + 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₁ = 30, k₂ = 40, k₃ = 50;
k = k₁ + k₂ + k₃ = 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₁ = 3, k₂ = 1, k₃ = 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₁, a₂, a₃. 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₁, a₂, a₃, počet pořadí bude menší než 120, protože některá pořadí budou stejná:

Jak naznačuje tabulka, každé pořadí prvků a, a, a, b, c odpovídá šesti pořadím prvků a₁, a₂, a₃, b, c, kde prvky b, c stojí na stejných místech a prvky a₁, a₂, a₃ se prostřídají všemi způsoby. Prvky a₁, a₂, a₃ 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₁, a₂, a₃, b, c.
Počet pořadí prvků a, a, a, b, c je tedy 120/3! = 120/6 = 20.
Pro kontrolu je ještě vyjmenujeme:
(a, a, a, b, c), (a, a, a, c, b),
(a, a, b, a, c), (a, a, c, a, b),
(a, a, b, c, a), (a, a, c, b, a),
(a, b, a, a, c), (a, c, a, a, b),
(a, b, a, c, a), (a, c, a, b, a),
(a, b, c, a, a), (a, c, b, a, a),
(b, a, a, a, c), (c, a, a, a, b),
(b, a, a, c, a), (c, a, a, b, a),
(b, a, c, a, a), (c, a, b, a, a),
(b, c, a, a, a), (c, b, a, a, a).

Příklad

Mějme 4 krabice s pastelkami: jednu krabici s k₁ žlutými pastelkami, jednu krabici s k₂ červenými pastelkami, jednu krabici s k₃ zelenými pastelkami a jednu krabici s k₄ modrými pastelkami; k₁, k₂, k₃, k₄ 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₁-krát, druhý prvek k₂-krát, třetí prvek k₃-krát a čtvrtý prvek k₄-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₁ + k₂ + k₃ + k₄, počet jejich seřazení by proto byl P(k₁ + k₂ + k₃ + k₄) = (k₁ + k₂ + k₃ + k₄)!.
Protože pastelky nejsou všechny navzájem různé, budou se některá pořadí opakovat:
Každých k₁! pořadí je stejných, protože se v nich mění jen pořadí žlutých pastelek.
Každých k₂! pořadí je stejných, protože se v nich mění jen pořadí červených pastelek.
Každých k₃! pořadí je stejných, protože se v nich mění jen pořadí zelených pastelek.
Každých k₄! 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

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:

Příklad

Určete, kolika způsoby je možné srovnat do řady 2 šedé, 2 modré a 2 černé kostky.

Řešení

Několik úloh k permutacím s opakováním