a pravděpodobnost
KOMBINATORIKA
L23: Permutace s opakováním
<< Předchozí lekce | Seznam lekcí | Další lekce >>
V jedné z předchozích lekcí jsme se již seznámili s permutací bez opakování, což je uspořádaná n-tice z n prvků, která je sestavena tak, že každý se v ní vyskytuje právě jednou. V případě permutací s opakováním budeme tentokrát sestavovat k-tice z n prvků tak, že počet výskytů každého z těchto prvků bude předem daný.
Určete počet všech pětic sestavených z písmen A, B takových, že písmeno A se zde vyskytuje třikrát a písmeno B dvakrát. Všechny tyto skupiny vypište.
Vytváříme pětice z písmen A a B tak, že A se zde bude vyskytovat třikrát, B dvakrát.
Nejprve si dané pětice zkusíme vypsat: AAABB, AABAB, ABAAB, ABABA, ABBAA, AABBA, BAAAB, BAABA, BABAA, BBAAA
Jedná se tedy o 10 skupin.
Určete počet všech pětic sestavených z písmen A, B takových, že písmeno A se zde vyskytuje třikrát a písmeno B dvakrát (tj. skupin z příkladu L23.01) pomocí vzorce pro výpočet počtu permutací s opakováním.
Vzorec pro určení počtu permutací s opakováním: $${P`(k_{1}, k_{2}, \dots, k_{n}) = \frac{(k_{1} + k_{2} + ~ \dots ~ + k_{n})!}{k_{1}! \cdot k_{2}! \cdot ~ \dots ~ \cdot k_{n}!}}$$
Dosadíme ${k_1 = 3}$ a ${k_2 = 2}$: $${P`(3, 2) = \frac{(3 + 2)!}{3! \cdot 2!} = \frac{5!}{3! \cdot 2!} = 10}$$
Jedná se tedy o 10 skupin.
Kolik různých sedmiciferných čísel lze vytvořit z číslic 1, 2 a 3 tak, aby se číslice 1 vyskytovala třikrát a číslice 2 dvakrát?
Víme, že číslice 1 se vyskytuje třikrát a číslice 2 dvakrát. Protože je výsledné číslo sedmiciferné, musí se číslice 3 vyskytovat také dvakrát (${7 - (3 + 2) = 2}$).
$${P`(3, 2, 2) = \frac{(3 + 2 + 2)!}{3! \cdot 2! \cdot 2!} = \frac{7!}{3! \cdot 2! \cdot 2!} = 210}$$
Kolik různých slov lze sestavit ze slova INTERNET bez ohledu na jejich význam?
Nejprve je nutné zjistit, kolikrát se vyskytují v původním slově jednotlivá písmena: $${k_I = 1}$$ $${k_N = 2}$$ $${k_T = 2}$$ $${k_E = 2}$$ $${k_R = 1}$$
Získané hodnoty dosadíme do vzorce: $${P`(1, 2, 2, 2, 1) = \frac{(1 + 2 + 2 + 2 + 1)!}{1! \cdot 2! \cdot 2! \cdot 2! \cdot 1!} = \frac{8!}{1 \cdot 2 \cdot 2 \cdot 2 \cdot 1} = \frac{8!}{8} = 7! = 5~040}$$
Ze slova INTERNET lze přeskupením písmen sestavit 5 040 slov.
Na nemocničním oddělení pracují lékaři na 3 směny (ranní, odpolední a noční směna). Na ranní směnu je potřeba 5 lékařů, na odpolední 3 a na noční 2. Kolika způsoby je možné rozdělit 10 lékařů na jednotlivé směny?
K jednotlivým lékařům přiřazujeme jednu ze 3 směn. Tvoříme tedy desetičlennou skupinu, kde ranní směna bude pětkrát, odpolední směna třikrát a noční směna dvakrát.
$${P`(5, 3, 2) = \frac{(5 + 3 + 2)!}{5! \cdot 3! \cdot 2!} = \frac{10!}{5! \cdot 3! \cdot 2!} = 2~520}$$
Ve skupině prvků se jediný z nich vyskytuje vícekrát a to třikrát. Kolik prvků skupina má, jestliže po odstranění jednoho z opakujících se prvků klesne počet permutací čtyřikrát?
Vzorec pro výpočet počtu permutací s opakováním: $${P`(k_{1}, k_{2}, \dots, k_{n}) = \frac{(k_{1} + k_{2} + ~ \dots ~ + k_{n})!}{k_{1}! \cdot k_{2}! \cdot ~ \dots ~ \cdot k_{n}!}}$$
(1) Původní skupina:
Ze zadání víme, že: $${k_1 = k_2 = \dots = k_{n-1} = 1}$$ $${k_{n} = 3}$$
Dosadíme: $${P`_1(1, 1, \dots , 1, 3) = \frac{(1 + 1 + \dots + 1 + 3)!}{1! \cdot 1! \cdot \dots \cdot 1! \cdot 3!} = \frac{\left[(n - 1) \cdot 1 + 3\right]!}{(n - 1) \cdot 1!\cdot 3!} = \frac{(n - 1 + 3)!}{(n - 1) \cdot 3!} = \frac{(n + 2)!}{(n - 1) \cdot 3!} }$$
(2) Nová skupina:
Ze zadání víme, že: $${k_1 = k_2 = \dots = k_{n-1} = 1}$$ $${k_{n} = 2}$$
Dosadíme: $${P`_2(1, 1, \dots , 1, 2) = \frac{(1 + 1 + \dots + 1 + 2)!}{1! \cdot 1! \cdot \dots \cdot 1! \cdot 2!} = \frac{\left[(n - 1) \cdot 1 + 2\right]!}{(n - 1) \cdot 1!\cdot 2!} = \frac{(n - 1 + 2)!}{(n - 1) \cdot 2!} = \frac{(n + 1)!}{(n - 1) \cdot 2!} }$$
3. Porovnání:
$${P`_1(1, 1, \dots , 1, 3) = 4 \cdot P`_2(1, 1, \dots , 1, 2)}$$ $${\frac{(n + 2)!}{(n - 1) \cdot 3!} = 4 \cdot \frac{(n + 1)!}{(n - 1) \cdot 2!}}$$ $${\frac{(n + 2) \cdot (n + 1)!}{(n - 1) \cdot 3 \cdot 2!} = 4 \cdot \frac{(n + 1)!}{(n - 1) \cdot 2!}}$$ $${\frac{(n + 2)}{3} = 4 \cdot \frac{1}{1}}$$ $${n + 2 = 12}$$ $${n = 10}$$Daná skupina má 10 různých prvků.
- Co je to "permutace s opakováním"?
- Pomocí jakého vzorce vypočítáme počet permutací s opakováním?
- Kolik nejvýše osmiciferných čísel lze sestavit z číslic 1, 2, 3, 4 tak, že číslice 1 se v daném čísle vyskytuje čtyřikrát, číslice 2 dvakrát, číslice 3 a 4 jedenkrát?
- k-členná permutace s opakováním z n prvků je uspořádaná k-tice sestavená z těchto prvků tak, že jednotlivé prvky mají daný počet opakování, tj. 1. prvek se vyskytuje ${k_1}$ krát, 2. prvek se vyskytuje ${k_2}$ krát, až n-tý prvek se vyskytuje ${k_n}$ krát.
- $${P`(k_{1}, k_{2}, \dots, k_{n}) = \frac{(k_{1} + k_{2} + ~ \dots ~ + k_{n})!}{k_{1}! \cdot k_{2}! \cdot ~ \dots ~ \cdot k_{n}!}}$$
- ${840}$