Permutace s opakováním

Uspořádáme všechny vagóny:
               $3 \cdot 2 \cdot 1 = 3!$

Tím, že osobní vagóny mezi sebou nerozlišujeme, nyní máme několik duplicitních uspořádání vagónů.

Všechna uspořádání jsou (N-nákladní, O₁, O₂-osobní vagóny – sice je nerozlišujeme, ale pro vysvětlení počítání si je označíme):
               N O₁ O₂    O₁ N O₂    O₁ O₂ N
               N O₂ O₁    O₂ N O₁    O₂ O₁ N

Jak to vyřešíme?
Všimněte si, že sloupce tvoří pevně umístěný nákladní vagón a k němu různá umístění osobních vagónů. Počet různých umístění osobních vagónů je 2!. Proto pokud je nerozlišujeme, musíme výsledek vydělit počtem permutací osobních vagónů. $$\frac{3!}{2!} = 3$$

Celkem jsou $4$ vločky, počet jejich možných uspořádání je $4!$.

Jelikož bílé vločky mezi sebou nerozlišujeme, dělíme ještě počtem permutací třech bílých vloček a dostáváme výsledek:

$$ \frac{4!}{3!} = 4 $$

Proč dělíme počtem permutací třech vloček?

Pokud si vypíšeme všechna uspořádání vloček s rozlišením bílých vloček, dostáváme:
(B₁, B₂, B₃ - bílé vločky, M - modré vločky)
               M B₁ B₂ B₃    B₁ M B₂ B₃    B₁ B₂ M B₃    B₁ B₂ B₃ M
               M B₁ B₃ B₂    B₁ M B₃ B₂    B₁ B₃ M B₂    B₁ B₃ B₂ M
               M B₂ B₁ B₃    B₂ M B₁ B₃    B₂ B₁ M B₃    B₂ B₁ B₃ M
               M B₂ B₃ B₁    B₂ M B₃ B₁    B₂ B₃ M B₁    B₂ B₃ B₁ M
               M B₃ B₁ B₂    B₃ M B₁ B₂    B₃ B₁ M B₂    B₃ B₁ B₂ M
               M B₃ B₂ B₁    B₃ M B₂ B₁    B₃ B₂ M B₁    B₃ B₂ B₁ M

V tabulce můžeme vidět, že sloupce tvoří právě ty čtveřice, které obsahují stejné postavení modré vločky vůči bílým. Tedy v rámci sloupce je umístění modré pevně dáno a bílé jsou propermutovány mezi sebou. Pokud tedy bílé vločky mezi sebou nerozlišujeme, musíme vydělit počtem řádků a těch je právě 3!.

Jestliže číslice 6 má být obsažena třikrát, číslice 4 bude obsažena dvakrát.

Rozmísťujeme $2 + 3 $ ($= 5$) číslic: $ 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5! $.

Číslice 6 mezi sebou nerozlišujeme, taktéž i číslice 4, proto ještě vydělíme počtem permutací jednotlivých číslic:

$$ \frac{5!}{2! \cdot 3!} = 10 $$

A) Jde o permutace s opakováním z pěti písmen A, B, D, K, R, v nichž je A pětkrát, B dvakrát, D jednou, K jednou a R dvakrát. Počet všech permutací tedy je: $ \dfrac{11!}{5! \cdot 2! \cdot 2! \cdot 1! \cdot 1!} = \dfrac{11!}{480} $

B) Nemají-li být dvě písmena A vedle sebe, musí být každé z pěti písmen A na jednom ze sedmi míst vyznačených podtržítkem:
_ B _ R _ K _ D _ B _ R _
Pět z těchto míst lze vybrat $\dbinom{7}{5}$ způsoby a zbývající písmena lze přemístit $ \dfrac{6!}{2! \cdot 2!}$
Počet všech "slov", v nichž žádná dvě písmena A spolu nesousedí, je $$\dbinom{7}{5} \cdot \dfrac{6!}{2! \cdot 2!} = 3780 $$

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.)

