■スターリングの公式(その11)

 スターリングの公式の図形的近似式において,

  n!は直角三角錐

  n^nは立方体

と関係している部分である.すなわち,n^n/n!は1辺の長さnの立方体を切断した直角三角錐の体積になる.

 図形的証明に対して,スターリングの近似の組み合わせ論的証明も可能かもしれない.というのは,n^nは{1,2,3,・・・n}から{1,2,3,・・・n}へのinto写像,n!は{1,2,3,・・・n}から{1,2,3,・・・n}へのonto写像であるからだ.以下,クヌースのアイデアを補足しながら解説する.

===================================

【1】スターリングの近似の組み合わせ論的証明

 fが{1,2,3,・・・n}から{1,2,3,・・・n}へのランダムな写像である場合,数列1,f(1),f(f(1)),・・・内の相異なる値の個数の期待値は

  Q(n)=1+(n−1)/n+(n−1)/n・(n−2)/n+・・・で与えられる.

 実際,Q(n)という量は多くのアルゴリズム解析の際に現れる.そこで,Q(n)の漸近値を絶対誤差o(1)で求めてみよう.

 k≦n^1/2+eであれば,スターリング近似から,

  ln(n(n−1)(n−2)・・・(n−k+1)/n^k)=−k^2/2n+k/2n−k^3/6n^2+O(n^-1+4e)

したがって,

  n(n−1)(n−2)・・・(n−k+1)/n^k++++=exp(-k^2/2n)(1+k/2n−2k^3/3(2n)^2+O(n^-1+4e)

 ここで,テータ関数

  Θn=Σexp(−k^2/n)=・・・+exp(−9/n)+exp(−4/n)+exp(−1/n)+1+exp(−1/n)+exp(−4/n)+exp(−9/n)+・・・

に対して,tの周期関数

  Θn(t)=Σexp(−(k+t)^2/n)

のフーリエ級数展開は,ポアソンの和公式より

  Θn(t)=√πn(1+2exp(−π^2n)cos2πt+2exp(−4π^2n)cos4πt+2exp(−9π^2n)cos6πt+・・・)

 t=0とおけば

  Θn=Θn(0)=√πn+O(n^-m)

  Θn/√πn=1+2exp(−nπ^2)+O(−4nπ^2)

 この式と加え合わせて,k=0の項を消せば

  −1+Θ2n+Θ2n^(1)−2/3Θ2n^(3)+O(n^-1/2+4e)=√(πn/2)−1/3+O(n^-1/2+4e)

が得られる.

 すなわち,Q(n)の期待値は

  √(2πn)/2+O(1)

となることから,スターリング近似の係数√(2πn)の説明がつく.

===================================

【雑感】

 Stirlingの公式の大体の形は(n!/n^n+1/2・e(−n)がn→∞のときに一定の極限値をもつ)はいろいろな方法で導かれますが,その極限値を正しく√(2π)とするにはWallisの公式が不可欠のようで,これまでの証明はすべてWallisの公式(ないしそれと同等の結果)を活用しています.

 √(2π)を導くのにこのような方法があったとはちょっと意外(?)な感じですが,実はスターリングも求めることはできませんでした.何年か後でド・モアブルが定数の存在を証明した後でやっと求めることができたようです.

===================================