# How do I bound ${{n \log n} \choose {\log n}}\frac{1}{n ^ {\log n}}$ tightly?

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): 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 all • Have you tried Stirling's approximation yet? – user14972 Sep 24 '13 at 0:30
• Yes, have you tried these: en.wikipedia.org/wiki/… – Alexander Sep 24 '13 at 0:33
• @Alexander: Well, I used the first one, which gave me the aforementioned bound :) i.e ${n \choose k} \leq n^k/k!$ – TCSGrad Sep 24 '13 at 2:19
• 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}!$ – TCSGrad Sep 24 '13 at 2:38

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: • Perhaps you might continue using $(1-1/n)^n \sim 1/e$. – marty cohen Sep 24 '13 at 1:36