■漸化式と母関数(その24)
n個の要素に対する完全順列の数をモンモール数と呼びます.一般項は
f(n)=n!Σ(−1)^k/k!
また,漸化式
f(n)=(n−1)(f(n−1)+f(n−2)),n≧2
f(n+1)=n{f(n)+f(n−1)),n≧1
が成り立ちます.
通常型母関数
f(x)=Σanx^n,n≧0
指数型母関数
f(x)=Σanx^n/n!,n≧0
が用いられるが,ここでは完全順列数{f(n)}の指数型母関数D(x)を求めてみたい.
f’(x)=Σanx^n-1/(n−1)!,n≧1
f’(x)=Σan+1x^n/n!,n≧0
===================================
f(n+1)=n{f(n)+f(n−1)),n≧1
f(n+1)x^n=nf(n)x^n+nxf(n−1)x^n-1),n≧1
f(n+1)x^n/n!=xf(n)x^n-1/(n−1)!+xf(n−1)x^n-1/(n−1)!,n≧1
D’(x)=xD’(x)+xD(x)
(1−x)D’(x)=xD(x)
D(x)=(1−x)exp(−x)
→f(n)=n!Σ(−1)^k/k!
===================================