はしりがき

「組み合わせ数学入門I」（C・L・リウ著、伊里正夫、伊里由美共訳、共立全書（共立出版））
「数え上げ組み合わせ論入門」（成嶋弘著、日評数学選書（日本評論社））
から使えそうな公式を抽出。

■スターリングの近似公式

n! ≒ √(2πn) * (n/e)^n

π：円周率 e：ネピアの数/自然対数の底

絶対誤差(差)はnの増大とともに増大するが、相対誤差(商)は単調減少するとのこと。確率では相対誤差のみが問題となるから、十分良い近似が得られる。
ちなみにn=40を放り込むと8.14217264 * 10⁴⁷。これで40! = 8.15915283 * 10⁴⁷を割ると1.00208546となる。
Wikipedia丸写しだけど、1+1/(12n)+1/(288n²)-139/(51840n³)を掛けてやることでさらに精度が上がるっぽい。計算すると8.15915283*10⁴⁷だから信頼できそうか。

■母関数
勉強中

■第2種スターリング数
集合A(|A| = n)を{ B_i | ∨_i=1^kB_i = A, B_i∧B_j = ø (i ≠ j) }に分割したとき、分割パターン数は_nS_kで表され、次のような式(漸化式と一般公式)を得る。

nSk = 1	(k = 1,n)
nSk = n-1Sk-1 + k * n-1Sk	(2 ≤ k ≤n-1)
nSk = ∑i=0k(-1)i * (k-i)n / { i! * (k-i)! }

実際に使うのはB(n) = ∑_k=1ⁿ_nS_kaのように総和をとったものだが、これについても次の漸化式

B(n+1) = ∑k=0nnCk* B(k)

が成立するみたい。一般式は分からなくても、プログラミングの都合上は漸化式で十分なんだよなー。