Odhady

Odhady z přednášky:

• $n^{n/2} \le n! \le n^n$ $\hskip 1.8cm$ $e\left(\frac{n}{e}\right)^n \le n! \le en \left(\frac{n}{e}\right)^n$
• $\left({n\over k}\right)^k \le {n \choose k} \le \left({en \over k}\right)^k$
• $\frac{2^{2m}}{2m+1} \le {2m \choose m} \le 2^{2m}$ $\hskip 1cm$ $\frac{2^{2m}}{2 \sqrt{m}} \le {2m \choose m} \le \frac{2^{2m}}{\sqrt{2m}}$

Zápisem $[n]$ označme množinu $\{0, 1, 2, 3, \dots , n-1\}$. V následujících otázkách předpokládejme, že $n$ je nějaké „dost velké“ číslo.

1. Pomocí těsnějších odhadů na $n!$ odhadněte $n! \over k!(n-k)!$.
2. Čeho je víc, všech funkcí z množiny $[n]$ do množiny $[3n]$, nebo všech prostých funkcí z množiny $[2n]$ do množiny [2n]?
3. Čeho je víc, všech grafů na množině vrcholů $[n]$, nebo všech grafů na množině vrcholů $[100n]$, jejichž každý vrchol má stupeň nejvýš $10$?
4. Rozhodněte, zda platí $n! \in 2^{\O(n)}$ a $n! \in 2^{\Omega(n)}$.
5. Seřaďte podle velikosti: $2^{2n}, e^{\left(\ln n\right)^3}, {2n \choose n}, n^{\ln n}, \left(\sqrt n\right)^n$.

Vytvořující funkce

Vytvořující funkce pro posloupnost $(a_0, a_1, a_2, \dots)$ je mocninná řada $a(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots$. Je obecně známo, že $1 \over 1-x$ je vytvořující funkce pro $1,1,1\dots$.

Funkce pomocí jiné

Předpokládejme, že posloupnost $a_0, a_1, a_2, \dots$ má vytvořující funkci $f(x)$. Jakou vytvořující funkci budou pak mít následující posloupnosti?

1. $a_0 + 1, a_1 + 1, a_2 + 1, \dots , a_n + 1, \dots$
2. $2a_0 , 2a_1 , 2a_2 , \dots , 2a_n , \dots$
3. $0, a_0 , a_1 , a_2 , \dots , a_{n-1} , \dots$
4. $a_1 , a_2 , a_3 , \dots$
5. $a_0 , -a_1 , a_2 , -a_3 , \dots , (-1)^n a_n , \dots$
6. $a_0 , 0, a_2 , 0, a_4 , 0, a_6 , 0, \dots$
7. $a_0 , 0, a_1 , 0, a_2 , 0, a_3 , 0, \dots$
8. $a_0 , a_0 + a_1 , a_0 + a_1 + a_2 , a_0 + a_1 + a_2 + a_3 , \dots$

Posloupnost pomocí jiné

A které posloupnosti mají následující vytvořující funkce?

1. $f(-x)$
2. $f'(x)$
3. $f(2x)$