Is $\binom{n}{k}$ always considered polynomial?

Question

I'm trying to understand the growth of the term $\binom{n}{k}$ - I saw here a proof that $\binom{n}{k} = O(n^k)$. However, if $k$ is quite large (say $k=n$) then this term is not polynomial. I know that $\binom{n}{k} = \binom{n}{n-k}$ and hence we can deduce that $\binom{n}{k} = O(n^{\min \{k, n-k \}}$.

My problem regards to the worst case, that is when $k=\frac{n}{2}$ (let's assume that $n$ is even). In this case $k = n-k$ and we get $\binom{n}{k} = O(n^{\frac{n}{2}})$, which seems very-not-polynomial to me...

Am I missing something? Or that is just my basic assumptions about the binomial coefficient being a polynomial is simply wrong?

Answer 1

For $n$ and $k$ large, it is helpful to think of this number in terms of Stirling's approximation.

Recall that

$${n \choose k}= \frac{n!}{k! (n-k)!}$$

and

$$n!\approx \sqrt{2\pi}\cdot \frac{n^{n+1/2}}{ e^{n} }.$$

Hence

$${n \choose k}\approx \frac{1}{\sqrt{2\pi}} \sqrt{\frac{n}{k(n- k)}}\left(\frac{n}{k}\right)^{k} \left(\frac{n}{n-k}\right)^{n-k}.$$

This approximation is good when $n$, $k$ and $n-k$ are large. Like people have remarked in the comments, if something is polynomial depends on what you consider variables and what constants.

If both $n$ and $k$ are variables then this thing is not polynomial.

If $n$ is constant, then there are finitely many possibilities for $k$, so the thing is clearly polynomial (bound by a constant).

If $n$ is considered variable but $k$ constant, then observe that $$f(k)={n\choose k}=\frac{1}{k!}n\cdot (n-1)\cdot ...\cdot (n-k+1),$$ which is a polynomial in $n$.

Answer 2

For $0<\alpha<1$, we have $$ \binom{n}{n\alpha}^{-1} = (n+1)\int_0^1 x^{\alpha n} (1-x)^{(1-\alpha)n} \, dx $$ (this is a consequence of the more general relationship $\binom{a+b}{a}^{-1} = (1+a+b)\int_0^1 x^a (1-x)^b \, dx $).

We can use Laplace's Method to find an asymptotic for this integral, whence $$ \binom{n}{n\alpha} \sim \frac{1}{\sqrt{2\pi \alpha(1-\alpha)}}\frac{((1-\alpha)^{-1+\alpha}\alpha^{-\alpha})^{n}}{\sqrt{n}}, $$ which is indeed not polynomial.