\input /home/pasky/school/fastex/lib.tex

\subchapter{Vánoční besídka (šatnářka)}{

$n$ dárců dostane nazpět $n$ dárků. Každá z $n!$ možností je stejně
pravděpodobná. Jaká je pravděpodobnost, že nikdo nedostane zpátky
svůj dárek?


\scpart{Matematická formulace}{

	Hledáme ${š(n)\over{}n!}$, $š(n) = $ počet permutací $\pi$ množiny $\{1,\ldots{},n\}$ bez pevného bodu.

\shortdef{Pevný bod}{
	$i$ je pevný bod, pokud $\pi(i)=i$.
}

}


\theorem{}{Šatnářka}{

	$$ š(n) = n!\left(1-{1\over{}1!}+{1\over{}2!}-{1\over{}3!}+\cdots{}+(-1)^n{1\over{}n!}\right) $$


\example{

	$$ š(1) = 1!\left(1-{1\over{}1!}\right) = 0 $$
	$$ š(2) = 2!\left(1-{1\over{}1!}+{1\over{}2!}\right) = 1 $$
	$$ š(3) = 3!\left(1-{1\over{}1!}+{1\over{}2!}-{1\over{}3!}\right) = 2 $$

}


\proof{

	$$ S_{n} = \textbox{množina všech permutací $\{1,\ldots{},n\}$} $$
	$$ A_{i} = \{ \pi \in{} S_{n}, i=1,\ldots,n:\ \pi(i)=i \} $$
	$$ |A_{i}| = (n-1)! \textnote{Prvek $i$ stojí, ostatní se propermutují.} $$

	Pro $I=\{i_{1}, \ldots{}, i_{k}\} \subseteq{} \{1, \ldots{}, n\}$ platí:

	$$ \undernote{
			\setcommon{i \in{} I}{}{A_{i}}
		}{
			A_{i_{1}} \cap{} \cdots{} \cap{} A_{i_{k}}
		} = \textbox{množina vsech permutací $\pi$} $$
	množiny $\{1, \ldots{}, n\}$ takových, že $\pi(i_{1})=i_{1},\ldots{},\pi(i_{k})=i_{k}$.

	$$ |\setcommon{i \in{} I}{}{A_{i}}| = (n-k)! \textnote{$k$ prvků stojí, ostatní se propermutují.} $$

	$$ š(n) = |S_{n}| - |\setjoin{i=1}{n} A_{i}| = $$
	$$      = n! - \sum_{k=1}^{n}{(-1)^{k-1} \cdot \sum_{I\in{}\cn{\{1,\ldots{},n\}}{k}}{\undernote{|\setcommon{i \in{} I}{}{A_{i}}|}{(n-k)!}} } $$
	$$      = n! - \sum_{k=1}^{n}{(-1)^{k-1} \cdot \undernote{\cn{n}{k}\*(n-k)!}{n!\over{}k!}} $$
	$$      = n! \cdot \left(1 - \sum_{k=1}^{n}{{(-1)^{k-1}\over{}k!}}\right) $$
	\qed


}


Tedy {\bf pravděpodobnost}, že nikdo nedostane zpět svůj dárek, je:

$$ {š(n)\over{}n!} = 1 - {1\over{}1!} + {1\over{}2!} - \cdots{} \pm {1\over{}n!} \to{} {1\over{}\ee} \approx{} 0.36787\ldots{} $$

}

}
\bend