■モンモールの問題の変形? (その1)

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

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

【1】モンモール数

 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

 これは,モンモール数f(n)がn−1で割り切れることを意味すると同時に,フィボナッチ数よりも急減に増加することを意味する.参考までに記しますが,

  p(n)≦p(n-1)+p(n-2)

が成り立つことより,分割数p(n)の増大速度はフィボナッチ数で上から抑えられることが示されます.したがって,黄金比φ=(√5+1)/2とおくと上界は

  p(n)<φ^n.

すなわち,モンモール数>フィボナッチ数>分割数

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

  pn=f(n)/n!

より,

  pn=pn-1−(pn-1−pn-1)/n

  pn−pn-1=−(pn-1−pn-1)/n

 また,

  n!=Σ(n,r)f(r)

  f(n)=Σ(−1)^(n-r)(n,r)r!

は二項変換の逆変換・反転表示の特別な形である.

  f(n)=[n!/e+m],1/3≦m≦1/2

  pn=1/n![n!/e+m],1/3≦m≦1/2

と表すことができる.

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