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