求解n!的近似,斯特林公式(Stirling)的推导

在排列组合中，$n!$的求解是不厌其烦的被用到，用高性能的计算机一个一个的求解也会花费$O(n)$的时间。有没有一种办法找到一个近似于$n!$的公式呢？下面的推导过程可能很low，但是蕴涵的数学思想还是值得学习的。 本文整理自台湾蔡聰明老师。

高估或者低估

只需要找到$a_n$，使得 $$\begin{equation} \lim_{n \to \infty} \frac{n!}{a_n} = 1 ,~~\text{记做} n! \sim a_n. \end{equation}$$ 观察$n!=n(n-1)(n-2)\ldots 3\cdot2\cdot1$,想要估计它的值，采用高估策略很简单，每个因子用$n$代表， $$\begin{equation}\label{f:an} % \underbrace{a + \overbrace{b+\cdots}^{{}=t}+z}_{\text{total}} ~~ a + {\overbrace{b+\cdots}}^{126}+z a_n=\underbrace{n\cdot n \ldots n}_{\text{n个}}=n^n \end{equation}$$ 显然，$\lim_{n\to \infty}\frac{n!}{n^n}=0$,改造($\ref{f:an}$)，取$\frac{1}{2}$使其变小： $$\begin{equation} a_n=\underbrace{\frac{n}{2} \cdot \frac{n}{2} \ldots \frac{n}{2}}_{\text{n个}}=(\frac{n}{2})^n = n^n\cdot 2^{-n} \end{equation}$$ 现在令 $$\begin{equation} b_n=\frac{n!}{(\frac{n}{2})^n} \end{equation}$$ 如果$\lim_{n \to \infty}b_n$=1,那么我们就证明了$a_n=(\frac{n}{2})^n$是$n!$的逼近了。 由 $$\begin{equation} \sqrt[n]{n!}<\frac{n+(n-1)+(n-2)+\ldots+2+1}{n}=\frac{(n+1)n}{2n}=\frac{n+1}{2} \approx \frac{n}{2} \end{equation}$$ 当$n>4$时， $$\begin{equation} n!<(\frac{n}{2})^n \end{equation}$$ 也就是说$(\frac{n}{2})^n$高估了$n!$。

高估或着低估了多少？

我们想得到$b_n=1$的估值，但是我们很难一眼看出$b_n$是多少。先观察估值为1的情况，假设有正数列$S_n$,并且$\lim_{n \to \infty}=S\in R$其中$S\neq 0$,则 $$\begin{equation}\label{f:s_n} \lim_{n \to \infty} \frac{S_{n+1}}{S_n} = 1 \end{equation}$$ 现在考虑($\ref{f:s_n}$)不成立的情况， $$\begin{equation}\label{f:s_n之比的三种情况} \begin{cases} \lim_{n \to \infty} S_n=0 \\ \lim_{n \to \infty} S_n=\infty \\ \lim_{n \to \infty} S_n\text{不存在} \\ \end{cases} \end{equation}$$ 如果($\ref{f:s_n}$)成立，则$(S_n)$可能收敛也可能发散。现在计算 $$\begin{equation}\label{f:b_n+1/b_n} \lim_{n \to \infty} \frac{b_{n+1}}{b_n}= \frac{(n+1)!}{(\frac{n+1}{2})^{n+1}} \cdot \frac{(\frac{n}{2})^n}{n!}=\lim _{n \to \infty} \frac{2}{(1+\frac{1}{n})^n} < \frac{2}{e} \neq 1 \end{equation}$$ 根据 ($\ref{f:s_n之比的三种情况}$)， 则($\ref{f:b_n+1/b_n}$)为0。我们观察到，只需要把$2$替换成$e$，则$\ref{f:b_n+1/b_n}$为1。重新取 $$\begin{equation} a_n=(\frac{n}{e})^n \end{equation}$$ 则有 $$\begin{equation} c_n=\frac{n!}{(\frac{n}{e})^n} \end{equation}$$ 则有 $$\begin{equation}\label{f:c_n+1/c_n} \lim_{n \to \infty} \frac{c_{n+1}}{c_n}= \frac{(n+1)!}{(\frac{n+1}{e})^{n+1}} \cdot \frac{(\frac{n}{e})^n}{n!}=\lim _{n \to \infty} \frac{e}{(1+\frac{1}{n})^n} = \frac{e}{e} = 1 %\lim_{n \to \infty} \frac{c_{n+1}}{c_n}=1 \end{equation}$$ 虽然如此，我们依然不知道$\lim_{n \to \infty}c_n=1$是否成立。由($\ref{f:b_n+1/b_n}$)和($\ref{f:c_n+1/c_n}$)可知， $$\begin{equation} \frac{(n+1)!}{n!} \sim \frac{ (\frac{n+1}{e})^{n+1} }{ (\frac{n}{e})^n } \sim \frac{2}{e} \cdot \frac{ (\frac{n+1}{2})^{n+1} }{ (\frac{n}{2})^n } \end{equation}$$ 所以有等比关系， $$\begin{equation} \frac{ (\frac{n+1}{e})^{n+1} }{ (\frac{n}{e})^n } <\frac{(n+1)!}{n!} < \frac{ (\frac{n+1}{2})^{n+1} }{ (\frac{n}{2})^n } \end{equation}$$ 因此，可以知道 $$\begin{equation} \begin{cases} n!<(\frac{n}{2})^n,~~ \forall n\geq 6 \\ (\frac{n}{e})^n < n!,~~ \forall n \in N \\ n! < (\frac{n+1}{2})^n,~~ \forall n \geq 2 \end{cases} \end{equation}$$ 看来我们又低估$n!$。求$c_n$的极限 $$\begin{equation} \lim_{n \to \infty} c_n=\frac{n!}{(\frac{e}{n})^n}=\beta ,~~ \beta \in {(1,+\infty]} \end{equation}$$ 但是$\beta$是多少呢？

Wallis公式

$$\begin{equation} \frac{2}{1} \cdot \frac{2}{3} \ldots \frac{2n}{2n-1}\cdot \frac{2n}{2n+1} = \frac{\pi}{2} \end{equation}$$ 或者 $$\begin{equation} \lim_{n to \infty} \frac{(2^n \cdot n!)^4}{((2n)!)^2(2n+1)} = \frac{\pi}{2} \end{equation}$$ 或者 $$\begin{equation} \lim_{n \to \infty} \frac{2^{2n}(n!)^2}{(2n)!\sqrt{n}} = \sqrt{\pi} \end{equation}$$ 由 $$\begin{equation} c_n = \frac{n!}{(\frac{n}{e})^n} = \frac{n!e^n}{n^n} \end{equation}$$ 得 $$\begin{equation} n!=c_n n^n e^{-n} \end{equation}$$ 从而 $$\begin{equation} (2n)!=c_{2n}(2n)^{2n}e^{-2n} \end{equation}$$ 代入Wallis公式 $$\begin{equation} \lim_{n \to \infty} \frac{2^{2n}c_n n^{2n} e^{-2n}}{c_{2n}(2n)^{2n} e^{-2n} \sqrt{n}}= \sqrt{\pi} \end{equation}$$ 也就是 $$\begin{equation}\label{f:c_n与wallis的逼近} \lim_{n \to \infty} \frac{c_{n}^2}{c_{2n}\sqrt{n}} = \sqrt{\pi} \end{equation}$$ 如果$\lim_{n \to \infty}=\beta$是有限的，则有$0=\sqrt{\pi}$的荒谬结论，所以， $$\begin{equation} \lim_{n \to \infty}c_n = \lim_{n \to \infty} \frac{n!}{(\frac{n}{e})^n} = \infty \end{equation}$$ 总之，$(\frac{n}{e})^n$低估了$(n!)$。

接近真理

我们再加一个$n$试一试 $$\begin{equation} a_n = (\frac{n}{e})^n n \end{equation}$$ 令 $$\begin{equation} d_n = \frac{n!}{(\frac{n}{e})^n n} \end{equation}$$ 易知其为正递减数列，故$\lim_{n \to \infty}d_n=r$存在，且$0 \leq r < \infty$。令$r \neq 0$，则由Wallis知 $\infty = \sqrt{\pi}$。所以$\lim_{n \to \infty}d_n=0$。也就是说，$(\frac{n}{e})^n n$高估了$n!$。观察($\ref{f:c_n与wallis的逼近}$)，含有$\sqrt{n}$因子，我们在$c_n$的基础上再高估$\sqrt{n}$试试， $$\begin{equation} a_n = (\frac{n}{e})^n \sqrt{n} \end{equation}$$ 现在有 $$\begin{equation} u_n=\frac{n!}{(\frac{n}{e})^n\sqrt{n}} \end{equation}$$ 是一个递减正数列，考虑 $$\begin{equation} \frac{u_n}{u_{n+1}}>1 \end{equation}$$ 因此$\lim_{n \to \infty}= L$存在，并且$0 \le L < \infty$,如果$L=0$,则必须继续估计，现在将其重新代入Wallis公式 $$\begin{equation} \lim_{n \to \infty} \frac{2^{2n}(u_n (\frac{n}{e})^n \sqrt{n})^2}{u_{2n}(\frac{2n}{e})^2n \sqrt{2n} \sqrt{n}} = \sqrt{\pi} \end{equation}$$ 化简 $$\begin{equation} \lim_{n \to \infty}\frac{u_n^2}{u_{2n}}=\sqrt{2\pi} \end{equation}$$ 则 $$\begin{equation} \lim_{n \to \infty} u_n = \sqrt{2\pi} \end{equation}$$ 也就是说 $$\begin{equation} n! \sim \sqrt{2\pi n}n^n e^{-n} \end{equation}$$

---

下面是pdf版本