Stirling 公式

Stirling公式

• 1.阶乘

  $$n!=n(n-1)(n-2)\cdots \times 3\times 2\times 1(n\ge 1)$$$$0！=1$$

• Stirling公式

  $$n!\approx \sqrt{2\pi n}(\frac{n}{e}{)}^n$$

  当n足够大的时候，n！的计算量很大，Stirling公式这个时候就很好用，公式也可以变形为

  $$\underset{n+\infty }{\lim }\frac{n!}{\sqrt{2\pi n}(\frac{n}{e}{)}^n}=1$$

  或者也等价于

  $$\underset{n+\infty }{\lim }\frac{e^{n}n!}{n^n\sqrt{n}}=\sqrt{2\pi }$$

  在Wikipedia上看到，Stirling公式是由 $$\mathrm{A}\mathrm{b}\mathrm{r}{\mathrm{r}}^{\prime }\mathrm{m}\mathrm{a}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{d}\mathrm{e}\mathrm{M}\mathrm{o}\mathrm{i}\mathrm{v}\mathrm{r}\mathrm{e}$$发现的，不过没有那么精确

  $$n!=c{n}^{n+\frac{1}{2}}{e}^{-n}$$ 其中c为常数,后来Stirling证明了$c=\sqrt{2\pi n}$，约为2.506628274631.更加精确的形式是由雅克·比内发现的。

推导

这个公式的误差的估计，可以推导如下。首先不直接估计$n!$,而是考虑它的自然对数：

$$\mathsf{l}\mathsf{n}(n!)=\mathsf{l}\mathsf{n}1+\mathsf{l}\mathsf{n}2+\mathsf{l}\mathsf{n}3+\cdots +\mathsf{l}\mathsf{n}n.$$

即：

$$\mathsf{l}\mathsf{n}(n!)-\frac{1}{2}\mathsf{l}\mathsf{n}n=\mathsf{l}\mathsf{n}1+\mathsf{l}\mathsf{n}2+\cdots +lnn-\frac{1}{2}\mathsf{l}\mathsf{n}n\mathsf{l}\mathsf{n}$$

这个方程的右边是积分${\int }_1^n\mathsf{l}\mathsf{n}(x)dx=n\mathsf{l}\mathsf{n}n-n+1$的近似值(利用梯形法则)，而他的误差由欧拉-麦克劳林公式给出：

$$\mathsf{l}\mathsf{n}(n!)-\frac{\mathsf{l}\mathsf{n}n}{2}=\mathsf{l}\mathsf{n}1+\mathsf{l}\mathsf{n}2+\mathsf{l}\mathsf{n}3\cdots +\mathsf{l}\mathsf{n}(n-1)+\frac{\mathsf{l}\mathsf{n}n}{2}=n\mathsf{l}\mathsf{n}n-n+1+\sum _{k=2}^m\frac{B_k(-1{)}^k}{k(k-1)}(\frac{1}{n^{k-1}}-1)+R_{m,n}$$

其中$B_k$是伯努利数，$R_{m,n}$是欧拉麦克劳林中的余项。取极限，可得：

$$\underset{n\to \infty }{\lim }(\mathsf{l}\mathsf{n}n!-n\mathsf{l}\mathsf{n}n+n-\frac{\mathsf{l}\mathsf{n}n}{2})=1-\sum _{k=2}^m\frac{B_k(-1{)}^k}{k(k-1)}+\underset{n\to \infty }{\lim }{R}_{m,n}.$$

把这个极限记为 $\mathsf{y}$ .由于欧拉-麦克劳林公式中的余项$R_{m,n}$满足：

$$R_{m,n}=\underset{n\to \infty }{\lim }+\mathrm{O}(\frac{1}{n^{2m-1}})$$

其中用到了大 $\mathrm{O}$符号，与以上的方程结合，便得出对数形式的近似公式：

$$\mathsf{l}\mathsf{n}n!=n\mathsf{l}\mathsf{n}(\frac{n}{e})+\frac{\mathsf{l}\mathsf{n}n}{2}+y+\sum _{k=2}^m\frac{B_k(-1{)}^k}{k(k-1)n^{k-1}}+\mathrm{O}(\frac{1}{n^{2m-1}})$$

两边取质数，并选择任何正整数$m$，便得到了一个含有未知数$e^y$的公式。当$m=1$时，公式为：

$$n!=e^y\sqrt{n}(\frac{n}{e}{)}^n[1+\mathrm{O}(\frac{1}{n})]$$

这个上述表达式带入沃利斯乘积公式，并令$n$趋于无穷，便可以得出

$$e^y(e^y=\sqrt{2\pi })$$

因此，我们便得出斯特林公式:

