\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
