$ 1 $ から $ n $ までの番号のついたカード $ n $ 枚を無作為に並べる.すべての $ k\ (1\leqq k \leqq n) $ について,
$ k $ 番目にあるカードの番号が $ k $ではないような順列を完全順列という.
完全数列の総数をモンモール数という.
なお完全順列とならない順列をめぐりあいの順列とも言う.それが表題の意味である.
これは,
2004年東工大後期,
2007年名古屋市大,
2014年大阪医大などに出題されている.
モンモール数を求める方法は,2004年東工大後期の解答のなかに2通り,本問の解答のなかに2通り,一つは基本的に同じなので,あわせて3通りが示されている.
同様に考えることのできる問題をあわせてここに紹介する.
【問題甲】 $ 1 $ から $ n $ までの番号のついたカード $ n $ 枚を勝手に並べるとき,少なくとも一枚 $ k $ 番目に番号 $ k $ のカードのある確率を求めよ.
【問題乙】 $ 1 $ から $ n $ までの番号のついた赤球と白球,あわせて $ 2n $ 個を円周上に並べる. 赤球と白球が隣りあうことはないという条件の下で,同じ番号の赤球と白球が隣りあうことのない場合の数を $ C(n) $ , 少なくとも一組同じ番号の赤球と白球が隣りあう場合の数 $ f(n) $ とする. $ C(n) $の漸化式,および $ f(n) $ の明示式を求めよ.
【問題丙】 $ m $台の客車で編成された列車がある.
$ n $人の乗客がそれぞれいずれかの列車にる.
各々の客車に少なくとも1人は乗るような乗り方の総数を $ a_m(n) $ とする.
$ a_m(n) $ はその定義から $ m=n $ のとき $ a_m(n)=n! $ , $ m>n $ のとき $ a_m(n)=0 $ であるが,
一方 $ m< n $ のときを含めて
\[
a_m(n)
=\sum_{k=1}^{m}{}_m \mathrm{C}_k(-1)^{m-k}k^n
\]
となることを示せ.
$ k $ 番の乗客が $ f(k) $ が番の列車に乗るとすると,
$ f $ は,個数 $ n $の有限集合から個数 $ m $ の有限集合への写像であり,
いずれかの列車に乗るということは $ f $ が全射であるということである.
したがって, $ a_m(n) $ はまた,個数 $ n $ の有限集合から個数 $ m $ の有限集合への全射の総数でもある.