$$n!=\sqrt{2\pi n}(\frac{n}{e}{)}^n[1+\mathrm{O}(\frac{1}{n})]$$

这个公式也可以反复使用分部积分法来得出，首相可以通过最速下降法得到。把以下的和：

$$\mathsf{l}\mathsf{n}(n!)=\sum _{j=1}^n\mathsf{l}\mathsf{n}j$$

用积分近似代替，可以得出不含$\sqrt{2\pi n}$的因子的Stirling公式（这个因子通常在实际应用中无关）：

$$\sum _{j=1}^n\mathsf{l}\mathsf{n}j\approx {\int }_1^n\mathsf{l}\mathsf{n}xdx=n\mathsf{l}\mathsf{n}n-n+1$$

收敛速率和误差分析

更加精确的近似公式为：

$$n!=\sqrt{2\pi n}(\frac{n}{e}{)}^n{e}^{{\lambda }_n}$$

其中：

$$\frac{1}{12n+1}<{\lambda }_n<\frac{1}{12n}$$

Stirling公式实际上是一下级数（现在成为Stirling级数）的第一个近似值：

$$n!=\sqrt{2\pi n}(\frac{n}{e}{)}^n(1+\frac{1}{288n^2}-\frac{139}{51840n^3}-\frac{517}{2488320n^4}+\cdots )$$

当$n\to \infty$时，截断级数的误差等于第一个省略掉的项。这是渐进展开式的一个例子。他不是一个收敛级数，对于任何特殊值n，级数的准确性只在取有限个项时达到最大，如果取更多的项，则准确性将变得越来越差。
阶乘的对数的渐近展开式也称为Stirling级数：

$$\mathsf{l}\mathsf{n}n!=n\mathsf{l}\mathsf{n}n-n+\frac{1}{2}\mathsf{l}\mathsf{n}(2\pi n)+\frac{1}{12n}-\frac{1}{360n^3}+\frac{1}{1260n^5}-\frac{1}{1680n^7}+\cdots$$

这种情况下，级数的误差总是与第一个省略掉的异号，且最多同大小。

Gamma函数的Stirling公式

对于所有正整数，有：

$$n!=\Pi (n)=\Gamma (n+1).$$

然而，Gamma函数与阶乘不一样，他对于所有复数都有定义。尽管如此，Stirling公式仍然适用。如果$R(z)>0$，那么：

$$\mathsf{l}\mathsf{n}\Gamma (z)=(z-\frac{1}{2})\mathsf{l}\mathsf{n}z-z+\frac{\mathsf{l}\mathsf{n}2\pi }{2}+2{\int }_o^{\infty }\frac{arctan\frac{t}{2}}{e^{2\pi t}-1}dt$$

反复使用分部积分法，可得一下渐近展开式：

$$\mathsf{l}\mathsf{n}\Gamma (z)=(z-\frac{1}{2})\mathsf{l}\mathsf{n}z-z+\frac{\mathsf{l}\mathsf{n}2\pi }{2}+\sum _{n=1}^{\infty }\frac{(-1{)}^{n-1}{B}_n}{2n(2n-1)z^{2n-1}}$$

其中$B_n$是第n个伯努利数。当$|argz|<\pi -ϵ$，其中 $ϵ$ 是正数时，这个公式对于绝对值足够大的$z$是适用的，当使用了最初$m$个项时，误差为$\mathrm{O}(z^{-m-\frac{1}{2}})$。对应的近似值可以写为：

$$\Gamma (z)=\sqrt{\frac{2\pi }{z}}(\frac{z}{e}{)}^z[1+\mathrm{O}(\frac{1}{z})]$$

Stirling公式的收敛公式

欲得出Stirling公式的一个收敛形式，我们必须计算：

$${\int }_0^{\infty }\frac{2arctan\frac{t}{2}}{e^{2\pi t}-1}dt=\mathsf{l}\mathsf{n}\Gamma (z)-(z-\frac{1}{2})\mathsf{l}\mathsf{n}z+z-\frac{1}{2}\mathsf{l}\mathsf{n}(2\pi )$$

一种方法是利用含有上升阶乘幂的级数。如果

$$z^{\overline{n}}=z(z+1)\cdots (z+n-1)$$

那么：

$${\int }_0^{\infty }\frac{2arctan\frac{t}{2}}{e^{2\pi t}-1}dt=\sum _{n=1}^{\infty }\frac{c_n}{(z+1{)}^{\overline{n}}}$$

其中：

$$c_n=\frac{1}{n}{\int }_0^1{x}^{\overline{n}}(x-\frac{1}{2})dx$$

从中可以得出Stirling级数的一个收敛形式：

