\input /home/pasky/school/fastex/lib.tex
\subchapter{Odhady faktoriálů a kombinačních čísel}{

\scpart{Faktoriály}{


\scpart{Věta}{

	$$ n^{n/2} \le{} n! \le{} \Big({n+1\over{}2}\Big)^n $$
	$$ n^{n/2} = \left(\sqrt{n}\right)^n $$

}


\proof{

	$$ (n!)^2 = \undernote{(1 \cdot n) (2\cdot(n-1)) \cdots (n\cdot1)}
				{\textbox{\it($n!$ jednou popředu a}\atop
				 \textbox{\it k~tomu podruhé odzadu)}} $$
	$$ (n!)^2 = z_{1} \cdot z_{2} \cdots z_{2n} $$

	Z \ref{AG nerovnost}i:
	$$ z \le{} \left({n+1\over{}2}\right)^2 $$

	A protože
	$$(i+1)(n-i) = n+i(n-1-i) \ge{} n$$
	(pro $i=0,1,\cdots,n-1 \Rightarrow{} (i\ge{}0 \land{} (n-1-i)\ge{}0)$),
	platí:
	$$ z \ge{} n $$
	
	Tedy:
	$$ (n^n) \le{} (n!)^2 \le{} \left(\left({n+1\over{}2}\right)^2\right)^n $$
	$$ n^{n\slash{}2} \le{} n! \le{} \left({n+1\over{}2}\right)^n $$
	\qed

}
%% \ee -> Euler (\e je member)



\scpart{Přesněji}{
	$$ n! \approx{} \left({n\over{}e}\right)^n\cdot\sqrt{2\pi\*n} $$
	$$ \textbox{tj.} \lim_{n\to{}\infty} {n!\over{}\left({n\over{}\ee}\right)^n\cdot\sqrt{2\pi\*n}} = 1 $$

	Bez důkazu.
}

}


\scpart{Kombinační čísla}{

Můžeme přeformulovat jako odhad prostředního čísla v $n$-tém řádku Pascalova trojúhelníku.



\scpart{Víme}{

	$$ \cn{n}{0} + \cn{n}{1} +\cdots+ \cn{n}{n} = 2^n $$

	Protože součet je počet podmnožin $n$-prvkové množiny.
	
	\shortdef{Alternativní výklad}{Každá čísla v předcházejícím řádku přispějí $2\times$ do dalšího řádku.}

}


Zřejmě z první definice kombinačního čísla:
	
$$ \cn{n}{0} < \cn{n}{1} < \cdots < \cn{n}{\floor{n\over{}2}} =
   \cn{n}{\ceil{n\over{}2}} > \cdots > \cn{n}{n} $$

$$ {2^n\over{}n+1} < \cn{n}{\floor{n\over{}2}} < 2^n $$

Přesněji:

$$ \cn{n}{\floor{n\over{}2}} \approx{} {2^n\over{}\sqrt{\pi\*n/2}} $$

Platí také:

$$ \cn{n}{0} + \cn{n}{1} + \cdots + \cn{n}{k} \le{} \Big({\ee \cdot n\over{}k}\Big)^k $$

Bez důkazu. (Ve skriptech, nepovinný.)

}

}

\bend