Asymptotics in combinatorics

$\sum_{1 \leqslant k \leqslant n} k^{\alpha k / n} \sim \frac{n^{1+\alpha }}{\alpha \ln n}$;

$\sum_{1 \leqslant k \leqslant n} k^{-\alpha k / n} \sim \frac{n}{\alpha \ln n}$;

$\sum_{1 \leqslant k \leqslant n}(k!)^{-\alpha / n} \sim \frac{n}{\alpha \ln n}$;

$\sum_{1 \leqslant k \leqslant n} k^{\alpha n} \sim \frac{n^{\alpha n}}{1-e^{-\alpha }}$.

$\sum_{1 \leqslant k \leqslant n} \sqrt{C_{n}^{k}} \sim \sqrt[4]{2 \pi n} 2^{n / 2}$;

$\sum_{1 \leqslant k \leqslant n} C_{n}^{k} \sqrt{\left|2 k-n\right|} \sim \frac{\Gamma \left(\frac{3}{4}\right)}{\sqrt{\pi }} \sqrt[4]{2 n} 2^{n}$.

the sums from Problem 1.1.6 (1);

the sums from Problem 1.1.6 (2);

the sums from Problem 1.1.6 (3);

the number $A_n$ of subsets of the set $\left\{ 1, 2, \ldots , n\right\}$ containing no two consecutive numbers;

the same as in part (4), for three consecutive numbers.

$\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$. By definition, this means that there exists a function $\psi (n) = o(1)$ such that

or, equivalently,

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

Find the asymptotics of $\sqrt[n]{\dbinom {n}{[n/2]}}$ (cf. Problems 1.4.3 (2) and 6.1.10 (2)).

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

Find the asymptotics of $\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$, where $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$, where $a_1+\ldots +a_s=1$, $0 < a_k < 1$.

Find the asymptotics of $\ln (n!)$.

Find the asymptotics of $\sqrt[n]{n!}$.

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

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

Stirling’s formula. $n! \sim n^ne^{-n}\sqrt{2\pi n}$, i.e., $\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)$ for $k=k_n < \dfrac {n}{2}$.

This means that there exists a function $\psi (n) = O\left(\dfrac {k}{n}\right)$ such that

or, equivalently,

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

(Formulate yourself what $e^{-\frac{k(k-1)}{2n}+O(k^3/n^2)}$ means here.)

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

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

(Formulate yourself what $e^{-\frac{k^2}{n}(1+o(1))}$ means here.)

Is it true that the notations $e^{o(n)}$ and $o(e^n)$ are ``equivalent''?

That is, is it true that for any function $f : \mathbb {Z} \to (0,+\infty )$ the conditions $\lim_{n\to \infty }\dfrac {\ln f(n)}{n}=0$ and $\lim_{n\to \infty }f(n)e^{-n}=0$ are equivalent?

Find functions $f,g : \mathbb {Z} \to (0,+\infty )$ such that $f(n)\sim g(n)$, but $e^{f(n)} \neq O(e^{g(n)})$.

Can functions $f,g : \mathbb {Z} \to (0,+\infty )$ simultaneously satisfy the relations $f(n)=o(g(n))$ and $g(n)=o(f(n))$?

Can functions $f,g : \mathbb {Z} \to (0,+\infty )$ simultaneously satisfy the relations $f(n)=O(g(n))$ and $g(n)=O(f(n))$?

Do the two relations of part (4) imply that $f(n)\sim g(n)$?

Which function grows faster: $x^{(x^x)}$ or $(x!)^{(2^x)}$?

That is, find $\lim_{x\to \infty } x^{(x^x)}(x!)^{(-2^x)}$.

Does there exist a function $\psi (n) = o(1)$ such that $(2+\psi (n))^n \times 2^{-n}e^{-\sqrt{n}} \to \infty$?

(As in any mathematical problem, the answer must be justified: give an example of such a function, or prove its existence, or prove that no such function exists.)

$\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\}$ (cf. Problem 4.1.5);

$s(n) := \min \left\{ m \in \mathbb {N} : \dfrac {2^m}{m} > n\right\}$ (the function $2^m/m$ arises as the complexity of realizing Boolean functions);

$s(n) := \min \left\{ m \in \mathbb {N} : \dbinom {m}{[m/2]} > n\right\}$ (cf. Problem 1.4.3 (2)).

the number of linear subspaces of $\mathbb {Z}_2^n$ (see Problem 1.4.7 and the definition preceding it);

the number of unicyclic graphs with $n$ vertices (see Problem 2.2.5 (2) and the definition preceding it).