Kombinatorika

Problém šatniarky.
Pri vstupe do klubu si každý z piatich pánov odloží klobúk do šatne. Pri odchode šatniarka vydá náhodne každému pánovi jeden klobúk bez toho, že by skontrolovala, či je to správny klobúk. Aké sú šance, že žiaden z pánov nedostane vlastný klobúk?

1. Ide o permutácie klobúkov. Šatniarka priraďuje klobúky pánom. Jedno priradenie klobúkov pánom je permutácia.
2.  Keď permutácia má pevný bod, tak to znamená, že niektorý klobúk bol daný správne svojmu pánovi.
3. Pravdepodobnosť bude predstavovať podiel počtu permutácií bez pevného bodu k počtu všetkých permutácií.
4. Derangement (deranžmán) permutácia bez pevných bodov, v ktorej nikto nedostane svoj pôvodný prvok.
5. Čitateľ bude rovný počtu všetkých permutácií bez pevného bodu (počet všetkých deranžmánov).
6. Na permutácie s aspoň jedným pevným bodom sa uplatňuje princíp inklúzie a exklúzie.

1. Riešenie pomocou princípu zapojenia a vypojenia
Aplikovaním princípu zapojenia a vypojenia dostaneme:

1. $\small  N(0)=\normalsize{5!- \binom {5} {1}(5-1)! + \binom {5} {2} (5-2)!- \binom {5} {3}(5-3)! + \binom {5} {4}(5-4)!-\binom {5} {5}(5-5)!}$
2. $\small  N(0)=\normalsize{5!\left(1- \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}+ \frac{1}{4!} - \frac{1}{5!}\right)=44}$
3. Teda pravdepodobnosť je $\frac{44}{5!} = \frac{44}{120} = \frac{11}{30}$.

2. Riešenie pomocou cyklového rozkladu permutácie
Bez pevného bodu znamená, že v cyklovom rozklade permutácie sa nesmie vyskytnúť 1-cyklus. Pri piatich prvkoch teda prichádzajú do úvahy iba dva typy rozkladu:

1. jeden 5-cyklus,
2. jeden 2-cyklus a jeden 3-cyklus.

Spočítajme a) prípad:

• • Počet 5-cyklov na piatich prvkoch je $\small  (5-1)! = 4! = 24$. Pozrite si zdôvodnenie Tu.

Spočítajme b) prípad:

• • Pri rozklade na 2-cyklus a 3-cyklus najprv vyberieme dvojicu prvkov, ktoré vytvoria 2-cyklus: $\small  \binom 5 2 = 10$.
  • Zostávajúce tri prvky musia vytvoriť 3-cyklus. Počet 3-cyklov na troch prvkoch je $\small  (3-1)! = 2$.
  • Takýchto permutácií je teda $\small  \binom 5 2 \cdot 2 = 10 \cdot 2 = 20$.

Spolu dostaneme počet permutácií bez pevného bodu $\small  24 + 20 = 44$. Pravdepodobnosť je preto
$\frac{44}{5!} = \frac{44}{120} = \frac{11}{30}$.

Poznámka: Tento spôsob je výhodný tým, že sa nemusí používať princíp zapojenia a vypojenia; stačí vychádzať z cyklového rozkladu permutácie.

3. Riešenie pomocou rekurentného vzorca pre počet deranžmánov
Označme $\small  D_n$ počet permutácií $\small  n$ prvkov bez pevného bodu. Pre deranžmány platí rekurentný vzťah
$\small  D_n=(n-1)(D_{n-1}+D_{n-2}).$
Zdôvodnenie vychádza z princípu zapojenia a vypojenia. Vysvetlenie pre náš prípad:

1. Sledujme, kam sa dostane klobúk pána číslo 1. Nemôže zostať u pána 1, preto môže ísť k niektorému zo zvyšných $\small 4$ pánov.
2. Predpokladajme, že klobúk 1 dostane pán $\small k$.
3. Teraz nastanú dve možnosti:
   • buď klobúk pána $\small k$ dostane pán 1; potom sa dvojica $\small (1,k)$ uzavrela do 2-cyklu a zvyšné $\small 3$ klobúky sa musia rozdať bez pevného bodu, teda počtom $\small D_3$,
   • alebo klobúk pána $\small k$ nedostane pán 1; potom po vhodnom zlúčení situácie dostaneme počet možností $\small D_4$.
4. Preto $\small  D_5=4(D_4+D_3)$. Teraz už len dopočítame menšie hodnoty:

1. • $\small  D_1=0$ — jeden pán vždy dostane svoj klobúk.
   • $\small  D_2=1$ — jediná možnosť je výmena klobúkov.
   • $\small  D_3=2$.
   • $\small  D_4=3(D_3+D_2)=3(2+1)=9$.
   • $\small  D_5=4(D_4+D_3)=4(9+2)=44$.
2. Teda opäť dostávame pravdepodobnosť $\small  \frac{D_5}{5!}=\frac{44}{120}=\frac{11}{30}$.

4. Riešenie pomocou známeho vzorca pre deranžmány
Počet permutácií $\small n$ prvkov bez pevného bodu sa označuje $\small  !n$ a platí vzorec $\small  !n=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}\right).$ Pre $\small n=5$ dostaneme:

1. $\small  !5=5!\left(1-1+\frac12-\frac16+\frac1{24}-\frac1{120}\right)$
2. $\small  !5=120\left(0+\frac12-\frac16+\frac1{24}-\frac1{120}\right)=44$
3. Pravdepodobnosť teda je $\small  \frac{!5}{5!}=\frac{44}{120}=\frac{11}{30}$.

Tento postup je najkratší  ale študenti musia poznať pojem deranžmán a základné vzorce súvisiace s týmto pojmom.
A tie sú ekvivalentné princípu zapojenia a vypojenia.

Záver.
Nech už použijeme princíp zapojenia a vypojenia, cyklový rozklad permutácie, rekurentný vzťah pre deranžmány alebo priamo známy vzorec pre $!n$, vo všetkých prípadoch dostaneme ten istý výsledok: $\small  P(\text{nikto nedostane svoj klobúk})=\frac{11}{30}.$

Poznámky.

1. Permutácia je deranžmán práve vtedy, keď nemá žiadny cyklus dĺžky 1.
2. Počet deranžmánov z 𝑛 prvkov sa označuje: !𝑛
   $\small  !n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!}\right)$
3. „!𝑛 čítame ako deranžmán z n.“  alebo „Je to tzv. subfaktoriál.“