n$人がプレゼント交換するとき,\ 誰も自分のプレゼントをもらわない(プレゼント交換
に成功する)場合の総数を$M_n$とする.
(1)\ \ $M_1,\ \ M_2,\ \ M_3,\ \ M_4\,を求めよ.$
(2)\ \ $M_n=(n-1)(M_{n-1}+M_{n-2})\ \ (n≧3)\ を示せ(上級者用).$ \\
完全順列（攪乱順列）
4人のプレゼント交換の場合の数は $4!=24\ (通り)$
[1]\ \ 4人全員が自分のプレゼントをもらう}とき その場合の数は\ 1通り
[2]\ \ ちょうど3人が自分のプレゼントをもらう}とき その場合の数は\ 0通り
[3]\ \ ちょうど2人が自分のプレゼントをもらう}とき
自分のプレゼントをもらう2人の選び方は $C42=6$通り
残りの2人がプレゼント交換に成功する方法は 1通り
ちょうど2人が自分のプレゼントをもらう場合の数は $6×1=6\ (通り)$
[4]\ \ 1人だけが自分のプレゼントをもらう}とき
自分のプレゼントをもらう1人の選び方は $C41=4$通り
残りの3人がプレゼント交換に成功する方法は 2通り
1人だけが自分のプレゼントをもらう場合の数は $4×2=8\ (通り)$
をすべて満たすように並べる順列の総数}を求める.
このような順列を完全順列}または攪乱(かくらん)順列}という.
また,\ 数学者モンモールに由来し,\ モンモール問題}とも呼ばれる.
M_n\,をモンモール数}といい,\ M_1\,から順に書き出すと0,\ 1,\ 2,\ 9,\ 44,\ 265,\ ･･･\ となる.
大学受験での出題はせいぜいM_5=44までなので,\ 表や樹形図}ですべて書き出せばよい.
「お(0)い(1)！肉(2,9)！よし(44)！」などと適当なゴロ合わせで覚えておくといいかも？
総数からプレゼント交換に失敗する場合の数を引く}別解(M_4\,のみ)も示した(補集合の利用}).
プレゼント交換に失敗する場合の数は,\ 何人が自分のプレゼントをもらうかで場合分け}すると求まる.
[3],\ [4]\ \ 2人,\ 3人がプレゼント交換に成功する場合の総数はそれぞれM_2,\ M_3\,のことである.
[1],\ [2]}\ \ よって,\ 本解のように書き出して考えるとそれぞれ1通り,\ 2通りである.
,以外のn-2人がプレゼント交換に成功する}場合の数は M_{n-2}\ 通り$
M_n\,を一般的に求めるには,\ 漸化式の作成}(数 B:数列)が有効である.
ただし,\ 作り方が特殊なのでパターン認識がなければ難しい.
例としてM_5\,を考える.\ \ \emKaku{1}\,は②,\ ③,\ ④,\ ⑤をもらえるが,\ 対等性より各場合の数は等しい.
よって,\ \emKaku{1}\,が②をもらうときの場合の数を4倍すればよい.
さて,\ \emKaku{1}\,が②をもらうパターンは以下の2つがあり,\ 互いに排反}である.
「}\,\emKaku{2\,が①をもらう」「}\,\emKaku{2\,が①以外をもらう」} (\,\emKaku1\,と\,\emKaku2\,が互いに交換し合うか否か)
しかし,\ 実は完全順列か否かにおいて番号が一致しているか否かは関係ない.}
完全順列の条件の本質は,\ 「どの人ももらわないプレゼントがただ1個ずつある」}ことである.
つまり,\ 例えば\ \emKaku{1}≠③,\ \emKaku{2}≠②,\ \emKaku{3}≠①\ のような場合でもM_3=2\,通りとなる.
簡単には納得いかないかもしれないが,\ (1)の本解のように実際に書き出してみるとわかりやすい.
\emKaku{1}\,が②をもらう2つの場合は排反}なので,\ 和の法則によりその総数は(M_3+M_4)通りとなる.
\emKaku{1}\,は②,\ ③,\ ④,\ ⑤をもらう可能性があるから,\ M_5=4(M_3+M_4)\ となる.
以上を文字nを用いて一般化したものが(2)の漸化式である.
意欲的な学生のために,\ 漸化式を解いて$M_n}$の一般化公式を得る過程を示しておく.
以下を理解するには数Bの数列にかなり習熟している必要がある.
$M_n=(n-1)(M_{n-1}+M_{n-2}),\ \ M_1=0,\ \ M_2=1$
$M_n-nM_{n-1}=-\,\{M_{n-1}-(n-1)M_{n-2}\}$と変形できるから,\ これを繰り返し適用する.
$M_n-nM_{n-1}=-\,\{M_{n-1}-(n-1)M_{n-2}\}=(-\,1)^2\{M_{n-2}-(n-2)M_{n-3}\}$
(-\,1)^n$の両辺を$n!$で割ると
(階差数列型漸化式)} {4!}=4･3-4+1=9$ [\,展開してから計算すると楽}\,]} 人のプレゼント交換が成功する確率$P_n}$とその極限(数III)を求めてみる. \
ここで,\ マクローリン展開(大学1年)によりinfty}P_n=1e≒0.37$ [\,自然対数の底$e$の近似値は\ $e≒2.71$\,]}
$P_n$は非常に収束が速く,\ $n=5$の時点でほぼ0.37に収束する.
つまり,\ 5人でも1万人でも,\ プレゼント交換が成功する確率は約37％になるのである.
逆に言えば,\ 少なくとも1人が自分のプレゼントをもらってしまう確率は約63％である.
以下の2つは同じことである.\ \ ①の漸化式は,\ 後者の扱いで解いている.
M_n\,の公式は,\ 漸化式の作成以外に包除原理}を利用して得る方法が知られている.\ 概要を示す.
包除原理(包含と排除の原理)とは,\ 次の個数定理を一般化したものである.
n(A∪ B∪ C)=n(A)+n(B)+n(C)-n(A∩ B)-n(B∩ C)-n(C∩ A)+n(A∩ B∩ C)
4個以上の集合に対しても同様の法則が成り立つ.
n(A∪ B∪ C∪ D)=n(A)+n(B)+n(C)+n(D)
n(A∪ B∪ C∪ D)} \ \ -\,n(A∩ B)-n(A∩ C)-n(A∩ D)-n(B∩ C)-n(B∩ D)-n(C∩ D)
n(A∪ B∪ C∪ D)} \ \ +\,n(A∩ B∩ C)+n(A∩ B∩ D)+n(A∩ C∩ D)+n(B∩ C∩ D)
n(A∪ B∪ C∪ D)} \ \ -\,n(A∩ B∩ C∩ D)
全体集合をU,\ \emKaku1=①となる順列の集合をA,\ \emKaku2=②となる順列の集合をB,\ ･･････\ とする.
M_4=n(U)-n(A∪ B∪ C∪ D) [\,(全体)-(少なくとも1人が自分のプレゼントをもらう)\,]
\emKaku1=①かつ\,\emKaku2=②となる順列の集合A∩ Bの要素は,\ ③,\ ④の並べ方に帰着するから2!\,個ある.
同様に,\ A∩ C,\ A∩ D,\ B∩ C,\ B∩ D,\ C∩ Dの要素の個数もそれぞれ2!\,個ずつある.
A,\ B,\ C,\ Dの4つから2つの集合を選ぶ方法は\,C42\,通りあるから,\ C42･2!\,を引くことになる.
