完全順列
モンモール数 anを与える母関数は以下のようになる。
∑ n = 0 ∞ a n x n = e − ( 1 + 1 x ) x E i ( 1 + 1 x ) = 1 + x 2 + 2 x 3 + 9 x 4 + 44 x 5 + 265 x 6 + ⋯ {\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }a_{n}x^{n}&={\frac {e^{-\left(1+{\frac {1}{x}}\right)}}{x}}\mathrm {Ei} \left(1+{\frac {1}{x}}\right)\\&=1+x^{2}+2x^{3}+9x^{4}+44x^{5}+265x^{6}+\cdots \end{aligned}}}
ここで、Ei は指数積分である。また、指数型母関数は以下のようになる。
例えば 5 人でプレゼントを持ち寄ってランダムに分け直したとき、誰かが自分の持ってきたプレゼントに当たってしまう確率 p5 は
p 5 = 5 ! − 44 5 ! = 76 120 = 19 30 = 0.6333 ⋯ {\displaystyle p_{5}={\dfrac {5!-44}{5!}}={\dfrac {76}{120}}={\dfrac {19}{30}}=0.6333\cdots } となる。
人数が 10 人の場合の確率 p10 は
p 10 = 10 ! − 1334961 10 ! = 2293839 3628800 = 0.63212053571428571428571428571429 ⋯ {\displaystyle p_{10}={\dfrac {10!-1334961}{10!}}={\dfrac {2293839}{3628800}}=0.63212053571428571428571428571429\cdots } となる。
人数が n 人の場合の確率 pn の極限は
lim n → ∞ p n = 1 − 1 e = 0.63212055882855767840447622983854 ⋯ {\displaystyle \lim _{n\to \infty }p_{n}=1-{\frac {1}{e}}=0.63212055882855767840447622983854\cdots } となる。
上記の式におけるの n 人のときの分子の数 (n! - an) はオンライン整数列大辞典の数列 A002467を参照。
完全順列(かんぜんじゅんれつ、英: complete permutations)、もしくは攪乱順列(かくらんじゅんれつ、英: derangement)とは、整数 1, 2, 3, ..., n を要素とする順列において、i 番目 (i ≦ n) が i でない順列である。順列を置換とみると、完全順列は不動点の個数が 0 の置換に対応している。乱列、混乱順列ともいう。
包除原理を用いてもモンモール数の一般項を求めることができる。1 ≦ k ≦ n を満たす自然数 k に対して、集合 A k {\displaystyle A_{k}} を n 個の数字 {1, 2, ..., n} を自分自身に写す置換の中で、k 番目の数字を固定する(すなわち、k を k に写した)順列の集合とする。i 個の集合の共通部分は i 個の数字を固定する置換を施した順列になるので、その元の個数は ( n − i ) ! {\displaystyle (n-i)!} に等しくなる。このとき、共通部分の選び方は n C i = ( n i ) {\displaystyle _{n}\mathrm {C} _{i}={\tbinom {n}{i}}} 通りになるので、包除原理により以下の式が成り立つ。
| A 1 ∪ ⋯ ∪ A n | = ∑ i | A i | − ∑ i < j | A i ∩ A j | + ∑ i < j < k | A i ∩ A j ∩ A k | + ⋯ + ( − 1 ) n + 1 | A 1 ∩ ⋯ ∩ A n | = ( n 1 ) ( n − 1 ) ! − ( n 2 ) ( n − 2 ) ! + ( n 3 ) ( n − 3 ) ! − ⋯ + ( − 1 ) n + 1 ( n n ) 0 ! = ∑ i = 1 n ( − 1 ) i + 1 ( n i ) ( n − i ) ! = n ! ∑ i = 1 n ( − 1 ) i + 1 i !