モンモール数は規準となる並び順に対して，どの要素も本来のポジションにないような順列のことで，完全順列（撹乱順列）と呼ばれます．たとえば，｛５，１，２，３，４｝はどの数も元の場所に位置していないので完全順列，｛５，２，１，３，４｝は２の位置が固定されたままなので完全順列ではありません．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】包除原理

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

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

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

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】モンモール数

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

（ｎ，１）／ｎ−（ｎ，２）／ｎ（ｎ−１）＋（ｎ，３）／ｎ（ｎ−１）（ｎ−２）−・・・＋（ｎ，ｎ）／ｎ！

＝１−１／１！＋１／２！−・・・＋（−１）^n１／ｎ！

ｎ＝１３のとき

１−１／１！＋１／２！−・・・＋（−１）^n１／ｎ！＝０．３６７９

ｎ→∞のとき，

　　（１−１／ｎ）^n　→　１／ｅ＝０．３６７８・・・

に近づきます．

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

　　ｆ（ｎ）＝ｎ！Σ（−１）^k／ｋ！

また，漸化式

　　ｆ（ｎ）＝（ｎ−１）（ｆ（ｎ−１）＋ｆ（ｎ−２））

が成り立ちます．

ｎ　　ｆ（ｎ）

１　　　　０

２　　　　１

３　　　　２

４　　　　９

５　　　４４

６　　２６５

　これは，モンモール数ｆ（ｎ）がｎ−１で割り切れることを意味すると同時に，フィボナッチ数よりも急減に増加することを意味する．参考までに記しますが，

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

が成り立つことより，分割数ｐ（ｎ）の増大速度はフィボナッチ数で上から抑えられることが示されます．したがって，黄金比φ＝（√５＋１）／２とおくと上界は

　　p(n)<φ^n．

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

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　　ｐn＝ｆ（ｎ）／ｎ！

より，

　　ｐn＝ｐn-1−（ｐn-1−ｐn-1）／ｎ

　　ｐn−ｐn-1＝−（ｐn-1−ｐn-1）／ｎ

　また，

　　ｎ！＝Σ（ｎ，ｒ）ｆ（ｒ）

　　ｆ（ｎ）＝Σ（−１）^(n-r)（ｎ，ｒ）ｒ！

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

　　ｆ（ｎ）＝［ｎ！／ｅ＋ｍ］，１／３≦ｍ≦１／２

　　ｐn＝１／ｎ！［ｎ！／ｅ＋ｍ］，１／３≦ｍ≦１／２

と表すことができる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