■お見合い問題(その4)

 お見合問題と似た問題に,モンモールの問題がある.

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

 モンモール数は規準となる並び順に対して,どの要素も本来のポジションにないような順列のことで,完全順列(撹乱順列)と呼ばれます.たとえば,{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・・・

に近づきます.

 誤差項Rは

  R≦1/(n+1)!

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

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

また,漸化式

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

が成り立ちます.f(0)=0,f(1)から始めてこれらの数を計算すると・・・

n  f(n)

1    0

2    1

3    2

4    9

5   44

6  265

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