Odhady faktoriálu a kombinačních čísel

Odhad faktoriálu

$e{\left(\frac{n}{e}\right)}^n\le n!\le en{\left(\frac{n}{e}\right)}^n$ Pro důkaz odhadu užijeme indukce a odhad rozdělíme na dva případy:

1. $n!\le en{\left(\frac{n}{e}\right)}^n$
   • $n=1$:

$$1!\le e\cdot 1\cdot {\left(\frac{1}{e}\right)}^1=1$$

Z indukčního předpokladu platí odhad pro $n-1$ a musíme dokázat platnost odhadu u $n$:

$$\begin{array}{rl}n!=n(n-1)!& {\le }^{\text{IP}}en(n-1){\left(\frac{n-1}{e}\right)}^{n-1}\\ & =en{\left(\frac{n}{e}\right)}^n{\left(\frac{e}{n}\right)}^n(n-1){\left(\frac{n-1}{e}\right)}^{n-1}\\ & =en{\left(\frac{n}{e}\right)}^n{\left(\frac{n-1}{n}\right)}^{n}e\end{array}$$

výraz $\left( \frac{n-1}{n} \right)^n e$ je menší než jedna:

$${\left(\frac{n-1}{n}\right)}^{n}e={\left(1-\frac{1}{n}\right)}^{n}e\le {\left(e^{-1/n}\right)}^{n}e=e^{-1}e=1$$

a tedy máme $n! \leq en\left( \frac{n}{e} \right)^n \left( \frac{n-1}{n} \right)^n e \leq en\left( \frac{n}{e} \right)^n$.

2. $e{\left(\frac{n}{e}\right)}^n\le n!$ - n = 1:

$$e\cdot {\left(\frac{1}{e}\right)}^1=1\le 1!$$

- $n-1 \rightarrow n$:

$$\begin{array}{rl}en{\left(\frac{n-1}{e}\right)}^{n-1}& \le n(n-1)!\\ en{\left(\frac{n}{e}\right)}^n{\left(\frac{e}{n}\right)}^n{\left(\frac{n-1}{e}\right)}^{n-1}& =\\ e{\left(\frac{n}{e}\right)}^n{\left(\frac{n-1}{n}\right)}^{n-1}e& =\end{array}$$

	kde $\left( \frac{n-1}{n} \right)^{n-1} e \geq 1$:
	1. Nechť $m=n-1$. Potřebujeme:

$$(\frac{n-1}{n}{)}^{n-1}e\ge 1⟺(1+\frac{1}{m}{)}^m\le e.$$

	2. Binomická věta:

$$(1+\frac{1}{m}{)}^m=\sum _{k=0}^m(\genfrac{}{}{0ex}{}{m}{k})\frac{1}{m^k}\le \sum _{k=0}^m\frac{1}{k!}\le \sum _{k=0}^{\infty }\frac{1}{k!}=e.$$

\Bigl(1+\tfrac1m\Bigr)^m \le e ;\Longrightarrow; \Bigl(\tfrac m{m+1}\Bigr)^m e \ge1,

tedy pro $m=n-1$

\Bigl(\tfrac{n-1}{n}\Bigr)^{n-1}e \ge1.

## Odhad binomických koeficientů Důkaz odhadů

\Bigl(\frac{n}{k}\Bigr)^k ;\le;\binom nk;\le;\Bigl(\frac{e,n}{k}\Bigr)^k.

$$1.\ast \ast V\acute{y}choz\acute{ı}vzorec\ast \ast$$

\binom nk =\frac{n(n-1)\cdots(n-k+1)}{k!} =\prod_{j=1}^k\frac{,n-j+1,}{j}.

undefined

\frac{,n-j+1,}{j};\ge;\frac{n}{k},

undefined

\binom nk =\prod_{j=1}^k\frac{,n-j+1,}{j} ;\ge;\bigl(\frac{n}{k}\bigr)^k.

$$3.\ast \ast Horn\acute{ı}odhad\ast \ast Z\check{r}ejm\acute{e}jei$$

\frac{,n-j+1,}{j};\le;\frac{n}{j},

$$proto$$

\binom nk \le;\prod_{j=1}^k\frac{n}{j} =\frac{n^k}{k!} ;\le;\frac{n^k}{(k/e)^k} =\Bigl(\tfrac{e,n}{k}\Bigr)^k,

kde jsme použili odhad $k!\ge (k/e)^k$: 1. **Logaritmický přechod**

\ln(k!) ;=;\sum_{i=1}^k\ln i ;\ge;\int_{1}^{k}\ln x,dx ;=;\bigl[x\ln x - x\bigr]_{1}^{k} ;=;k\ln k - k + 1.

undefined

k\ln k - k + 1 ;\ge; k\ln k - k,

$$dostaneme$$

\ln(k!) ;\ge; k(\ln k - 1) ;=;k\ln!\bigl(\tfrac{k}{e}\bigr).

undefined