[Enunciado] Seja $\binomiall{n}{k}$ o número de combinações de $n$ objetos tomados $k$ a $k\text{.}$ Como se sabe, \[ \binomiall{n}{k} = \frac{n!}{k!\,(n-k)!} \]
(Notações alternativas: $\binomial{n}{k}$ e $n \choose k$.)
Fato: $\binomiall{n}{3} \leq \frac{1}{6}\,n^3\text{.}$ Prova: $\binomiall{n}{3} = \frac{n(n-1)(n-2)}{3\,\cdot\,2\,\cdot\,1} \leq \frac{1}{6}\, n^3\text{.}$
Fato: Para todo $k \leq n\text{,}$ $\binomiall{n}{k} \leq \frac{1}{k!}\,n^k\text{.}$ Prova: \[ \binomiall{n}{k} = \frac{n(n-1)\,\cdots\,(n-k+1)}{k!} \leq \frac{1}{k!}\, n^k. \]
Segue daí que, para qualquer $k$ constante, temos $\binomiall{n}{k} = \Oh(n^k)\text{.}$ (Mas não é verdade, por exemplo, que $\binomiall{n}{n/2}$ seja $\Oh(n^{n/2})\text{.}$)
[Enunciado] Seja $\binomiall{n}{k}$ o número de combinações de $n$ objetos tomados $k$ a $k\text{.}$ Como se sabe, $ \binomiall{n}{k} = \frac{n!}{k!\,(n-k)!}. $
Fato: $\binomiall{n}{3} \geq \frac{1}{27}\,n^3\text{.}$ Prova: $\binomiall{n}{3} = \frac{n(n-1)(n-2)}{3\,\cdot\,2\,\cdot\,1} = \frac{n}{3} \frac{n-1}{2} \frac{n-2}{1} \geq (\frac{n}{3})^3 = \frac{1}{3^3}\, n^3\text{.}$
Fato: Para todo $k \leq n\text{,}$ $\binomiall{n}{k} \geq \frac{1}{k^k}\,n^k\text{.}$ Prova: De acordo com o lema abaixo, \begin{align*} \binomiall{n}{k} & = \frac{n}{k} \frac{n-1}{k-1}\,\cdots\, \frac{n-(k-1)}{k-(k-1)} \\ & \geq \frac{n^k}{k^k}. \end{align*}
Lema: Para quaisquer números naturais $i\text{,}$ $k\text{,}$ $n$ tais que $0 \leq i < k \leq n\text{,}$ tem-se \[ \frac{n-i}{k-i} \geq \frac{n}{k}. \]
Prova: Temos $k \leq n\text{,}$ donde $ik \leq in\text{,}$ donde $-ik \geq -in\text{,}$ donde $nk - ik \geq kn - in\text{,}$ donde $(n-i)k \geq (k - i)n\text{,}$ donde $\frac{n-i}{k-i} \geq \frac{n}{k}\text{.}$
A propósito, vale a recíproca: se $0 < i < k$ e $\frac{n-i}{k-i} \geq \frac{n}{k}$ então $k \leq n\text{.}$
Segue daí que, para qualquer $k$ que seja constante em relação a $n\text{,}$ tem-se $\binomiall{n}{k} = \Omega(n^k)\text{.}$ (Mas não é verdade, por exemplo, que $\binomiall{n}{n/2}$ seja $\Omega(n^{n/2})\text{.}$)