Approximate combination $^nC_k$ by polynomial

Question

Is it possible to approximate ${}^n C _k$ by polynomial? I want only to know the order (e.g. $O(n^3)$), so accuracy doesn't matter much.

If $n \gg r$, we have $$ {}^n C _r = O(n^r). $$

But how about general case?

Answer 1

The simplest approximation comes, as usual, for Stirling apparoxiamtion.

Considering $k=a \,n$ $$\binom{n}{k}=\binom{n}{a n}=\frac{\Gamma (n+1)}{\Gamma ((1-a) n+1)\, \Gamma (a n+1)}$$ Taking logarithms, using three times Stirling approximation and finishing with Taylor series $$\log \left (\binom{n}{a n}\right)=-\big[a\log(a)+(1-a)\log(1-a)\big]\,n-\log \left( \sqrt{2\pi a(1-a) n}\right)-$$ $$\sum_{k=0}^\infty\frac {P_k(a)}{c_k\,\big[a(1-a)n \big]^{2k+1}}$$ The $c_k$ form sequence $A046969$ in $OEIS$ and the very first polynomials are $$\left( \begin{array}{cc} k & P_k(a) \\ 0 & a^2-a+1 \\ 1 & -a^6+3 a^5-3 a^4+a^3-3 a^2+3 a-1 \\ 2 & a^{10}-5 a^9+10 a^8-10 a^7+5 a^6-a^5+5 a^4-10 a^3+10 a^2-5 a+1 \\ \end{array} \right)$$

For the case of comb(735, 214) you used in comments, neglecting the summation gives for its logarithm $439.9103$ while its exact value is $439.9098$. The first term of the summation is $-0.0004$.

Answer 2

This approximation is good for quick estimates:

$$ \left(\frac{n}{r}\right)^r \le \binom{n}{r} \le \left(\frac{e\cdot n}{r}\right)^r$$

(see e.g. this question for proof). If $r > \tfrac{n}{2}$, then use the identity $\binom{n}{r} = \binom{n}{n-r}$ first to get tighter bounds.

Using the example from your comment,

$$ 3^{214} < \left(\frac{735}{214}\right)^{214} \le \binom{735}{214} \le \left(\frac{2.72\times 735}{214}\right)^{214} < 10^{214}$$

so we can roughly estimate the value to be in the $10^{100}$ to $10^{200}$ range. (The actual value is about $1.123\times 10^{191}$.)