$N^L$ vs. ${N+L\choose N}$

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

-

2
You could try applying Stirling on the factorials implicit in the binomial coefficient... – J. M. May 2 '11 at 17:07

1
I don't understand the notations $N^L$ and $C_{N+L}^N$. What do those mean? – Mitch May 2 '11 at 17:17
@Mitch: I am taking $N^L$ as the exponential and $C_{N+L}^N$ as the binomial coefficient of $N+L$ choose $N$ – Ross Millikan May 2 '11 at 17:52

1
In what regime? If $L$ is fixed and $N$ is allowed to grow then the ratio approaches $L!$. – Qiaochu Yuan May 2 '11 at 17:54
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. – Mitch May 2 '11 at 17:56
show 1 more comment

3 Answers

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

-

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

-

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!}$$

-

Thank you, this is a good hint as well. – Leo May 2 '11 at 18:59
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 21, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9342897534370422, "perplexity_flag": "middle"}