0
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ It depends on what is a variable. In this case I assume $n$ is our variable and $k$ is constant, so saying $n=k$ does not make sense. $\endgroup$ – I was suspended for talking Apr 15 '18 at 12:50
  • 1
    $\begingroup$ The variable is indeed $n$. My question actually regards for a theoretical algorithm for the vertex cover problem, so I need to take care of the worst case with regards to $k$ (clearly there's a graph with minimal VC of size $k=n$). $\endgroup$ – noamgot Apr 15 '18 at 12:52
  • 1
    $\begingroup$ Yes, $\binom{2n}{n}=\frac{(2n)!}{(n!)^2}\sim\frac{2^{2n}}{\sqrt{\pi n}}$, by Stirling's approximation, is not polynomial. $\endgroup$ – user552631 Apr 15 '18 at 12:59
  • $\begingroup$ You can get an approximation to $\binom {2n}n$ or $\binom {2n+1}n$ using Stirling's approximation to the factorials. Note that this is not of the form $\binom nk$ with $k$ fixed so is not polynomial in form. $\endgroup$ – Mark Bennet Apr 15 '18 at 13:00
  • 1
    $\begingroup$ Did you read the comments on the question you link to? The very first one explains that the binomial is not necessarily polynomial when $k$ is a function of $n$ (which it is, in your case: $k=n/2$). $\endgroup$ – David K Apr 15 '18 at 13:29
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.