Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Are there really good upper and lower bounds for $\binom{n}{cn}$ when $c$ is a constant $0 < c < 1$? I know that $\left(\frac{1}{c^{cn}}\right) \leq \binom{n}{cn} \leq \left(\frac{e}{c}\right)^{cn}$.

share|improve this question

3 Answers 3

up vote 9 down vote accepted

Using Stirling's formula, $$ \begin{align}{n\choose cn}&\approx\frac{n^n e^{-n}\sqrt{2\pi n}}{(cn)^{cn}e^{-cn}\sqrt{2\pi cn}\cdot ((1-c)n)^{(1-c)n}e^{-(1-c)n}\sqrt{2\pi (1-c)n}}\\&=\frac{1}{c^{cn}(1-c)^{(1-c)n}\sqrt{2\pi c(1-c)n}}\end{align}.$$ You can turn $\approx$ to good upper and lower bounds by fillig in the details of the error term in the Stirling formula.

Edit: For every $n\geqslant1$ and every $c$ in $(0,1)$ such that $cn$ is an integer, $$ \frac{2\pi/\mathrm e^2}{c^{cn}(1-c)^{(1-c)n}\sqrt{2\pi c(1-c)n}}\leqslant{n\choose cn}\leqslant\frac{\mathrm e/\sqrt{2\pi}}{c^{cn}(1-c)^{(1-c)n}\sqrt{2\pi c(1-c)n}}. $$ The ratio between the upper and lower bounds is $\lt1.275$.

share|improve this answer
    
The page @Hagen linked to explains that the ratio between any factorial and its Stirling equivalent is always between $1$ and $a=\mathrm e/\sqrt{2\pi}\lt1.09$. Since binomial coefficients are ratios of one factorial by two other factorials, multiplying the equivalent by $1/a^2$ and $a$ yields rigorous lower and upper bounds. Better estimates are also on the same WP page (did you read it?). –  Did Sep 18 '13 at 11:01
    
The link is in your comment. I did not suggest to use convergent series, only the rigorous bounds, valid for every $n$, which are on the WP page. –  Did Sep 18 '13 at 11:22
    
@Hagen I took the liberty to edit your answer, adding an expansion of the hint you give at the end, since this seems to be what the OP is after. Of course, if you object, please revert to the previous version (and accept my apologies). –  Did Sep 18 '13 at 11:39
    
@Did Thank you. –  Anush Sep 18 '13 at 13:25
    
@Anush You are welcome. Whether the absolute bounds in the Edit or the moving bounds based on the $\exp(1+1/(12n))$ factor explained on the WP page are best, really depends on the setting. –  Did Sep 18 '13 at 13:56

Stirling's Asymptotic Expansion, derived here, is $$ n!=\sqrt{2\pi n}\,n^ne^{-n}\left(1+\frac1{12n}+\frac1{288n^2}-\frac{139}{51840n^3}-\frac{571}{2488320n^4}+O\left(\frac1{n^5}\right)\right) $$ From which we get $$ \begin{align} &\frac{n!}{(cn)!((1-c)n)!}\\[6pt] &=\frac{\left(c^c(1-c)^{1-c}\right)^{-n}}{\sqrt{2\pi c(1-c)n}}\small\left(1-\frac{1-c+c^2}{12c(1-c)}\frac1n+\frac{1-2c+3c^2-2c^3+c^4}{288c^2(1-c)^2}\frac1{n^2}+O\left(\frac1{n^3}\right)\right) \end{align} $$


Absolute Bounds

For $n\ge1$, $$ \sqrt{2\pi n}\,n^ne^{-n}\left(1+\frac1{12n}\right)\le n!\le\sqrt{2\pi n}\,n^ne^{-n}\left(1+\frac1{12n}+\frac1{288n^2}\right) $$ which gives $$ \sqrt{2\pi n}\,n^ne^{-n}\le n!\le\frac{313}{288}\sqrt{2\pi n}\,n^ne^{-n} $$ From which we get, for $1\le cn\le n-1$, $$ \left(\frac{288}{313}\right)^2\frac{\left(c^c(1-c)^{1-c}\right)^{-n}}{\sqrt{2\pi c(1-c)n}} \le\binom{n}{cn} \le\frac{313}{288}\frac{\left(c^c(1-c)^{1-c}\right)^{-n}}{\sqrt{2\pi c(1-c)n}} $$ Note that $$ \frac{e}{\sqrt{2\pi}}\doteq1.0844\lt1.0868\doteq\frac{313}{288} $$ so this is close to Hagen von Eitzen's answer.


The bound mentioned in Hagen's answer is based on the fact that the ratio $$ \frac{\Gamma(n)}{\sqrt{2\pi n}\,n^ne^{-n}} $$ is decreasing in $n$. Thus, the greatest ratio is for $n=1$ and therefore, $$ \sqrt{2\pi n}\,n^ne^{-n}\le n!\le\frac{e}{\sqrt{2\pi}}\sqrt{2\pi n}\,n^ne^{-n} $$

share|improve this answer
    
This probably uses the postfactor $1+c/(12n)+\cdots$ instead of $1+1/(12cn)+\cdots$ for $(cn)!$ (and similarly for $((1-c)n)!$). –  Did Sep 18 '13 at 11:20
    
@Did: Ack, yes. Fixing.. –  robjohn Sep 18 '13 at 11:21
    
I love the upvotes... By the way, using asymptotic expansions seems offtopic if the OP is interested in nonasymptotic bounds. –  Did Sep 18 '13 at 11:22
    
Thanks for noticing the error. However, as for the asymptotic expansion being off-topic, I did not notice that the OP was not interested in asymptotic bounds. I was simply supplying what "error terms" I could. –  robjohn Sep 18 '13 at 11:35
    
"How can I use that to give strict upper or lower bounds?" –  Did Sep 18 '13 at 11:40

Hint: as $n$ goes to infinity, you can approximate $\binom{n}{cn}$ by Entropy function as follows: $$ \binom{n}{cn}\approx e^{nH(c)}. $$ where $H(c)=-c\log(c)-(1-c)\log(1-c)$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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