Stirling近似公式

组合计数的渐进值问题是组合论的一个研究方向。

Stirling公式给出一个求n!的近似公式,它对从事计算和理论分析都是有意义的。

原文转载自http://www.ekany.com/wdg98/zhsx/1/1_3.htm


1)Wallis公式

,显然,

I1=1.k≥2时,

Ik

  =(k-1)(Ik-2-Ik)

(1-3-1)

由(1-3-1), (1-3-2)

当x∈(0,π/2)时, sink+1x<sinkx 因而I2k+1<I2k<I2k-1, k=1,2,…。

由(1-3-2), ,

所以,

(1-10-3)

2)stirling公式

(1-3-4)

(1-3-5)

tn的几何意义是由x轴,x=n,以及连接(1,0), (2,ln2),…,(n-1,ln(n-1)),(n,lnn)诸点而成的折线围成的面积。

Tn=1/8+ln2+…+ln(n-1)+(lnn)/2 (1-3-6)

Tn是由三部分面积之和构成的。一是曲线y=lnx在x=k点的切线和x轴,以及x=k-1/2,x=k-1/2包围的梯形,当k分别为2,3,…,n-1时的面积之和;一是由y=lnx在x=1点的切线,x=3/2线,以及x轴围城的梯形;另一是由y=lnn,x=n-1/2,x=n及x轴包围的矩形面积。因而有tn<An<Tn (1-3-7)

0<An-tn<Tn-tn=1/8

bn=An-tn.序列b1,b2,…是单调增,而且有上界,故有极限,

bn=b1 由(1-3-4),(1-3-5)
得 bn=nlnn-n+1-ln(n!)+(lnn)/2=lnnn-n+1-ln(n!)+(ln)/2

ln(n!)=1-bn+lnnn-ln-lnen
∴n!= (1-3-8)

βn= ,βn=β.
将(1-3-8)代入(1-3-3),整理得 β=.

所以 n! ~


这个公式在PKU 1423:Big Number中得到了很好的应用。

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: