スターリングの公式

　　ｎ！　〜　√（２πｎ）（ｎ／ｅ）^n

は面白い公式で，

　　ｎ！／ｎ^n　〜　√（２πｎ）／ｅ^n

　　１／ｎ・２／ｎ・・・（ｎ−１）／ｎ・ｎ／ｎ　〜　√（２πｎ）／ｅ^n

として，全体のｎ乗根をとればｋ／ｎの相乗平均が大まかに１／ｅに近いことを示している．

　図形的証明に対して，スターリングの近似の組み合わせ論的証明も可能かもしれない．というのは，ｎ^nは｛１，２，３，・・・ｎ｝から｛１，２，３，・・・ｎ｝へのinto写像，ｎ！は｛１，２，３，・・・ｎ｝から｛１，２，３，・・・ｎ｝へのonto写像であるからだ．以下，クヌースのアイデアを補足しながら解説する．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

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

　ｆが｛１，２，３，・・・ｎ｝から｛１，２，３，・・・ｎ｝へのランダムな写像である場合，数列１，ｆ（１），ｆ（ｆ（１）），・・・内の相異なる値の個数の期待値は

　　Ｑ（ｎ）＝１＋（ｎ−１）／ｎ＋（ｎ−１）／ｎ・（ｎ−２）／ｎ＋・・・で与えられる．

　実際，Ｑ（ｎ）という量は多くのアルゴリズム解析の際に現れる．そこで，Ｑ（ｎ）の漸近値を絶対誤差ｏ（１）で求めてみよう．

　ｋ≦ｎ^1/2+eであれば，スターリング近似から，

　　ｌｎ（ｎ（ｎ−１）（ｎ−２）・・・（ｎ−ｋ＋１）／ｎ^k）＝−ｋ^2／２ｎ＋ｋ／２ｎ−ｋ^3／６ｎ^2＋Ｏ（ｎ^-1+4e）

したがって，

　　ｎ（ｎ−１）（ｎ−２）・・・（ｎ−ｋ＋１）／ｎ^k＋＋＋＋＝ｅｘｐ（-k^2/2n）（１＋ｋ／２ｎ−２ｋ^3／３（２ｎ）^2＋Ｏ（ｎ^-1+4e）

　ここで，テータ関数

　　Θn＝Σｅｘｐ（−ｋ^2／ｎ）＝・・・＋ｅｘｐ（−９／ｎ）＋ｅｘｐ（−４／ｎ）＋ｅｘｐ（−１／ｎ）＋１＋ｅｘｐ（−１／ｎ）＋ｅｘｐ（−４／ｎ）＋ｅｘｐ（−９／ｎ）＋・・・

に対して，ｔの周期関数

　　Θn（ｔ）＝Σｅｘｐ（−（ｋ＋ｔ）^2／ｎ）

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

　　Θn（ｔ）＝√πｎ（１＋２ｅｘｐ（−π^2ｎ）ｃｏｓ２πｔ＋２ｅｘｐ（−４π^2ｎ）ｃｏｓ４πｔ＋２ｅｘｐ（−９π^2ｎ）ｃｏｓ６πｔ＋・・・）

　ｔ＝０とおけば

　　Θn＝Θn（０）＝√πｎ＋Ｏ（ｎ^-m）

　　Θn／√πｎ＝１＋２ｅｘｐ（−ｎπ^2）＋Ｏ（−４ｎπ^2）

　この式と加え合わせて，ｋ＝０の項を消せば

　　−１＋Θ2n＋Θ2n^(1)−２／３Θ2n^(3)＋Ｏ（ｎ^-1/2+4e）＝√（πｎ／２）−１／３＋Ｏ（ｎ^-1/2+4e）

が得られる．

　すなわち，Ｑ（ｎ）の期待値は

　　√（２πｎ）／２＋Ｏ（１）

となることから，スターリング近似の係数√（２πｎ）の説明がつく．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【雑感】

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

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

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