■いろいろの漸化式と母関数(その11)

 完全順列の数を与える一般公式は,

  F(q)=q!Σ(−1)^k/k!

 5通の手紙と宛名の書かれた5枚の封筒があったとする.どの手紙も正しい封筒に入らないのは何通りあるかという場合の数がF(5)である.

F(5)=5!(1−1/1!+1/2!−1/3!+1/4!−1/5!)

=120(1−1+1/2−1/6+1/24−1/120)

=120−120+60−20+5−1=44

F(4)=4!(1−1/1!+1/2!−1/3!+1/4!)

=24(1−1+1/2−1/6+1/24

=24−24+12−4+1=9

F(3)=3!(1−1/1!+1/2!−1/3!)

=6(1−1+1/2−1/6)

=6−6+3−1=2

F(2)=2!(1−1/1!+1/2!)

=2(1−1+1/2)

=2−2+1=1

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

[1]モンモールの問題

 モンモール数は規準となる並び順に対して,どの要素も本来のポジションにないような順列のことで,完全順列(撹乱順列)と呼ばれます.たとえば,{5,1,2,3,4}はどの数も元の場所に位置していないので完全順列,{5,2,1,3,4}は2の位置が固定されたままなので完全順列ではありません.

 n個の宛名を書いた封筒にn個の手紙を無作為に入れるとき,すべての手紙がその宛名と違う封筒に入る確率は,包除原理より,

(n,1)/n−(n,2)/n(n−1)+(n,3)/n(n−1)(n−2)−・・・+(n,n)/n!

=1−1/1!+1/2!−・・・+(−1)^n1/n!

n=13のとき

1−1/1!+1/2!−・・・+(−1)^n1/n!=0.3679

n→∞のとき,

  (1−1/n)^n → 1/e=0.3678・・・

に近づきます.

 n個の要素に対する完全順列の数をモンモール数と呼びます.一般項は

  f(n)=n!Σ(−1)^k/k!

また,漸化式

  f(n)=(n−1)(f(n−1)+f(n−2))

が成り立ちます.

n  f(n)

1    0

2    1

3    2

4    9

5   44

6  265

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