Thursday 24 December 2015

combinatorics - Dealing with floor function in binomial coefficients




I'm trying to estimate $\binom{n}{\left \lfloor{\alpha n}\right \rfloor }$ asymptotically using Stirling's formula. However, I'm a little lost with what to do about the floor function here.



In the case without the floor function, there is a greater ease to combine the $\alpha$ and $n$ terms, such as
$$\binom{n}{\alpha n}=\frac{n!}{\alpha n!(n-\alpha n)!} \sim \frac{\sqrt{2\pi n}\left(\frac{n}{e}\right)^n}{\sqrt{2\pi \alpha n}\left(\frac{\alpha n}{e}\right)^{\alpha n} \sqrt{2\pi (n-\alpha n)}\left(\frac{(n-\alpha n)}{e}\right)^{(n-\alpha n)}}
=\frac{1}{\sqrt{2 \pi\alpha (n- \alpha n)}
\alpha^{\alpha n}\left(\left(\frac{n}{e}\right)^{n}\right)^{(\alpha - 1)}
\left(\frac{(n-\alpha n)}{e}\right)^{(n-\alpha n)}}$$
I'm not sure if there's a further simplification of this (if there is, please left me know!) but I'm also not sure how this would work with the floor function.



I tried splitting into cases, so if $\frac{1}{\alpha}n$ leaves $\left \lfloor{\alpha n}\right \rfloor$ the same.



Answer



The asymptotic expansion you have written
without the floor function
implicitly uses the floor function
or you couldn't have approximated
$(\alpha n)!$.



What you have done is a good start.
The next thing to do
is replace all occurrences

of
$n-\alpha n$
by
$n(1-\alpha)$
so you can group more terms
with $n$ together.



I'll let you do that.
If you still have problems,
comment and

I'll proceed further.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...