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.

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?

share|improve this question
2  
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
4  
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
1  
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

1 Answer 1

up vote 10 down vote accepted

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) $$

Thus your binomial coefficient is

$$ 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)$.

share|improve this answer
    
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 at 12:16

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.