Stirling's formula

From Polymath Wiki
Jump to: navigation, search

Stirling's formula: [math]n! = (1+o(1)) (2\pi n)^{1/2} n^n e^{-n}[/math].

As a consequence, one has

[math]\binom{n}{\alpha n + k} = (c(\alpha)+o(1)) \theta(\alpha)^k 2^{h(\alpha) n} \frac{1}{\sqrt{n}}[/math]

for fixed [math]0 \lt \alpha \lt 1[/math] and bounded k, where

[math] c(\alpha) := \frac{1}{\sqrt{2\pi \alpha(1-\alpha)}}[/math]
[math] \theta(\alpha) := \frac{1-\alpha}{\alpha}[/math]
[math] h(\alpha) := \alpha \log_2 \frac{1}{\alpha} + (1-\alpha) \log_2 \frac{1}{1-\alpha}.[/math]

Thus for instance

[math]\binom{n}{n/2 + k} = (\sqrt{\frac{2}{\pi}} + o(1)) \frac{1}{\sqrt{n}} 2^n[/math]
[math]\binom{n}{n/3 + k} = (\sqrt{\frac{9}{4\pi}} + o(1)) \frac{1}{\sqrt{n}} 3^n 2^{-2n/3 + k}[/math]

etc. Note that the entropy function [math]h(\alpha)[/math] attains a maximum at [math]\alpha=1/2[/math], which is consistent with the binomials [math]\binom{n}{j}[/math] being maximized at [math]j \approx n/2[/math].

For trinomials, we have

[math]\frac{n!}{(\alpha n+i)! (\beta n + j)! (\gamma_n + k)!} = (c(\alpha,\beta,\gamma)+o(1)) \alpha^{-i} \beta^{-j} \gamma^{-k} 2^{h(\alpha,\beta,\gamma) n} \frac{1}{n}[/math]

for fixed [math]0 \lt \alpha,\beta,\gamma \lt 1[/math] and bounded i,j,k summing to 1 and 0 respectively, where

[math]c(\alpha,\beta,\gamma) := \frac{1}{2\pi} \alpha^{-1/2} \beta^{-1/2} \gamma^{-1/2}[/math]
[math]h(\alpha,\beta,\gamma):= \alpha \log_2 \frac{1}{\alpha} + \beta \log_2 \frac{1}{\beta} + \gamma \log_2 \frac{1}{\gamma}.[/math]

Thus for instance

[math]\frac{n!}{(n/3+i)! (n/3+j)! (n/3+k)!} = (\frac{3^{3/2}}{2\pi} + o(1)) \frac{1}{n} 3^n.[/math]

Here is the Wikipedia article for the Stirling's formula.