完全順列(攪乱順列 ; モンモールの問題)の漸化式

スポンサーリンク

本項目は発展的な内容です。

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