憂しと見し世ぞ今は恋しき

モンモール数

モンモール数って?

完全順とか、攪乱(かくらん)順列とか呼ばれる並べ方の場合の数の総数をモンモール数といいます。
知りませんがきっとモンモールさんが発見したんでしょう。

0,1,2,9,44,265,1854・・・以降は一般項の公式で出してください。
1854については「日米和親条約がモンモール数」って覚えています。

完全順列(攪乱順列)って?

1,2,3・・・という要素を持つ順列を作ったときに、1番目に1、2番目に2・・・のようにn番目にnが来ないようになる並べ方が完全順列です。
たとえば、要素1,2,3,4を並べる場合ですと並べ方は4!=24通りありますが、そのうち完全順列となるのは右表の9個になりますね。

2 1 4 3
2 3 4 1
2 4 1 3
3 1 4 2
3 4 1 2
3 4 2 1
4 1 2 3
4 3 1 2
4 3 2 1

これがモンモール数の4個目が9ってことです。
これくらいなら先頭を2で固定して3通りだから、3の場合と4の場合で×3して9通りってのが樹形図と計算ですぐに出ます。

モンモール数を使う問題の具体例

このモンモール数ですが、大学受験の数学だけでなく、中学受験の算数でもたまに見かけます。
四谷大塚の小6夏期講習テキストにもぶっこまれていますね。
どんな問題で使うかというと、「カラーボールと箱」とか「プレゼント交換」とか「専用個室」なんかをテーマにした問題で効力を発揮します。

カラーボールと完全順列の例題

赤、青、黄、緑の4つのボールと、同じ4色の4つの箱があります。1つの箱にボールを1つずつ入れていくとき、ボールの色と箱の色が全て異なるような入れ方は何通りですか

モンモール数を知らなくても、先ほどやったように赤箱に青球を入れて、残り3箱で3通り・・・から解けばものの1分で解けますがね。
当然、答えは9通りです。

プレゼント交換と完全順列の例題

A、B、C、D、Eの5人がそれぞれプレゼントを持ち寄ってプレゼント交換をしました。5人とも自分の手元に自分が持ってきたプレゼントが戻ってこないような交換のしかたは何通りですか

これも完全順列ですね。
AにBのプレゼント、BにAのプレゼントで残り3人が2通り(DEC、ECD)、AにB、BにCで残り3人が3通り(BED、EBD、DEB)でBにDの場合、Eの場合も同様ですから2+3×3=11通り。
AにC、D、Eの場合も同様にして11×4=44通りと計算できます。

専用個室と完全順列の例題(2013年武蔵中)

5匹のやぎA、B、C、D、Eがいて、図のようなそれぞれのための小屋があります。あるとき、5つの小屋にやぎが1匹ずつ入っていましたが、自分の小屋にいたのは5匹のうち1匹だけでした。 5匹のやぎの、このような小屋への入り方は全部で何通りですか

武蔵中は敷地内でやぎを飼っているので、入試にやぎが登場してくることが多いです。
それはともかく、これも完全順列で処理できます。
やぎAが小屋Aに入っていたとして、残り4匹の完全順列が9通り、これをやぎBが小屋B、やぎCが・・・として×5ですから45通りになりますね。

モンモール数の一般項

このモンモール数ですが、上の例題でやったように要素5つくらいなら手計算でも問題ないですが、6つを超えてくると厳しくなります。
そんなのが中学受験で出題されることはないでしょうが。

一応、一般項としてn番目のモンモール数について

という計算で求められます。

n=5でしたら です。

この計算、n→∞でネイピア数eの逆数になります。
およそ1/2.712・・・=0.367・・・で37%くらいでしょうか。

どういうことかというと、要素の数が増えても完全順列のできる確率は増えないってことですね。
2人のときは1/2=50%、3人のときは2/9=22.2%、4人で9/24=37.5%、5人で44/120=36.7%ですからもう収束してます。
プレゼント交換なんて、人数が増えれば自分のプレゼントが戻ってくる人がいる確率なんて増えそうな気がしますけどね。