Řešení:

$$ P(1,2) = \frac{(1 + 2)!}{1! \cdot 2!} = 3$$

Určete počet způsobů, jimiž lze přemístit písmena slova ABRAKADABRA.

Řešení:

$$ P(1,1,2,2,5) = \frac{(1 + 1 + 2 + 2 + 5)!}{1! \cdot 1! \cdot 2! \cdot 2! \cdot 5!} = \frac{11!}{2 \cdot 2 \cdot 5!} = 83160$$

a) $$ \frac{(1 + 1 + 2 + 2 + 2 + 8)!}{2! \cdot 2! \cdot 2! \cdot 8!} = \frac{16!}{2 \cdot 2 \cdot 2 \cdot 8!} = 64864800 \qquad =[P'(1, 1, 2, 2, 2, 8)] $$

b) $$ {8 \choose 2} \cdot \frac{16!}{2! \cdot 2! \cdot 2! \cdot 8!} = 1816214400 $$

Celkem je ve slově $13$ písmen. Počet jednotlivých písmen je:
A - 2, B - 1, I - 2, K - 2, M - 1, N - 1, O - 2, R - 1, T - 1.

Jelikož jednotlivá písmena mezi sebou nerozlišujeme, dostáváme výsledek:

$$ \frac{13!}{2! \cdot 2! \cdot 2! \cdot 2!} = 389188800 \qquad =[P'(1, 1, 1, 1, 1, 2, 2, 2, 2)] $$

a) $$ \frac{5!}{3! \cdot 2!} = 10 \qquad =[P'(2, 3)] $$

b) $$ \frac{5!}{3! \cdot 2!} + \frac{5!}{2! \cdot 3!} + \frac{5!}{1! \cdot 4!} + \frac{5!}{0! \cdot 5!} = 10 + 10 + 5 + 1 = 26 \qquad = [P'(3, 2) + P'(2, 3) + P'(1, 4) + P'(0, 5)] $$

