Асимптотики

сумм из задачи 1.1.6 (1);

сумм из задачи 1.1.6 (2);

сумм из задачи 1.1.6 (3);

количества $A_n$ подмножеств множества $\left\{ 1, 2, \ldots , n\right\}$, не содержащих двух подряд идущих чисел;

то же, что в п. (4), для трёх подряд идущих чисел.

$\ex_{P_k}(n) \gtrsim \dfrac {k-2}{2} \cdot n$.

$\ex_{C_{2k+1}}(n) \gtrsim \dfrac {n^2}{4}$.

$\ex_{K_{1,k}}(n) \sim \dfrac {k-1}{2} \cdot n$.

$n^2\left(2+\dfrac {1}{n}\right)^n = (2+o(1))^n$. По определению это означает, что существует функция $\psi (n) = o(1)$, для которой

или, что то же самое,

$3^{\sqrt{n}}\left(2+\dfrac {1}{n}\right)^n = (2+o(1))^n$.

Найдите асимптотику для $\sqrt[n]{\dbinom {n}{[n/2]}}$ (ср. с задачами 1.4.3 (2) и 6.1.10 (2)).

$\dfrac {2^n}{n+1} < \dbinom {n}{[n/2]} < 2^n$.

Найдите асимптотику для $\sqrt[m]{\dbinom {3m}{m}}$.

$\dfrac {3^{3m}}{3m+1} < 2^{2m}\dbinom {3m}{m} < 3^{3m}$.

$\dbinom {n}{[an]} = (a^{-a}(1-a)^{a-1}+o(1))^n$, где $0 < a < 1$.

$\dfrac {n!}{[a_1n]!\ldots [a_sn]!} = (e^{-a_1\ln a_1 - \ldots - a_s\ln a_s}+o(1))^n$, где $a_1+\ldots +a_s=1$, $0 < a_k < 1$.

Найдите асимптотику для $\ln (n!)$.

Найдите асимптотику для $\sqrt[n]{n!}$.

$n^ne^{-n+1} \leqslant n! \leqslant n^{n+1}e^{-n+1}$;

$n! \leqslant n^ne^{-n+1}\sqrt{n}$.

Формула Стирлинга. $n! \sim n^ne^{-n}\sqrt{2\pi n}$, т.е. $\lim_{n \to \infty } \dfrac {n!}{n^ne^{-n}\sqrt{2\pi n}} = 1$.

$\dbinom {n}{k} < \dfrac {n^k}{k!}$.

$\ln \dfrac {(n-1)(n-2)\ldots (n-k)}{n^k} = -\dfrac {k(k+1)}{2n}\left(1+O\left(\dfrac {k}{n}\right)\right)$ для $k=k_n < \dfrac {n}{2}$.

Это означает, что существует функция $\psi (n) = O\left(\dfrac {k}{n}\right)$, для которой

или, что то же самое,

$\dbinom {n}{k} = \dfrac {n^k}{k!}e^{-\frac{k(k-1)}{2n}+O(k^3/n^2)}$ для $k=k_n < \dfrac {n}{2}$.

(Сформулируйте сами, что здесь означает $e^{-\frac{k(k-1)}{2n}+O(k^3/n^2)}$.)

$\dbinom {n}{k} \sim \dfrac {n^k}{k!}$ для $k=k_n=o(\sqrt{n})$.

$\dbinom {2n}{n-k}\Big/\dbinom {2n}{n} = e^{-\frac{k^2}{n}(1+o(1))}$ для $k=k_n=o(n)$.

(Сформулируйте сами, что здесь означает $e^{-\frac{k^2}{n}(1+o(1))}$.)

Верно ли, что записи $e^{o(n)}$ и $o(e^n)$ <<равнозначны>>?

То есть верно ли, что для любой функции $f : \mathbb {Z} \to (0,+\infty )$ условия $\lim_{n\to \infty }\dfrac {\ln f(n)}{n}=0$ и $\lim_{n\to \infty }f(n)e^{-n}=0$ равносильны?

Подберите функции $f,g : \mathbb {Z} \to (0,+\infty )$ такие, что $f(n)\sim g(n)$, но $e^{f(n)} \neq O(e^{g(n)})$.

Могут ли функции $f,g : \mathbb {Z} \to (0,+\infty )$ одновременно удовлетворять соотношениям $f(n)=o(g(n))$ и $g(n)=o(f(n))$?

Могут ли функции $f,g : \mathbb {Z} \to (0,+\infty )$ одновременно удовлетворять соотношениям $f(n)=O(g(n))$ и $g(n)=O(f(n))$?

Следует ли из двух соотношений из п. (4), что $f(n)\sim g(n)$?

Какая функция растёт быстрее: $x^{(x^x)}$ или $(x!)^{(2^x)}$?

То есть найдите $\lim_{x\to \infty } x^{(x^x)}(x!)^{(-2^x)}$.

Существует ли функция $\psi (n) = o(1)$, для которой $(2+\psi (n))^n \times 2^{-n}e^{-\sqrt{n}} \to \infty$?

(Как в любой математической задаче, нужно обосновать ответ: привести пример такой функции или доказать её существование или доказать, что такой функции не существует.)

$\ln \dbinom {n^2}{n}$;

$\dbinom {n}{[n/2]}$;

$\dbinom {n^2}{n}$;

$\dbinom {n}{[n^\alpha ]}$, $\alpha \in (0,1)$;

$(2n-1)!! := (2n-1)\cdot (2n-3)\cdot \ldots \cdot 3\cdot 1$;

$\displaystyle \sum_{k=0}^{n}\dbinom {n}{k}^2$;

$\displaystyle \sum_{k=0}^{n}\dbinom {n}{k}^4$.

$s^s = n$;

$s^{s^3} = n$;

$s(n) := \max \left\{ k : k! \leqslant n\right\}$;

$s(n) := \min \left\{ m \in \mathbb {N} : \dbinom {n}{m} < 2^{\binom {m}{2}}\right\}$ (ср. с задачей 4.1.5);

$s(n) := \min \left\{ m \in \mathbb {N} : \dfrac {2^m}{m} > n\right\}$ (функция $2^m/m$ возникает как сложность реализации функций алгебры логики);

$s(n) := \min \left\{ m \in \mathbb {N} : \dbinom {m}{[m/2]} > n\right\}$ (ср. с задачей 1.4.3 (2)).

количества линейных подпространств в $\mathbb {Z}_2^n$ (см. задачу 1.4.7 и определение перед ней);

количества уницикличных графов с $n$ вершинами (см. задачу 2.2.5 (2) и определение перед ней).