$$\mathsf{l}\mathsf{n}\Gamma (z)=(z-\frac{1}{2})\mathsf{l}\mathsf{n}z-z+\frac{\mathsf{l}\mathsf{n}2\pi }{2}+\frac{1}{12(z+1)}+\frac{1}{12(z+1)(z+2)}+\frac{59}{360(z+1)(z+2)(z+3)}+\frac{29}{60(z+1)(z+2)(z+3)(z+4)}+\cdots$$
他在R(z)>0时收敛

适用于计算器的形式

以下的近似值

$$\Gamma \approx \sqrt{\frac{2\pi }{z}}(\frac{z}{e}\sqrt{zsinh\frac{1}{z}+\frac{1}{810z^6}}{)}^z$$

或：

$$2\mathsf{l}\mathsf{n}\Gamma (z)\approx \mathsf{l}\mathsf{n}(2\pi )-\mathsf{l}\mathsf{n}z+z[2\mathsf{l}\mathsf{n}z+\mathsf{l}\mathsf{n}(zsinh\frac{1}{z}+\frac{1}{810z^6})-2]$$

可以通过把Stirling公式整理，并注意到它的幂级数与双曲正弦函数的泰勒级数展开式的相似性来得出。当$z$的实数部分大于8时，这个近似值精确到小数点后8位。2002年，Robert H. Windschitl建议计算$\Gamma (z)$函数Gergo Nemes在2007年提出了一个近似公式，它的精确度与Windschitl的公式相等，但更加简单：

$$\Gamma (z)\approx \sqrt{\frac{2\pi }{z}}[\frac{1}{e}(z+\frac{1}{12z-\frac{1}{10z}}){]}^z$$

或：

$$\mathsf{l}\mathsf{n}\Gamma (z)\approx \frac{1}{2}[\mathsf{l}\mathsf{n}(2\pi )-\mathsf{l}\mathsf{n}z]+z[\mathsf{l}\mathsf{n}(z++\frac{1}{12z-\frac{1}{10z}})-1]$$

这个到后面全部都是Wikipedia上抄的了，因为不知道怎么总结了，就选择直接把他手打了一份，就当练习Markdown编辑器了，立个flag，把这里面的一些 名词都手打一遍，看一遍。今天就这样了吧，有点醉or$\beta$

斯特灵公式是一条用来取n阶乘近似值的数学公式。一般来说，当n很大的时候，n阶乘的计算量十分大，所以斯特灵公式十分好用。从图中可以看出，即使在n很小的时候，斯特灵公式的取值已经十分准确。

公式为：   

 从图中看出，对于足够大的整数n，这两个数互为近似值。更加精确地：   

       或者        

这个公式，以及误差的估计，可以推导如下。我们不直接估计n!，而是考虑它的自然对数：

按一般方法计算N的阶乘，其时间复杂度为O（N）：    N！= 1 * 2 * 3 * 4 * 5 * ............ * N；

如果要计算N后得到的数字为几位数，则我们可以知道其位数等于lgN！+1；

则: 

但是当N很大的时候，我们可以通过斯特林公式进行优化：（即Stirling公式）

（e = 2.718）

斯特林公式可以用来估算某数的大小，结合lg可以估算某数的位数，或者可以估算某数的阶乘是另一个数的倍数。

例题：  http://acm.hdu.edu.cn/showproblem.php?pid=1018

题目给出的N的范围是: 1<= N <= 107  

用普通方法肯定算不出N的阶乘后的出的数字位数，但运用斯特林公式则很好解决.

Stirling 公式

即：

    Stirling公式的意义在于：当n足够大时，n!计算起来十分困难，虽然有很多关于n!的等式，但并不能很好地对阶乘结果进行估计，尤其是n很大之后，误差将会非常大。但利用Stirling公式可以将阶乘转化成幂函数，使得阶乘的结果得以更好的估计。而且n越大，估计得越准确。

利用Stirling公式求解n!的位数：易知整数n的位数为[lgn]+1。利用Stirling公式计算n!结果的位数时，可以两边取对数，得:

故n!的位数为：

斯特林公式是一条用来求n的阶乘的近似值的数学公式。一般来说，当n很大的时候，n阶乘的计算量十分大，所以斯特林公式十分好用，而且，即使在n很小的时候，斯特林公式的取值已经十分准确。

数学表达式：

或更精确的

或

作用：当N较大时计算N！的位数

易知整数n的位数为[lgn]+1,因此对Stirling公式两边取10的对数得

为此N！的位数为

C语言代码实现

//运用换底公式

res=(long long)((0.5*log(2*PI*n)+n*log(n)-n)/log(10))+1；

//注：C语言中函数log10()  log()分别是以10和e为底