■漸化式と母関数(その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!

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