1
$\begingroup$

I'm trying to get a tight upper bound for the following expression:

${{n \log n} \choose {\log n}}\frac{1}{n ^ {\log n}}$

The bound that I've obtained is too loose, which is as follows:

$ m = nM, \\ M = \log n$

${{m} \choose {M}}\frac{1}{n ^ {M}} = \frac{({m} )!}{(m - M)! M!} \frac{1}{n^M} = \frac{m \cdot (m -1) \cdot (m - 2) \cdots (m - (M - 1))}{n \cdot n \cdot n \cdots n}\frac{1}{M!} \leq (\frac{m}{n})^M \cdot \frac{1}{M!} = \frac{M^M}{M!}$

But,the bound on the RHS is far greater than the LHS, as I can see when I graph the two quantities (Red is LHS, Blue is RHS):

${{m} \choose {M}}\frac{1}{n ^ {M}} and \frac{M^M}{M!}$

Any help in how to get a tighter bound would be much appreciated!

EDIT: The corrected graph of RHS vs LHS is added, which turns out to be a tight bound after allenter image description here

$\endgroup$
  • 2
    $\begingroup$ Have you tried Stirling's approximation yet? $\endgroup$ – user14972 Sep 24 '13 at 0:30
  • 1
    $\begingroup$ Yes, have you tried these: en.wikipedia.org/wiki/… $\endgroup$ – Alexander Sep 24 '13 at 0:33
  • $\begingroup$ @Alexander: Well, I used the first one, which gave me the aforementioned bound :) i.e ${n \choose k} \leq n^k/k!$ $\endgroup$ – TCSGrad Sep 24 '13 at 2:19
  • 1
    $\begingroup$ Ahh - my bad! The graph I'd posted is incorrect - the blue graph is $x^x/x!$, whereas it should be ${\log x}^{\log x}/{\log x}!$ $\endgroup$ – TCSGrad Sep 24 '13 at 2:38
3
$\begingroup$

For $n >>1 $

$$ \frac{\Gamma(n\log{n}+1)}{\Gamma(\log{n}+1) \Gamma(n\log{n}-\log{n}+1)} \sim \frac{\sqrt{2\pi n\log{n}}\left(\frac{n\log{n}}{e}\right)^{n\log{n}}}{\sqrt{2\pi \log{n}}\left(\frac{\log{n}}{e}\right)^{\log{n}}\left(\sqrt{2\pi(n-1)\log{n}}\right) \left(\frac{(n-1)\log{n}}{e}\right)^{(n-1)\log{n}}}= \frac{\sqrt{n} \cdot n^{n\log{n}}}{\left(\sqrt{2\pi(n-1)\log{n}}\right)\left(\frac{(n-1)\log{n}}{e}\right)^{(n-1)\log{n}}} = $$ $$ \frac{\sqrt{n} \cdot n^{n\log{n}}}{\left(\sqrt{2\pi(n-1)\log{n}}\right)\left(\frac{(n-1)\log{n}}{e}\right)^{(n-1)\log{n}}}=\frac{\sqrt{n} \cdot n^{n\log{n}}n^{(n-1)}}{\left(\sqrt{2\pi(n-1)\log{n}}\right)\left(\left((n-1)\log{n}\right)^{(n-1)\log{n}}\right)} = $$ $$ \frac{\sqrt{n} \cdot n^{n\log{n}}n^{(n-1)}}{\left(\sqrt{2\pi}\right)\left((n-1)\log{n}\right)^{(n-1)\log{n}+\frac{1}{2}}}=\left(\frac{1}{\sqrt{2\pi}}\right)\frac{n^{n\log{n}+n-\frac{1}{2}}}{\left((n-1)\log{n}\right)^{(n-1)\log{n}+\frac{1}{2}}} = $$ $$ \left(\frac{1}{\sqrt{2\pi}}\right)\frac{n^{n}n^{n\log{n}-\frac{1}{2}}}{\left((n-1)\log{n}\right)^{n\log{n}-\log{n}+\frac{1}{2}}}= $$ $$ \left(\frac{1}{\sqrt{2\pi}}\right)\frac{n^{n}n^{n\log{n}-\frac{1}{2}}}{\left((n-1)\log{n}\right)^{n\log{n}}\left((n-1)\log{n}\right)^{-\log{n}+\frac{1}{2}}}= $$ $$ \left(\frac{1}{\sqrt{2\pi}}\right)\left(\frac{n^{n\log{n}}}{(n-1)^{n\log{n}}}\right)\frac{n^{n}n^{-\frac{1}{2}}}{\left(\log{n}\right)^{n\log{n}}\left((n-1)\log{n}\right)^{-\log{n}+\frac{1}{2}}}\sim $$ $$\left(\frac{1}{\sqrt{2\pi}}\right)\left(e\right)^{\log{n}}\frac{n^{n}n^{-\frac{1}{2}}}{\left(\log{n}\right)^{n\log{n}}\left((n-1)\log{n}\right)^{-\log{n}+\frac{1}{2}}}=$$ $$ \left(\frac{1}{\sqrt{2\pi}}\right)\left(e\right)^{\log{n}}\frac{n^{n}n^{-\frac{1}{2}}}{\left(\log{n}\right)^{n\log{n}}\left((n-1)\log{n}\right)^{-\log{n}}\left((n-1)\log{n}\right)^{\frac{1}{2}}} = $$ $$ \left(\frac{1}{\sqrt{2\pi}}\right)\left(e\right)^{\log{n}}\frac{n^{n}n^{-\frac{1}{2}}}{\left(\log{n}\right)^{(n-1)\log{n}+\frac{1}{2}}\left(n-1\right)^{-\log{n}+\frac{1}{2}}} = $$ $$ \left(\frac{1}{\sqrt{2\pi}}\right)\frac{n^{n+\frac{1}{2}}}{\left(\log{n}\right)^{(n-1)\log{n}+\frac{1}{2}}\left(n-1\right)^{-\log{n}+\frac{1}{2}}} = $$ $$ \left(\frac{n}{2\pi(n-1)\log{n}}\right)^{\frac{1}{2}}\left(\frac{n-1}{(\log{n})^{n-1}}\right)^{\log{n}}n^n $$ Here is a picture of the whole shebang: WolframAlpha

$\endgroup$
  • $\begingroup$ Perhaps you might continue using $(1-1/n)^n \sim 1/e$. $\endgroup$ – marty cohen Sep 24 '13 at 1:36

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.