検索用コード
$n$人がプレゼント交換するとき,\ 誰も自分のプレゼントをもらわない場 \\[.2zh] \hspace{.5zw}合の総数を$M(n)$とする. \\[1zh] \hspace{.5zw} (1)\ \ $M(1),\ \ M(2),\ \ M(3),\ \ M(4)を求めよ.$ \\[.5zh] \hspace{.5zw} (2)\ \ $M(n)=(n-1)\{M(n-1)+M(n-2)\}\ \ (n\geqq3)\ を示せ.$ \\ $n$人に$1,\ 2,\ 3,\ \cdots,\ n$\,という番号を付ける. \\[.2zh] \phantom{ (1)}\ \ また,\ それぞれの人のプレゼントを$\maru1,\ \maru2,\ \maru3,\ \cdots\,\ \maru n\,$とする. \\[.2zh] \phantom{ (1)}\ \ $このとき,\ kと\maru kが対応しないような場合の数を求めればよい.$ \\\\ 1が\maru i\ (2\leqq i\leqq n)\ をもらう}ときを考える.$ \\[1zh] \phantom{ (1)}\ \ (\hspace{.13zw}i\hspace{.13zw})\ \ $\textcolor[named]{ForestGreen}{iが\maru1をもらう}とき$    {\normalsize $[\textcolor{brown}{1とiが相互に対応する}]$} \\[.5zh] \phantom{ (1)}\ \ \phantom{(ii)}\ \ $\textcolor{red}{1とi以外のn-2人が自分のプレゼントをもらわなければよい.}$ \\[.2zh] \phantom{ (1)}\ \ \phantom{(ii)}\ \ $よって M(n-2)\ (通り)$ \\[1zh] \phantom{ (1)}\ \ (ii)\ \ $\textcolor[named]{ForestGreen}{iが\maru1以外をもらう}とき$  {\normalsize $[\textcolor{brown}{1とiが相互に対応しない}]$} \\[.5zh] \phantom{ (1)}\ \ \phantom{(ii)}\ \ $\textcolor{cyan}{「iが\maru1以外」を「iが\maru i以外」とみなす.}$ \\[.2zh] \phantom{ (1)}\ \ \phantom{(ii)}\ \ \scalebox{0.98}[1]{$すると,\ \textcolor{red}{n-1人が自分のプレゼントをもらわない場合に帰着}する.$} \\[.2zh] \phantom{ (1)}\ \ \phantom{(ii)}\ \ $よって M(n-1)\ (通り)$ \\[1zh] \phantom{ (1)}\ \ ここで,\ 1がどのプレゼントをもらうかは$n-1$通りある. M(n)=(n-1)\{M(n-1)+M(n-2)を全て満たすように並べる順列の総数}を求める. \\ このような順列を\bm{完全順列や攪乱(かくらん)順列}という. \\ また,\ 数学者モンモールに由来し,\ \bm{モンモール問題}とも呼ばれる. \\ M(n)を\bm{モンモール数}といい,\ 順に書き出すと,\ 0,\ 1,\ 2,\ 9,\ 44,\ 265,\ \cdots\ となる. \\ 完全順列は,\ 一般的に考えるのは非常に難しい. →\ (2) \\ 通常の出題はせいぜいM(5)=44までなので,\ \bm{表や樹形図}で書き出せばよい. \\ 「おい!肉!よし!」などと適当なゴロ合わせで覚えておくといいかも? \\[1zh] 一般的には,\ (2)のような\bm{漸化式}を作成することになる. \\ 作り方を暗記していない場合,\ 1から作り出すのは常人には無理だろう. \\[1zh] 具体例として,\ M(5)を,\ \bm{2段階の場合分け}をして考える. \\ 1は\maru2,\ \maru3,\ \maru4,\ \maru5をもらえるが,\ 対等性より,\ どの場合の総数も等しい. \\ よって,\ とりあえず\bm{1が\maru2をもらうとき(1→\maru2)}を考え,\ 後で4倍する. \\[1zh] さて,\ ここからが本題で,\ さらに次の2つの場合に分ける.\ この2つは\bm{排反}である. \\ \bm{「2が\maru1をもらう」「2が\maru1以外をもらう」} \bm{(1と相互に対応するか否か)} \\[1zh] 2が\maru1をもらうとき,\ 1→\maru2,\ 2→\maru1\ と\bm{相互に対応}する.  このとき,\ 3\neqq\maru3,\ 4\neqq\maru4,\ 5\neqq\maru5\ が要求される. \\ これは\bm{n=3の完全順列}と考えられ,\ その総数はM(3)通りである. \\[1zh] 2が\maru1以外をもらう(2\neqq\maru1)場合を考える.\    例として,\ 2が\maru3をもらうとする. \\ 残りの3,\ 4,\ 5は\maru1,\ \maru4,\ \maru5との対応になるが,\ これはM(3)通りではない. \\ 4\neqq\maru4,\ 5\neqq\maru5が要求される一方,\ 3=\maru1は可能だからである. \\ よって,\ これは完全順列とはいえず,\ M(3)通りとすることはできないのである. \\[1zh] そこで,\ 非常に巧妙な考え方を導入する.        さらに,\ 場合分けの条件より,\ \bm{2\neqq\maru1}\ であることも要求されている. \\ ここで,\ \bm{\maru1を\maru2とみなす}(←うまい!)と,\ \bm{2\neqq\maru2}\ となる. \\ これは\bm{n=4の完全順列}に他ならず,\ その総数はM(4)通りである. \\[1zh] 2つの場合は\bm{排反}であるから,\ 和の法則により,\ \{M(3)+M(4)\}通りとなる. \\ 1が何をもらうかの4通りも考慮すると,\ M(5)=4\{M(3)+M(4)\}\ となる. \\ 以上を文字nを用いて一般化したものが(2)の漸化式である. \\[1zh] 勝手に\maru1を\maru2とみなすことを不可解に感じるかもしれない. \\ 完全順列は,\ ラベルや番号が一致するか否かが重要なわけではない. \\ \bm{「各要素に対応させてはいけないものがただ1つずつある」}条件が本質である. \\ 2\neqq\maru1,\ 3\neqq\maru3,\ 4\neqq\maru4,\ 5\neqq\maru5\ の条件で並べるのであるから,\ M(4)通りである.