# How to compute the asymptotic growth of $\binom{n}{\log n}$?

I'm interested with tight bounds for: $$f(n)={n\choose{\log{n}}}$$ It sounds like it's something simple, but I can't get a nice expression I can use.

Any ideas on how to do this?

-
We can rewrite this in terms of the gamma function, I think: $${n\choose\log n}=\frac{\Gamma(n+1)}{\Gamma(\log n+1)\Gamma(n-\log n)}.$$ Can you use properties of $\Gamma$ to make more progress? –  Ian Coley Apr 16 '13 at 16:54
i'm not familiar with gamma function. i need this for proving running time complexity for an algorithm. so, i need something comparable with polynomials, poly-logarithms, or super-polynomials/exponential functions. –  gilad hoch Apr 16 '13 at 17:06
What do you mean by "tight"? You can get decent bounds from the inequality $$\left(\frac{n}{k}\right)^k \le \binom{n}{k} \le \left(\frac{en}{k}\right)^k$$ –  Alfonso Fernandez Apr 16 '13 at 17:13
In my above comment, it should read $\Gamma(n-\log n+1)$. I'm not sure how to attack it further, sorry. –  Ian Coley Apr 16 '13 at 17:14
Building upon the formula of Alfonso, I commonly use $\binom{n}{k} \approx n^k$ for small (constant) $k$, which is not far off. And no, $\log n$ is not constant, but $\binom{n}{\log n} \approx n^{\log n}$ is a quick and quite precise estimate as Aryabhata confirms below. –  TMM Apr 16 '13 at 17:47

You can make use of Stirling's approximation.

$$\log n! = n\log n - n + \frac{1}{2} \log 2\pi n + O\left(\frac{1}{n}\right)$$

$$\log \binom{n}{\log n} = \log n! - \log ((n-\log n)!) - \log ((\log n)!)$$

$$= n\log n -(n-\log n)\log (n-\log n) + O(\log n \log \log n)$$

$$= n \log n -(n - \log n)\left(\log n + \log \left(1 - \frac{\log n}{n}\right)\right) + O(\log n \log \log n)$$

$$= \log^2 n + (n-\log n)\left(\frac{\log n}{n} + O\left(\frac{\log^2 n}{n^2}\right)\right) + O(\log n \log \log n)$$

$$= \log^2 n + O(\log n \log \log n)$$

$$n^{\log n +O(\log \log n)}$$

We can make it more accurate by computing the leading terms in $O(\log n \log \log n)$.

-
This certainly looks more plausible than the $n^{n \log n}$ you first had. –  TMM Apr 16 '13 at 17:44
@TMM: Yeah, a computation mistake... –  Aryabhata Apr 16 '13 at 17:44
thanks! it helps a lot! –  gilad hoch Apr 16 '13 at 18:44
@giladhoch: You are welcome. –  Aryabhata Apr 17 '13 at 0:25
@PhaniRaj: Your edit was too minor for such an ancient post. I approved it, although if I had realised the date of the original I would have rejected it. –  user1729 Jun 23 '14 at 12:16