c) $$ \frac{5!}{3! \cdot 2!} + \frac{5!}{4! \cdot 1!} + \frac{5!}{5! \cdot 0!} = 10 + 5 + 1 = 16 \qquad = [P'(3, 2) + P'(4, 1) + P'(5, 0)] $$

Ciferný součet uvažovaných čísel je nejvýše $ 4 \cdot 7 = 28$. Podmínka dělitelnosti čísla devíti je ekvivalentní tomu, že ciferný součet je dělitelný devíti. Do úvahy tak připadají pouze ciferné součty 27, 18, 9.
Ciferný součet 27 z uvažovaných číslic dostat nelze.
Ciferný součet 18 lze dostat pouze použitím číslic 7, 7, 2, 2 anebo 7, 5, 5, 1.
Ciferný součet 9 utvoří pouze číslice 7, 2, 0, 0 nebo 7, 1, 1, 0 nebo 5, 2, 2, 0 nebo 5, 2, 1, 1.

Počet čtyřciferných čísel odpovídajících jednotlivým skupinám cifer:

$$ 7, 7, 2, 2 \quad \ldots \quad \frac{4!}{2! \cdot 2!} = 6 \phantom{\frac{1}{2!}}$$ $$ 7, 5, 5, 1 \quad \ldots \quad \frac{4!}{2!} = 12 \phantom{-\frac{3!}{2!}}$$ $$ 7, 2, 0, 0 \quad \ldots \quad \frac{4!}{2!} - 3! = 6 \phantom{1}$$ $$ 7, 1, 1, 0 \quad \ldots \quad \frac{4!}{2!} - \frac{3!}{2!} = 9 $$ $$ 5, 2, 2, 0 \quad \ldots \quad \frac{4!}{2!} - \frac{3!}{2!} = 9 $$ $$ 5, 2, 1, 1 \quad \ldots \quad \frac{4!}{2!} = 12 \phantom{-\frac{3!}{2!}}$$

V některých případech jsme odečítali situace, kdy na první cifře je číslice 0.

Podle pravidla součtu je počet všech čtyřciferných čísel odpovídajících zadání roven: $$6+12+6+9+9+12=54.$$

Požadovaný výsledek získáme, pokud od počtu všech anagramů odečteme ty, kde se vyskytují tři písmena O vedle sebe (tři O vedle sebe budeme počítat jako jeden prvek).

$$ \frac{6!}{3! \cdot 2! \cdot 1!} - \frac{4!}{2! \cdot 1! \cdot 1!} = 60 - 12 = 48$$

Každý vyhovující anagram začíná buď samohláskou, nebo souhláskou (místa pro další samohlásky, resp. souhlásky jsou pak jednoznačně určena). Na zadaných místech lze pak souhlásky umístit $4!$ způsoby, pro zápis samohlásek je pak $\dfrac{4!}{3!}$ možností.

Podle pravidla součinu je celkový počet anagramů $2 \cdot (4! \cdot \dfrac{4!}{3!}) = 192$.

$\dfrac{8!}{3! \cdot 3! \cdot 2!} = 560 \qquad = [P'(2, 3, 3)]$

$\dfrac{10!}{2! \cdot 4! \cdot 3!} = 12600 \qquad = [P'(1, 2, 3, 4)]$

Všech permutací je: $\dfrac{62!}{9! \cdot 7! \cdot 7! \cdot 5! \cdot 5! \cdot 5! \cdot 5! \cdot 4! \cdot 4! \cdot 2! \cdot 2! \cdot 2!} = \dfrac{62!}{9! \cdot (7!)^2 \cdot (5!)^4 \cdot (4!)^2 \cdot (2!)^3}. $
$ = [P'(2, 2, 2, 4, 4, 5, 5, 5, 5, 7, 7, 9)] $

Toto číslo je přibližně rovno číslu $3,573 \cdot 10^{60}$. Počítač by potřeboval více než $10^{54}$ sekund. O velikosti tohoto čísla si uděláme představu, když si uvědomíme, že trvání našeho vesmíru - tj. přibližně 15 miliard roků - je méně než $10^{17}$ sekund.

Veni, vidi, vici (Přišel jsem, viděl jsem, zvítězil jsem).

$\dfrac{12!}{3! \cdot 5!} = 665 280 \qquad = [P'(1, 1, 1, 1, 3, 5)]$

Aby ciferný součet byl roven třem, můžeme použít následující skupiny číslic:

I) jedna $3$ a devět $0$
$1$ možnost.

II) jedna $2$, jedna $1$ a osm $0$
Na první cifru můžeme zvolit jednu ze dvou možností ($1$ nebo $2$) a k oběma těmto možnostem existuje pro umístění další nenulové číslice 9 různých možností. Celkem: $2 \cdot 9 = 18$ možností.

III) tři $1$ a sedm $0$
První cifra je jednoznačně určená číslicí $1$, poté pro rozmístění zbylých dvou $1$ a sedmi $0$ je možností $\dfrac{9!}{2! \cdot 7!} = 36$.

Celkem podle pravidla součtu: $1+18+36=55$

Aby číslo bylo sudé, na poslední cifře nesmí být liché číslo, celkem takových čísel je: $1+(9+8)+ \dfrac{8!}{2! \cdot 6!} = 46$

$3 \cdot \dfrac{4!}{2! \cdot 2!} + 3 \cdot \dfrac{4!}{2!} = 54 \qquad = [3 \cdot P'(2, 2) + 3 \cdot P'(1, 1, 2)] $

Bc. Monika Stančíková |
ÚMS, Přírodovědecká fakulta, Masarykova univerzita |
Návrat na úvodní stránku webu, přístupnost |

| Šablonu poskytlo:
| Servisní středisko pro e-learning na MU
| Fakulta informatiky Masarykovy univerzity, 2015

Nahoru