3
$\begingroup$

I've met some difficulties with such question: How can we approximate a binomial coefficient by using a Stirling's factorial approximation.

I've evaluate a little bit and got this

How can I transform the right side of this equation for getting estimation like (1 + ?/n + O(1/n^2))

$\endgroup$
4
$\begingroup$

Another case is when $k$ is a constant times $n$. Let $k = a n $ where $0 < a < 1$, so $k/n = a$.

Then

$\begin{align} \binom{n}{k} &=\frac{n!}{k!(n-k)!}\\\\ &\approx. \frac{\sqrt{2\pi n}(\frac{n}{e})^n} {\sqrt{2\pi k}(\frac{k}{e})^k \sqrt{2\pi (n-k)}(\frac{n-k}{e})^{n-k}}\\\\ &=\frac{1}{\sqrt{2\pi k}(k/n)^k \sqrt{1-(k/n)}(1-(k/n))^{n-k}}\\ &=\frac{1}{\sqrt{2\pi k(1-k/n)}a^{an} (1-a)^{n-an}}\\ &=\frac{1}{\sqrt{2\pi n a(1-a)}(a^a(1-a)^{1-a})^n}\\ \end{align} $

For example, if $a = 1/2$, since $a(1-a) = 1/4$ and $a^a (1-a)^{1-a} =(1/2)^{1/2}(1/2)^{1/2} =1/2 $, this becomes

$\binom{n}{n/2} \approx \frac{1}{\sqrt{2n\pi/4}(1/2)^n} = \frac{2^n}{\sqrt{n\pi/2}} $.

For another example, if $a = 1/3$, since $a(1-a) = 2/9$ and $a^a (1-a)^{1-a} =(1/3)^{1/3}(2/3)^{2/3} =\frac{(2^2)^{1/3}}{3} =\frac{4^{1/3}}{3} =(4/27)^{1/3} $, this becomes

$\binom{n}{n/3} \approx \frac{1}{\sqrt{2n\pi(2/9)}(4/27)^{n/3}} = \frac{3(27/4)^{n/3}}{2\sqrt{n\pi}} $.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If k > n, the binomial coefficient is zero. $\endgroup$ – marty cohen Apr 29 '15 at 2:28
  • $\begingroup$ Not if n and k are integers. $\binom{n}{k} = n(n-1)...(n-k+1)/k! = 0 $ if $k > n$. $\endgroup$ – marty cohen Apr 29 '15 at 2:43
  • $\begingroup$ Stirling's formula doesn't know about integers and is only an approximation. $\endgroup$ – marty cohen Apr 30 '15 at 1:05
  • $\begingroup$ I meant that one can use an asymptotic, large argument expansion of the Gamma function to derive Stirling's formula and can do so for non-integers. $\endgroup$ – Mark Viola Apr 30 '15 at 2:24
1
$\begingroup$

Stirling's approximation is given by $n!\approx. \sqrt{2\pi n}(n/e)^n$. Thus, for large $n$, and $n>>k$, we have

$$\begin{align} \binom{n}{k}&=\frac{n!}{k!(n-k)!}\\\\ &\approx. \frac{\sqrt{2\pi n}(\frac{n}{e})^n}{k!\sqrt{2\pi (n-k)}(\frac{n-k}{e})^{n-k}}\\\\ &=\frac{n^ne^{-k}}{k!\sqrt{1-(k/n)}n^{n-k}(1-(k/n))^{n-k}}\\\\ &\approx. \frac{n^k}{k!(1-(k/n))^{-k+1/2}}\\\\ &=\frac{n^k}{k!}\,\left(1-\frac{k}{n}\right)^{k-1/2} \end{align}$$

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

Thank you all for your answers, but I mentioned that I have to use slightly different factorial approximation: $$ n!=\sqrt{2\pi n}\cdot(\frac{n}{e})^n\cdot\left(1+\frac{1}{12n}+\frac{1}{288n^2}+O(\frac{1}{n^3})\right) $$ So, by using this approximation it's necessary to obtain approximation for the binomial coefficient $\binom{an}{n}$. Sorry that I defined the task conditions rudely: $a$ - is a constant and $n\rightarrow \infty$.

So, after doing some conversions I've got this one: $$\sqrt{\frac{a}{2\pi(a-1)n}}\cdot\left(\frac{a^a}{(a-1)^{a-1}}\right)^n\cdot\frac{1+\frac{1}{12an}+\frac{1}{288(an)^2}}{\left({1+\frac{1}{12n}+\frac{1}{288n^2}}\right)\cdot\left(1+\frac{1}{12(a-1)n}+\frac{1}{288((a-1)n)^2}\right)}$$ Then let's transform the right side of the expression: $$\frac{1+\frac{1}{12an}+\frac{1}{288(an)^2}}{\left({1+\frac{1}{12n}+\frac{1}{288n^2}}\right)\cdot\left(1+\frac{1}{12(a-1)n}+\frac{1}{288((a-1)n)^2}\right)}=\\=\displaystyle{\frac{1+\frac{1}{12an}+O(\frac{1}{n^2})}{1+\frac{a}{12(a-1)n}+O(\frac{1}{n^2})}}$$ Finally, we get: $$\displaystyle{1+X=\frac{1+\frac{1}{12an}}{1+\frac{a}{12(a-1)n}}}\rightarrow X=\frac{a-1-a^2}{a(12(a-1)n+a)}$$So, the right side of our approximation can be submitted as: $$1+\frac{a-1-a^2}{12a(a-1)}\cdot\frac{1}{n}+O\left(\frac{1}{n^2}\right)$$ And the whole answer is: $$\sqrt{\frac{a}{2\pi(a-1)n}}\cdot\left(\frac{a^a}{(a-1)^{a-1}}\right)^n\cdot\left(1+\frac{a-1-a^2}{12a(a-1)}\cdot\frac{1}{n}+O\left(\frac{1}{n^2}\right)\right)$$

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