— — Odhady faktoriálů a kombinačních čísel

Odhady faktoriálů a kombinačních čísel

Faktoriály

Věta

n^{n/2} ≤ n! ≤ (\frac{n + 1}{2} )^{n}

n^{n/2} = (\sqrt{n})^{n}

DŮKAZ:

(n!)^{2} = \underbrace{(1 · n)(2 · (n − 1)) ⋯ (n · 1)}_{(n! jednou popředu a k tomu podruhé odzadu)}
(n!)^{2} = z_{1} · z_{2} ⋯ z_{2n}

Z AG nerovnosti:

z ≤ (\frac{n + 1}{2} )^{2}

A protože

(i + 1)(n − i) = n + i(n − 1 − i) ≥ n

(pro i = 0, 1, ⋯, n − 1 ⇒ (i ≥ 0 ∧ (n − 1 − i) ≥ 0)), platí:

z ≥ n

Tedy:

(n^{n}) ≤ (n!)^{2} ≤ ((\frac{n + 1}{2} )^{2})^{n}

n^{n/2} ≤ n! ≤ (\frac{n + 1}{2} )^{n}

Q.E.D.

Přesněji

n! ≈ (\frac{n}{e})^{n} · \sqrt{2πn}

tj. lim_{n→∞} \frac{n!}{(\frac{n}{e})^{n} · \sqrt{2πn}} = 1

Bez důkazu.

Kombinační čísla

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

Víme

\binom{n}{0} + \binom{n}{1} + ⋯ + \binom{n}{n} = 2^{n}

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

/L:1 1 — — Odhady faktoriálů a kombinačních čísel

Zřejmě z první definice kombinačního čísla:

\binom{n}{0} < \binom{n}{1} < ⋯ < \binom{n}{⌊\frac{n}{2}⌋} = \binom{n}{⌈\frac{n}{2}⌉} > ⋯ > \binom{n}{n}

\frac{2^{n}}{n + 1} < \binom{n}{⌊\frac{n}{2}⌋} < 2^{n}

Přesněji:

\binom{n}{⌊\frac{n}{2}⌋} ≈ \frac{2^{n}}{\sqrt{πn/2}}

Platí také:

\binom{n}{0} + \binom{n}{1} + ⋯ + \binom{n}{k} ≤ (\frac{e · n}{k})^{k}

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