5
$\begingroup$

Any ideas on finding a good estimate/approximation for $\frac AB$ where $A = N^L$ and $B = {N+L\choose N}$?

$\endgroup$
6
  • 2
    $\begingroup$ You could try applying Stirling on the factorials implicit in the binomial coefficient... $\endgroup$ – J. M. isn't a mathematician May 2 '11 at 17:07
  • 1
    $\begingroup$ I don't understand the notations $N^L$ and $C_{N+L}^N$. What do those mean? $\endgroup$ – Mitch May 2 '11 at 17:17
  • $\begingroup$ @Mitch: I am taking $N^L$ as the exponential and $C_{N+L}^N$ as the binomial coefficient of $N+L$ choose $N$ $\endgroup$ – Ross Millikan May 2 '11 at 17:52
  • 1
    $\begingroup$ In what regime? If $L$ is fixed and $N$ is allowed to grow then the ratio approaches $L!$. $\endgroup$ – Qiaochu Yuan May 2 '11 at 17:54
  • $\begingroup$ Wow, just the slightest change in notation (from lower case to upper) made me misunderstand. That's not a problem with the notation, but a problem with my reading ability. $\endgroup$ – Mitch May 2 '11 at 17:56
4
$\begingroup$

If you expand $B$ as $\frac{(N+L)!}{N!L!}$ and then use Stirling's approximation on the factorials, you will be very close.

$\endgroup$
3
$\begingroup$

$\log(A/B) = \log(L!) - \sum_{j=1}^L \log(1+j/N)$. You can approximate or bound the sum in various ways, depending on your needs.

$\endgroup$
2
$\begingroup$

I'm assuming that by $C_{N+L}^N$ you mean the binomial coefficient $(N+L)!/N!L!$. (I would denote this by ${N+L \choose N}$.)

If you're thinking of $L$ as a constant then you can write this as

$$ {(N+L)(N+L-1) \cdots (N+1) \over L!}. $$

And you can expand out the numerator; you get

$$ {(N^L + {L(L+1) \over 2} N^{L-1} + \cdots) \over L!} $$

$\endgroup$
1
  • $\begingroup$ Thank you, this is a good hint as well. $\endgroup$ – Leo May 2 '11 at 18:59

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.