■モンモールの問題

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

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

【1】モンモール数

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

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

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

と表すことができる.

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

【2】包除原理

 2円または3円が交わったヴェン図を描いたことがあるだろう.2円の場合,共通部分がひとつできるが,3円の場合は2円の共通部分が3つ,3円の共通部分がひとつできる.

 中学・高校で4円以上が取り扱われることはまずないが,n円となっても原理は同じである.それは,共通部分に含まれるものを引いて,引き過ぎた分を足し直してということを繰り返す包除原理である.

 包除公式の例として,第2種スターリング数やデーン・サマービル関係式をあげることができるが,モンモール数も包除原理の例となっている.

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