No.376 - 高校数学で理解するマッチング問題 [科学]
\(\newcommand{\bs}[1]{\boldsymbol{#1}} \newcommand{\mr}[1]{\mathrm{#1}} \newcommand{\br}[1]{\textbf{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\sb}{\subset} \newcommand{\sp}{\supset} \newcommand{\al}{\alpha} \newcommand{\sg}{\sigma}\newcommand{\cd}{\cdots}\)
今まで「高校数学で理解する ･･････」というタイトルの記事をいくつか書きましたが、その続きです。過去の記事は、
の、総計 17 の記事です。分類すると、
となります。今回の "マッチング問題" は「③ 直感に反する確率」のジャンルに属するものです。
なお、"高校数学で理解する" というタイトルは、「高校までで習う数学だけを前提知識とする（それ以外は全部証明する）」という意味です。もちろん、"おおよそ高校までの数学" が正しく、正式には大学で習う数学を証明なしで使ったことがあります。たとえば、No.325「高校数学で理解する誕生日のパラドックス」での "マクローリン展開（テイラー展開）" ですが、今回もそれを使います。
席替えの成功確率
小学校で 40人のクラスがあるとします。このクラスには約 90%の確率で誕生日が同じ子がいる（正確には 89.12%）というのが No.325「高校数学で理解する誕生日のパラドックス」でしたが、今回は席替えの問題です。
40人のクラスで、席替えを "くじ引き" でやるとします。まず、現在の席に 1 ～ 40 の席番号を割り振ります。担任の先生は、1 ～ 40 の数字を書いた紙を 40枚用意し、その紙を数字が見えないように折って、箱の中に入れてかき混ぜます。生徒は席番号１の子から順に箱から紙を１枚ずつ引き、そこに書かれている数字がその子の新しい席となります。もちろんこのやり方だと、今の自分の席番号の紙を引く子が現れる可能性があります。現在の席番号以外の番号を引けば、その子は "成功" と定義します。
そして「すべての子が成功したら、クラスの席替えは成功」と定義します。つまり「すべての子が現在の席番号と違う番号を引いたとき、席替えは成功」です。では、40人のクラスで席替えが成功する確率はどれほどでしょうか。これが問題です。
40人だと考えづらいので、極端ですが、クラスの人数が 3人の場合で考えてみます。席１、席２、席３の子が引いた数字を順に３つの数字の組で表すと、考えられる組み合わせは、
（1, 2, 3）
（1, 3, 2）
（2, 1, 3）
（2, 3, 1）◎
（3, 1, 2）◎
（3, 2, 1）
の６通り（=3!）です。このうち "席替え成功" となるのは ◎印をつけた、
（2, 3, 1）
（3, 1, 2）
の２通りだけなので、
席替えの成功確率\(=\dfrac{2}{6}\fallingdotseq0.33\)
です。この結果の 0.33 は直感と合っているのではないでしょうか。席１の子が成功する確率は 0.66 ですが、もし席１の子が２を引き、席２の子が１を引いてしまったら（確率 0.5）席３の子が失敗します（"2,1,3" のパターン）。また、席１の子が３を引いたとしても、席２の子が２を引いてしまったら（確率 0.5）失敗です（"3,2,1" のパターン）。席替えの成功確率は 0.66 の半分になって 0.33。これはわかりやすい話です。
席替えの成功確率が 0.33 という低い数字になるのは、各生徒の成功確率が 0.66 とか 0.5 とかで、1.0 と比べるとかなり小さい数字だからと考えられます。席が３つしかないのでそうなるしかなく、成功確率は低い。
では、40人のクラスではどうでしょうか。この場合、席１の子の成功確率は \(\dfrac{39}{40}=0.975\) であり、席２の子の成功確率もそれに近い数です。40人全員の成功確率もそれなりに高いはずで、従ってクラスの席替えの成功確率は高いと思われます。くじを引く子たちの立場で考えてみても、まさか自分の席の番号を引くとは思わないでしょう。選択肢は 40 もあるのだから ･･････。しかし、実際に成功確率を計算してみると、
席替えの成功確率\(\fallingdotseq0.368\)
となり、40人のクラスでも、3人のクラスと成功確率はあまり変わらないのです。わずかに増加していますが ･･････。36.8 % という確率は、席替えを３回トライして１回成功するかどうかという数字です。逆に言うと、63.2 % という高確率で自分の席の紙を引く子が少なくとも１人は出てくる。
これは直感とはズレているのではないでしょうか。なぜそのようになるのか、それが以下です。
マッチング問題と完全順列
これは、一般にはマッチング問題（出会いの問題。matching problem）と呼ばれています。フランスの数学者、ピエール・ド・モンモール（1678-1719）が初めて提示したので、モンモールの問題とも言われます。
２人のプレーヤー、ＡとＢがそれぞれ 13枚のカードを渡されます。Ａにはスペードの A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K を、Ｂにはクラブの A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K です。ＡとＢはその中から任意の１枚を選び、同時に場に提示します。一度提示したカードは捨て、これを13回繰り返します。場に提示されたカードの種類が１回でも同じであればマッチング成功です。同じ種類のカードが全くなければマッチングは不成功です。成功する確率はどれだけか、というのがマッチング問題です。
一般化すると、\(1\) ～ \(n\) の数字の書かれたカードをランダムにシャッフルし、順番に場に提示したとき、\(i\) 番目に提示したカードの数字が \(i\) であるとマッチングが成立したことになります。「\(i\) 番目に提示したカードの数字が \(i\) でない」という状況が \(n\) 回続くと（＝一度もマッチしないと）、マッチング不成立です。
さきほど書いた\(40\)人のクラスの「席替え成功確率」は、\(n=40\) のときにマッチング不成立になる確率はいくらか、という問題になります。
\(1\) ～ \(n\) の \(n\)個の数字の順列の総数は \(n!\) ですが、\(i\) 番目の数字 \(d_i\) が \(i\) でない \((1\leq i\leq n)\) 順列を完全順列（complete permutation）と言います。つまり、
\(d_i\neq i\:\:(1\leq i\leq n)\)
を満たす順列です。攪乱順列（derangement）という言い方もあります。\(d_i\neq i\:(1\leq i\leq n)\) であってこそ「数字を完全にかき混ぜた（＝攪乱した）順列」なので、そう呼ばれるのでしょう。
完全順列という言葉を使うと、\(\bs{n}\) 個の数字の順列（総数は \(\bs{n!}\)）のうちの完全順列の割合がマッチング不成立の確率（＝席替えの成功確率）です。では、完全順列の数はどの程度あるのでしょうか。これを計算するために、まず、集合における「包除原理」を説明します。
包除原理（Inclusion-Exclusion Principle）
包除原理とは、有限集合の和集合の要素数を計算する原理で、英語では Inclusion-Exclusion Principle と言います。Inclusion は包含、Exclusionは除外の意味で、日本語では包除原理です。
以下、\(A_i\) を有限集合とし、\(A_i\) の要素数を \(|A_i|\) と表記します。いま２つの集合、\(A_1\) と \(A_2\) があるとき、\(A_1\) と \(A_2\) の和集合の要素数は次の式で表されます。
\(|A_1\cup A_2|=|A_1|+|A_2|-|A_1\cap A_2|\)
つまり、\(A_1\) と \(A_2\) の和集合の要素数は、\(A_1\) の要素数と \(A_2\) の要素数の和から、ダブル・カウントした \(A_1\) と \(A_2\) の共通部分（\(A_1\cap A_2\)）の要素数を引き算して求まります。これはシンプルです。３つの集合 \(A_1\:,A_2,\:A_3\) になると次が成り立ちます。
【証明】
\(|A_1|+|A_2|+|A_3|\) の式は、複数回カウントしている要素がある。要素のカウント数を図に表すと図１である。
\(|A_1\cap A_2|+|A_1\cap A_3|+|A_2\cap A_3|\) は「２つの集合の共通部分」を複数回カウントしている要素がある。要素のカウント数を図に表すと図２である。
\(|A_1\cap A_2\cap A_3|\) は「３つの集合の共通部分」を１回だけカウントしているから、カウント数を図に表すと図３である。要素のカウント数に注目して、
（図１）\(-\)（図２）\(+\)（図３）
を計算すると図４になる。図４はすべての要素を１回だけカウントしているので、題意は正しい。【証明終】
包除原理を使う例として、たとえば次の問題があります。
という問題です。包除原理の通りに順に計算すると、
\(\phantom{1}2\)の倍数：\(50\)（\(\phantom{1}2\)～\(100\)）
\(\phantom{1}3\)の倍数：\(33\)（\(\phantom{1}3\)～\(\phantom{1}99\)）
\(\phantom{1}5\)の倍数：\(20\)（\(\phantom{1}5\)～\(100\)）
\(\phantom{1}6\)の倍数：\(16\)（\(\phantom{1}6\)～\(\phantom{1}96\)）
\(10\)の倍数：\(10\)（\(10\)～\(100\)）
\(15\)の倍数：\(\phantom{1}6\)（\(15\)～\(\phantom{1}90\)）
\(30\)の倍数：\(\phantom{1}3\)（\(30\)～\(\phantom{1}90\)）
なので、答えは
\(100-(50+33+20-16-10-6+3)=26\)
となります。実際に数をリストしてみると、
\(\phantom{1}1,\:\phantom{1}7,\:11,\:13,\:17,\:19,\:23,\:29,\:31,\:37,\)
\(41,\:43,\:47,\:49,\:53,\:59,\:61,\:67,\:71,\:73,\)
\(77,\:79,\:83,\:89,\:91,\:97\)
の \(26\)個です。
さらに、集合の数が４個になると次のようになります。一般論につながる形で証明をします。
【証明】
１つの集合だけに属する要素は、第１項だけでプラス・カウントされているから、カウント数は１である。
\(A_1\) と \(A_2\) の共通部分（\(A_1\cap A_2\)）の要素は、第１項で２回プラス・カウントされ、第２項で１回マイナス・カウントされているから、合計のカウント数は計１である。これは「２つの集合の共通部分」すべてで同じである。
\(A_1\cap A_2\cap A_3\) の要素は、第１項で３回プラス・カウントされ（\(|A_1|+|A_2|+|A_3|\) で \(+\:{}_{3}\mr{C}_{1}\) 回）、第２項で３回マイナス・カウントされ（\(-|A_1\cap A_2|-\)\(|A_1\cap A_3|-\)\(|A_2\cap A_3|\) で \(-\:{}_{3}\mr{C}_{2}\) 回）、第３項で１回プラス・カウントされているから（\(+\:{}_{3}\mr{C}_{3}\) 回）、合計のカウント数は１である。これは「３つの集合の共通部分」すべてで同じである。
\(A_1\cap A_2\cap A_3\cap A_4\) の要素が何回カウントされているかをみると、
であり、合計のカウント数は１である。以上で、１つの集合だけに属する要素も、２～４個の集合の共通部分の要素もすべて１回カウントされているから、題意は正しい。【証明終】
集合の数が \(n\)個 の場合の一般論では次のようになります。
【証明】
１つの集合だけに属する要素は、第１項だけでプラス・カウントされているから、カウント数は１である。また、\(m\)個の集合の共通部分（\(2\leq m\leq n\)）は、第１項 ～ 第\(\bs{m}\)項でカウントされ、回数はそれぞれ、
だから、合計のカウント数は、
\(\displaystyle\sum_{k=1}^{m}(-1)^{k-1}{}_{m}\mr{C}_{k}\)
である。この式の値を評価するために \((x-1)^m\) の二項展開を利用する。\((x-1)^m\) を二項展開すると、
\(\begin{eqnarray}
&&\:\:(x-1)^m=&x^m&-{}_{m}\mr{C}_{1}x^{m-1}+{}_{m}\mr{C}_{2}x^{m-2}\\
&&&&-{}_{m}\mr{C}_{3}x^{m-3}+\:\cd\:+(-1)^m{}_{m}\mr{C}_{m}\\
\end{eqnarray}\)
となるが、この式に \(x=1\) を代入すると、
左辺\(=0\)
右辺\(=1-{}_{m}\mr{C}_{1}x+{}_{m}\mr{C}_{2}-{}_{m}\mr{C}_{3}+\:\cd\:+(-1)^m{}_{m}\mr{C}_{m}\)
である。ここから、
\(\longrightarrow\:\displaystyle\sum_{k=1}^{m}(-1)^{k-1}{}_{m}\mr{C}_{k}=1\)
となる。従って、\(m\)個の集合の共通部分（\(2\leq m\leq n\)）は、\(m\) の値にかかわらず合計１回だけカウントされている。
以上で１つの集合だけに属する要素も、共通部分に属する要素も、すべて１回カウントされているから、題意は正しい。【証明終】
完全順列の個数を数える
包除原理を踏まえて、完全順列の個数を計算します。\(1\) ～ \(n\) の \(n\) 個の数字の順列の集合を \(P(n)\) とすると \(|P(n)|=n!\) です。これらの中で、順列の \(i\) 番目の数字 \(d_i\) が \(i\) でないもの \((1\leq i\leq n)\) が完全順列（complete permutation）です。つまり、
\(d_i\neq i\:\:(1\leq i\leq n)\)
を満たす順列です。ここでは完全順列の反対、つまり、
ある \(i\:(1\leq i\leq n)\) について \(d_i=i\)
となる順列を「不完全順列」（incomplete permutation）と呼ぶことにし（ここだけの用語です）、
\(P_{cp}(n)\)：完全順列の集合
\(P_{ip}(n)\)：不完全順列の集合
と書くことにします。
\(\begin{eqnarray}
&&\:\:|P(n)|&=|P_{cp}(n)|+|P_{ip}(n)|\\
&&&=n!\\
\end{eqnarray}\)
です。以下、不完全順列の個数（\(|P_{ip}(n)|\)）を調べることにします。
\(1\) ～ \(n\) の \(n\)個の数字の順列で、\(i\) 番目の数字 \(d_i\) が \(d_i=i\) であるような順列の集合を \(A_i\) と定義します。そうすると、不完全順列の集合は、
\(P_{ip}(n)=A_1\cup A_2\cup A_3\cup\cd\cup A_n\)
と表現できます。もちろん、\(A_1,\:A_2,\:A_3,\:\cd\) の要素にはかなりの重複があります。ここで、重複を排して不完全順列の数を数えるために包除原理を使うと、
\(|P_{ip}(n)|=\)
となります。まず、第１項を考えると、\(|A_1|\) は「１番目の数字以外の \(n-1\) 個の数字」がつくる順列の数だけあります。つまり、
\(|A_1|=(n-1)!\)
であり、問題の対称性から、
\(|A_1|=|A_2|=|A_3|=\:\cd\:=|A_n|\)
なので、第１項\(=n\cdot(n-1)!\) です。
第２項は、２つの数字の選び方が \({}_{n}\mr{C}_{2}\) 通りあり、それぞれについて「２つの数字以外の \((n-2)\) 個の数字」がつくる順列の数＝\((n-2)!\) だけマイナス・カウントされるので、
第２項\(=-{}_{n}\mr{C}_{2}\cdot(n-2)!\)
です。同様に考えて全体をまとめると、
となります。従って、不完全順列の数はこれらを合算して、
\(|P_{ip}(n)|\)
\(\begin{eqnarray}
&&\:\: &=&n\cdot(n-1)!-\dfrac{n!}{(n-2)!2!}\cdot(n-2)!\\
&&&&+\dfrac{n!}{(n-3)!3!}\cdot(n-3)!-\cd\:+(-1)^{n-1}\cdot1\\
&&&=&n!\left(1-\dfrac{1}{2!}+\dfrac{1}{3!}-\:\cd\:+(-1)^{n-1}\dfrac{1}{n!}\right)\\
\end{eqnarray}\)
と計算できます。完全順列の数は、
\(|P_{cp}(n)|\)
\(=n!-|P_{ip}(n)|\)
\(=n!\left(\dfrac{1}{2!}-\dfrac{1}{3!}+\:\cd\:-(-1)^{n-1}\dfrac{1}{n!}\right)\)
\(=n!\left(\dfrac{1}{2!}-\dfrac{1}{3!}+\:\cd\:+(-1)^n\dfrac{1}{n!}\right)\)
です。
マッチング成立・不成立の確率
以上の不完全順列の個数をもとに、マッチングが成立する確率 \(\mathcal{P}_{match}(n)\) を計算すると、
\(\begin{eqnarray}
&&\:\:\mathcal{P}_{match}(n)&=\dfrac{|P_{ip}(n)|}{n!}\\
&&&=1-\dfrac{1}{2!}+\dfrac{1}{3!}-\:\cd\:+(-1)^{n-1}\dfrac{1}{n!}\\
&&&=\displaystyle\sum_{k=1}^{n}(-1)^{k-1}\dfrac{1}{k!}\\
\end{eqnarray}\)
となります。マッチングが不成立の確率 \(\mathcal{P}_{unmatch}(n)\) は、
\(\begin{eqnarray}
&&\:\:\mathcal{P}_{unmatch}(n)&=\dfrac{|P_{cp}(n)|}{n!}\\
&&&=\dfrac{1}{2!}-\dfrac{1}{3!}+\:\cd\:+(-1)^n\dfrac{1}{n!}\\
&&&=\displaystyle\sum_{k=2}^{n}(-1)^k\dfrac{1}{k!}\\
\end{eqnarray}\)
であり、これが「くじによる席替え」が成功する確率です。
ここで、\(\displaystyle\lim_{n\rightarrow\infty}\mathcal{P}_{match}(n)\)、\(\displaystyle\lim_{n\rightarrow\infty}\mathcal{P}_{unmatch}(n)\) の値を求めます。これにはテイラー展開の特別の場合であるマクローリン展開を使います。自然対数の底を \(e\) とすると、\(e^x\) のマクローリン展開は、
\(e^x=1+x+\dfrac{1}{2!}x^2+\dfrac{1}{3!}x^3+\dfrac{1}{3!}x^4+\:\cd\)
です。この式で \(x=-1\) とすると、
\(\dfrac{1}{e}=\dfrac{1}{2!}-\dfrac{1}{3!}+\dfrac{1}{4!}-\:\cd\)
\(1-\dfrac{1}{e}=1-\dfrac{1}{2!}+\dfrac{1}{3!}-\dfrac{1}{4!}+\:\cd\)
なので、
\(\begin{eqnarray}
&&\:\:\displaystyle\lim_{n\rightarrow\infty}\mathcal{P}_{match}(n)&=1-\dfrac{1}{e}\\
&&&=0.6321205588285577\cd\\
&&\:\:\displaystyle\lim_{n\rightarrow\infty}\mathcal{P}_{unmatch}(n)&=\dfrac{1}{e}\\
&&&=0.3678794411714423\cd\\
\end{eqnarray}\)
となります。ちなみに、この値を初めて求めたのは大数学者のオイラーだそうです。
\(\mathcal{P}_{unmatch}(n)\) の値（＝順列の中の完全順列の割合）を、\(n=3\) ～ \(13\)（＝カードの枚数） について計算し、小数点以下\(10\)桁だけを表示すると次の表の通りになります。
\(n=6\) あたりから急速に極限値である \(\dfrac{1}{e}=0.3678794411\cd\) に近づき、\(n=13\) では小数点以下\(10\)桁までが極限値と一致します。以降はほぼ一定の値になり、もちろん\(40\)人クラスの席替えの成功率も極限値とほぼ一致します。ということで、\(n\) が極端に少ない場合（\(5\) 以下）を除き、
としてよいのでした。つまり、くじによる席替えの成功確率は約\(\bs{36.8\:\%}\) であり、クラスの人数によらない。これが結論です。この「\(n\) の値にかかわらず確率がほぼ一定」というところが、少々直感に反する結果になるのでした。
本文では包除原理を使って完全順列の個数を求めましたが（包除原理の証明が記事の目的の一つでした）、完全順列の個数を示す漸化式を作ることができます。それを説明します。簡潔に書くために、\(n\) 個の数字の完全順列の数を \(D(n)\) とします（攪乱順列：derangement の \(D\) で、本文では \(|P_{cp}(n)|\) としたのもです）。
わかりやすく説明するために、\(n\) 個の箱があり、\(1\) ～ \(n\) の番号が振ってあるとします。また \(n\) 枚のカードがあり、\(1\) ～ \(n\) の番号が書かれています。このカードを１枚づつ順に箱に入れるとします。入れる順番は任意ですが、１つの箱には１枚のカードしか入れられません。箱に入れていないカードを "残っているカード"、カードが入っていない箱を "残っている箱" と表現します。
この状況で、カードと箱の対応パターンは \(n!\) 通りあります。
ここで「カードの番号と同じ番号の箱には入れない」というルールを設けます。このルールがあると、\(n\) 個の箱への \(n\) 枚のカードの対応パターンは完全順列の数である \(D(n)\) 通りになります。
入れる順序は任意なので、最初にカード \(\bs{1}\) を箱 \(\bs{i\:\:(i\neq1)}\) に入れるとします。\(i\) の選び方は \(n-1\) 通りあります。次に、カード \(\bs{i}\) を残っているどれかの箱に入れるとします。どの箱に入れるかを２つに分けて考えます。
カード \(i\) を箱 \(1\) に入れる場合
入れた後では、箱 \(1\) にカード \(i\)、箱 \(i\) にカード \(1\) がある状態です。残っているのは、
であり、これらの \((n-2)\) 枚のカードをルールに沿って \((n-2)\) 個の箱に入れるパターンは、定義から \(D(n-2)\) 通りです。
カード \(i\) を箱 \(1\) に入れない場合
この場合、カード \(i\) は "箱 \(1\) 以外の残っている箱" に入れることになります。ここで、カードの番号 \(i\) を \(1\) に書き換えてしまいます。こうしたとしても（書き換えた結果の）カード \(1\) は、"箱 \(1\) 以外の残っている箱" に入れることになります。カード \(1\) は箱 \(1\) に入れてはいけないというルールがあるからです。つまり、カード番号 の \(i\) を \(1\) に書き換えたとしても、「ルールに沿ってカードを箱に入れるパターンの数」は変わりません。
カードの番号を書き換えた直後の状態で、残っているのは、
となり、これらの \((n-1)\) 枚のカードをルールに沿って \((n-1)\) 個の箱に入れるパターンは、定義から \(D(n-1)\) 通りです。\((n-1)\) 枚を箱に入れ終わったあとで、\(1\) に書き換えたカードを \(i\) に戻せば、\(1\) から \(n\) のカードをすべて箱に入れたことになります。
まとめると、最初の \(i\) の選び方は \(n-1\) 通りあり、それぞれについて、
があり、この２つは排他的です。従って、
\(D(n)=(n-1)(D(n-1)+D(n-2))\)
の漸化式が得られます。\(D(1)=0,\:\:D(2)=1\) なので、
\(D(1)=0\)
\(D(2)=1\)
\(D(3)=2\cdot(1+0)=2\)
\(D(4)=3\cdot(2+1)=9\)
などとなります。
\(D(n)\) の一般項を求めるために漸化式を変形します。
\(D(n)=(n-1)(D(n-1)+D(n-2))\)
\(D(n)=nD(n-1)-D(n-1)+(n-1)D(n-2)\)
\(D(n)-nD(n-1)=-(D(n-1)-(n-1)D(n-2))\)
\(B(n)=D(n)-nD(n-1)\) とおくと、
\(B(2)=D(2)-2\cdot D(1)=1\)
\(B(n)=-B(n-1)\)
です。従って \(B(n)\) の一般項は、
\(B(n)=(-1)^n\)
であり、\(D(n)\) に戻すと、
\(D(n)-nD(n-1)=(-1)^n\)
になります。この両辺を \(n!\) で割ると、
\(\dfrac{D(n)}{n!}-\dfrac{D(n-1)}{(n-1)!}=(-1)^n\dfrac{1}{n!}\)
が得られます。この式の両辺を \(2\) から \(n\) までたし算して整理すると、
\(\dfrac{D(n)}{n!}-\dfrac{D(1)}{1!}\)
\(=\dfrac{1}{2!}-\dfrac{1}{3!}+\:\cd+(-1)^n\dfrac{1}{n!}\)
\(D(n)=n!\cdot\displaystyle\sum_{k=2}^{n}(-1)^k\dfrac{1}{k!}\)
となり、包除原理を使った計算（\(|P_{cp}(n)|\)）と一致します。
エレガントな解法ですが、漸化式を求めるのが難しい。特に「カード \(i\) を箱 \(1\) に入れない場合の数が \(D(n-1)\) である」ことをゼロから発想するのは大変でしょう。「カード \(i\) を箱 \(1\) に入れない」ということを「ルール上、カード \(1\) は箱 \(1\) に入れられない」と同一視する発想が必要です。また、漸化式から一般項を求める際にも、「式の変形」と「\(n!\) で割る」という、２つの "一般項生成テクニック" がポイントになっています。
ということで、本文では包除原理を使った説明にしました。この方がマッチング問題の本質をとらえています。
ただ、問題の本質をとらえた正攻法で "丹念に" 証明するしかないと "一見思える" 問題でも、漸化式という大変エレガントな解答がある。そのあたりに数学の深さの一端が現れていると思います。
今まで「高校数学で理解する ･･････」というタイトルの記事をいくつか書きましたが、その続きです。過去の記事は、
| 高校数学で理解するRSA暗号の数理 | |
| 高校数学で理解する公開鍵暗号の数理 | |
| 高校数学で理解する楕円曲線暗号の数理 | |
| 高校数学で理解する誕生日のパラドックス | |
| 高校数学で理解するレジ行列の数理 | |
| 高校数学で理解するガロア理論（１）～（６） | |
| 高校数学で理解する ChatGPT の仕組み | |
| 高校数学で理解する素数判定の数理 | |
| 高校数学で理解するガロア理論（７） |
の、総計 17 の記事です。分類すると、
| 公開鍵暗号とその関連技術（素数判定）
No.310, 311, 313, 315, 316, 369
| |
| ガロア理論
No.354, 355, 356, 357, 358, 359, 370
| |
| 直感に反する確率
No.325, 329
| |
| 生成AIの技術（＝Transformer）
No.365, 366
|
となります。今回の "マッチング問題" は「③ 直感に反する確率」のジャンルに属するものです。
なお、"高校数学で理解する" というタイトルは、「高校までで習う数学だけを前提知識とする（それ以外は全部証明する）」という意味です。もちろん、"おおよそ高校までの数学" が正しく、正式には大学で習う数学を証明なしで使ったことがあります。たとえば、No.325「高校数学で理解する誕生日のパラドックス」での "マクローリン展開（テイラー展開）" ですが、今回もそれを使います。
席替えの成功確率
小学校で 40人のクラスがあるとします。このクラスには約 90%の確率で誕生日が同じ子がいる（正確には 89.12%）というのが No.325「高校数学で理解する誕生日のパラドックス」でしたが、今回は席替えの問題です。
40人のクラスで、席替えを "くじ引き" でやるとします。まず、現在の席に 1 ～ 40 の席番号を割り振ります。担任の先生は、1 ～ 40 の数字を書いた紙を 40枚用意し、その紙を数字が見えないように折って、箱の中に入れてかき混ぜます。生徒は席番号１の子から順に箱から紙を１枚ずつ引き、そこに書かれている数字がその子の新しい席となります。もちろんこのやり方だと、今の自分の席番号の紙を引く子が現れる可能性があります。現在の席番号以外の番号を引けば、その子は "成功" と定義します。
そして「すべての子が成功したら、クラスの席替えは成功」と定義します。つまり「すべての子が現在の席番号と違う番号を引いたとき、席替えは成功」です。では、40人のクラスで席替えが成功する確率はどれほどでしょうか。これが問題です。
40人だと考えづらいので、極端ですが、クラスの人数が 3人の場合で考えてみます。席１、席２、席３の子が引いた数字を順に３つの数字の組で表すと、考えられる組み合わせは、
（1, 2, 3）
（1, 3, 2）
（2, 1, 3）
（2, 3, 1）◎
（3, 1, 2）◎
（3, 2, 1）
の６通り（=3!）です。このうち "席替え成功" となるのは ◎印をつけた、
（2, 3, 1）
（3, 1, 2）
の２通りだけなので、
席替えの成功確率\(=\dfrac{2}{6}\fallingdotseq0.33\)
です。この結果の 0.33 は直感と合っているのではないでしょうか。席１の子が成功する確率は 0.66 ですが、もし席１の子が２を引き、席２の子が１を引いてしまったら（確率 0.5）席３の子が失敗します（"2,1,3" のパターン）。また、席１の子が３を引いたとしても、席２の子が２を引いてしまったら（確率 0.5）失敗です（"3,2,1" のパターン）。席替えの成功確率は 0.66 の半分になって 0.33。これはわかりやすい話です。
席替えの成功確率が 0.33 という低い数字になるのは、各生徒の成功確率が 0.66 とか 0.5 とかで、1.0 と比べるとかなり小さい数字だからと考えられます。席が３つしかないのでそうなるしかなく、成功確率は低い。
では、40人のクラスではどうでしょうか。この場合、席１の子の成功確率は \(\dfrac{39}{40}=0.975\) であり、席２の子の成功確率もそれに近い数です。40人全員の成功確率もそれなりに高いはずで、従ってクラスの席替えの成功確率は高いと思われます。くじを引く子たちの立場で考えてみても、まさか自分の席の番号を引くとは思わないでしょう。選択肢は 40 もあるのだから ･･････。しかし、実際に成功確率を計算してみると、
席替えの成功確率\(\fallingdotseq0.368\)
となり、40人のクラスでも、3人のクラスと成功確率はあまり変わらないのです。わずかに増加していますが ･･････。36.8 % という確率は、席替えを３回トライして１回成功するかどうかという数字です。逆に言うと、63.2 % という高確率で自分の席の紙を引く子が少なくとも１人は出てくる。
これは直感とはズレているのではないでしょうか。なぜそのようになるのか、それが以下です。
マッチング問題と完全順列
これは、一般にはマッチング問題（出会いの問題。matching problem）と呼ばれています。フランスの数学者、ピエール・ド・モンモール（1678-1719）が初めて提示したので、モンモールの問題とも言われます。
２人のプレーヤー、ＡとＢがそれぞれ 13枚のカードを渡されます。Ａにはスペードの A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K を、Ｂにはクラブの A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K です。ＡとＢはその中から任意の１枚を選び、同時に場に提示します。一度提示したカードは捨て、これを13回繰り返します。場に提示されたカードの種類が１回でも同じであればマッチング成功です。同じ種類のカードが全くなければマッチングは不成功です。成功する確率はどれだけか、というのがマッチング問題です。
一般化すると、\(1\) ～ \(n\) の数字の書かれたカードをランダムにシャッフルし、順番に場に提示したとき、\(i\) 番目に提示したカードの数字が \(i\) であるとマッチングが成立したことになります。「\(i\) 番目に提示したカードの数字が \(i\) でない」という状況が \(n\) 回続くと（＝一度もマッチしないと）、マッチング不成立です。
さきほど書いた\(40\)人のクラスの「席替え成功確率」は、\(n=40\) のときにマッチング不成立になる確率はいくらか、という問題になります。
\(1\) ～ \(n\) の \(n\)個の数字の順列の総数は \(n!\) ですが、\(i\) 番目の数字 \(d_i\) が \(i\) でない \((1\leq i\leq n)\) 順列を完全順列（complete permutation）と言います。つまり、
\(d_i\neq i\:\:(1\leq i\leq n)\)
を満たす順列です。攪乱順列（derangement）という言い方もあります。\(d_i\neq i\:(1\leq i\leq n)\) であってこそ「数字を完全にかき混ぜた（＝攪乱した）順列」なので、そう呼ばれるのでしょう。
完全順列という言葉を使うと、\(\bs{n}\) 個の数字の順列（総数は \(\bs{n!}\)）のうちの完全順列の割合がマッチング不成立の確率（＝席替えの成功確率）です。では、完全順列の数はどの程度あるのでしょうか。これを計算するために、まず、集合における「包除原理」を説明します。
包除原理（Inclusion-Exclusion Principle）
包除原理とは、有限集合の和集合の要素数を計算する原理で、英語では Inclusion-Exclusion Principle と言います。Inclusion は包含、Exclusionは除外の意味で、日本語では包除原理です。
以下、\(A_i\) を有限集合とし、\(A_i\) の要素数を \(|A_i|\) と表記します。いま２つの集合、\(A_1\) と \(A_2\) があるとき、\(A_1\) と \(A_2\) の和集合の要素数は次の式で表されます。
\(|A_1\cup A_2|=|A_1|+|A_2|-|A_1\cap A_2|\)
つまり、\(A_1\) と \(A_2\) の和集合の要素数は、\(A_1\) の要素数と \(A_2\) の要素数の和から、ダブル・カウントした \(A_1\) と \(A_2\) の共通部分（\(A_1\cap A_2\)）の要素数を引き算して求まります。これはシンプルです。３つの集合 \(A_1\:,A_2,\:A_3\) になると次が成り立ちます。
\(|A_1\cup A_2\cup A_3|\) \(\begin{eqnarray} &&\:\:=&|A_1|+|A_2|+|A_3|\\ &&&-|A_1\cap A_2|-|A_1\cap A_3|-|A_2\cap A_3|\\ &&&+|A_1\cap A_2\cap A_3|\\ \end{eqnarray}\) |
【証明】
|
|
|
|
\(|A_1|+|A_2|+|A_3|\) の式は、複数回カウントしている要素がある。要素のカウント数を図に表すと図１である。
\(|A_1\cap A_2|+|A_1\cap A_3|+|A_2\cap A_3|\) は「２つの集合の共通部分」を複数回カウントしている要素がある。要素のカウント数を図に表すと図２である。
\(|A_1\cap A_2\cap A_3|\) は「３つの集合の共通部分」を１回だけカウントしているから、カウント数を図に表すと図３である。要素のカウント数に注目して、
（図１）\(-\)（図２）\(+\)（図３）
を計算すると図４になる。図４はすべての要素を１回だけカウントしているので、題意は正しい。【証明終】
包除原理を使う例として、たとえば次の問題があります。
\(100\)以下の自然数で、\(2,\:3,\:5\) の倍数ではない数は何個あるか |
という問題です。包除原理の通りに順に計算すると、
\(\phantom{1}2\)の倍数：\(50\)（\(\phantom{1}2\)～\(100\)）
\(\phantom{1}3\)の倍数：\(33\)（\(\phantom{1}3\)～\(\phantom{1}99\)）
\(\phantom{1}5\)の倍数：\(20\)（\(\phantom{1}5\)～\(100\)）
\(\phantom{1}6\)の倍数：\(16\)（\(\phantom{1}6\)～\(\phantom{1}96\)）
\(10\)の倍数：\(10\)（\(10\)～\(100\)）
\(15\)の倍数：\(\phantom{1}6\)（\(15\)～\(\phantom{1}90\)）
\(30\)の倍数：\(\phantom{1}3\)（\(30\)～\(\phantom{1}90\)）
なので、答えは
\(100-(50+33+20-16-10-6+3)=26\)
となります。実際に数をリストしてみると、
\(\phantom{1}1,\:\phantom{1}7,\:11,\:13,\:17,\:19,\:23,\:29,\:31,\:37,\)
\(41,\:43,\:47,\:49,\:53,\:59,\:61,\:67,\:71,\:73,\)
\(77,\:79,\:83,\:89,\:91,\:97\)
の \(26\)個です。
さらに、集合の数が４個になると次のようになります。一般論につながる形で証明をします。
\(|A_1\cup A_2\cup A_3\cup A_4|=\)
|
【証明】
１つの集合だけに属する要素は、第１項だけでプラス・カウントされているから、カウント数は１である。
\(A_1\) と \(A_2\) の共通部分（\(A_1\cap A_2\)）の要素は、第１項で２回プラス・カウントされ、第２項で１回マイナス・カウントされているから、合計のカウント数は計１である。これは「２つの集合の共通部分」すべてで同じである。
\(A_1\cap A_2\cap A_3\) の要素は、第１項で３回プラス・カウントされ（\(|A_1|+|A_2|+|A_3|\) で \(+\:{}_{3}\mr{C}_{1}\) 回）、第２項で３回マイナス・カウントされ（\(-|A_1\cap A_2|-\)\(|A_1\cap A_3|-\)\(|A_2\cap A_3|\) で \(-\:{}_{3}\mr{C}_{2}\) 回）、第３項で１回プラス・カウントされているから（\(+\:{}_{3}\mr{C}_{3}\) 回）、合計のカウント数は１である。これは「３つの集合の共通部分」すべてで同じである。
\(A_1\cap A_2\cap A_3\cap A_4\) の要素が何回カウントされているかをみると、
| 第１項で | \(+\:4\) 回 | （\(+\:{}_{4}\mr{C}_{1}\) 回） |
| 第２項で | \(-\:6\) 回 | （\(-\:{}_{4}\mr{C}_{2}\) 回） |
| 第３項で | \(+\:4\) 回 | （\(+\:{}_{4}\mr{C}_{3}\) 回） |
| 第４項で | \(-\:1\) 回 | （\(-\:{}_{4}\mr{C}_{4}\) 回） |
であり、合計のカウント数は１である。以上で、１つの集合だけに属する要素も、２～４個の集合の共通部分の要素もすべて１回カウントされているから、題意は正しい。【証明終】
集合の数が \(n\)個 の場合の一般論では次のようになります。
\(|A_1\cup A_2\cup A_3\cup\cd\cup A_n|=\)
|
【証明】
１つの集合だけに属する要素は、第１項だけでプラス・カウントされているから、カウント数は１である。また、\(m\)個の集合の共通部分（\(2\leq m\leq n\)）は、第１項 ～ 第\(\bs{m}\)項でカウントされ、回数はそれぞれ、
| 第１項で | \(+\) | \({}_{m}\mr{C}_{1}\) 回 |
| 第２項で | \(-\) | \({}_{m}\mr{C}_{2}\) 回 |
| 第３項で | \(+\) | \({}_{m}\mr{C}_{3}\) 回 |
| \(\vdots\) | ||
| 第\(\bs{m}\)項で | \((-1)^{m-1}\cdot\) | \({}_{m}\mr{C}_{m}\) 回 |
だから、合計のカウント数は、
\(\displaystyle\sum_{k=1}^{m}(-1)^{k-1}{}_{m}\mr{C}_{k}\)
である。この式の値を評価するために \((x-1)^m\) の二項展開を利用する。\((x-1)^m\) を二項展開すると、
\(\begin{eqnarray}
&&\:\:(x-1)^m=&x^m&-{}_{m}\mr{C}_{1}x^{m-1}+{}_{m}\mr{C}_{2}x^{m-2}\\
&&&&-{}_{m}\mr{C}_{3}x^{m-3}+\:\cd\:+(-1)^m{}_{m}\mr{C}_{m}\\
\end{eqnarray}\)
となるが、この式に \(x=1\) を代入すると、
左辺\(=0\)
右辺\(=1-{}_{m}\mr{C}_{1}x+{}_{m}\mr{C}_{2}-{}_{m}\mr{C}_{3}+\:\cd\:+(-1)^m{}_{m}\mr{C}_{m}\)
である。ここから、
| \({}_{m}\mr{C}_{1}-{}_{m}\mr{C}_{2}+{}_{m}\mr{C}_{3}-\:\cd\:-(-1)^m{}_{m}\mr{C}_{m}\) | \(=1\) | |
| \({}_{m}\mr{C}_{1}-{}_{m}\mr{C}_{2}+{}_{m}\mr{C}_{3}-\:\cd\:+(-1)^{m-1}{}_{m}\mr{C}_{m}\) | \(=1\) |
となる。従って、\(m\)個の集合の共通部分（\(2\leq m\leq n\)）は、\(m\) の値にかかわらず合計１回だけカウントされている。
以上で１つの集合だけに属する要素も、共通部分に属する要素も、すべて１回カウントされているから、題意は正しい。【証明終】
完全順列の個数を数える
包除原理を踏まえて、完全順列の個数を計算します。\(1\) ～ \(n\) の \(n\) 個の数字の順列の集合を \(P(n)\) とすると \(|P(n)|=n!\) です。これらの中で、順列の \(i\) 番目の数字 \(d_i\) が \(i\) でないもの \((1\leq i\leq n)\) が完全順列（complete permutation）です。つまり、
\(d_i\neq i\:\:(1\leq i\leq n)\)
を満たす順列です。ここでは完全順列の反対、つまり、
ある \(i\:(1\leq i\leq n)\) について \(d_i=i\)
となる順列を「不完全順列」（incomplete permutation）と呼ぶことにし（ここだけの用語です）、
\(P_{cp}(n)\)：完全順列の集合
\(P_{ip}(n)\)：不完全順列の集合
と書くことにします。
\(\begin{eqnarray}
&&\:\:|P(n)|&=|P_{cp}(n)|+|P_{ip}(n)|\\
&&&=n!\\
\end{eqnarray}\)
です。以下、不完全順列の個数（\(|P_{ip}(n)|\)）を調べることにします。
\(1\) ～ \(n\) の \(n\)個の数字の順列で、\(i\) 番目の数字 \(d_i\) が \(d_i=i\) であるような順列の集合を \(A_i\) と定義します。そうすると、不完全順列の集合は、
\(P_{ip}(n)=A_1\cup A_2\cup A_3\cup\cd\cup A_n\)
と表現できます。もちろん、\(A_1,\:A_2,\:A_3,\:\cd\) の要素にはかなりの重複があります。ここで、重複を排して不完全順列の数を数えるために包除原理を使うと、
\(|P_{ip}(n)|=\)
| \(+\displaystyle\sum_{i=1}^{n}|A_i|\) | 第１項 | ||
| \(-\displaystyle\sum_{1\leq i < j}^{n}|A_i\cap A_j|\) | 第２項 | ||
| \(+\displaystyle\sum_{1\leq i < j < k}^{n}|A_i\cap A_j\cap A_k|\) | 第３項 | ||
| \(\vdots\) | |||
| \((-1)^{n-1}\cdot|A_1\cap A_2\cap A_3\cap\cd\cap A_n|\) | 第\(\bs{n}\)項 |
となります。まず、第１項を考えると、\(|A_1|\) は「１番目の数字以外の \(n-1\) 個の数字」がつくる順列の数だけあります。つまり、
\(|A_1|=(n-1)!\)
であり、問題の対称性から、
\(|A_1|=|A_2|=|A_3|=\:\cd\:=|A_n|\)
なので、第１項\(=n\cdot(n-1)!\) です。
第２項は、２つの数字の選び方が \({}_{n}\mr{C}_{2}\) 通りあり、それぞれについて「２つの数字以外の \((n-2)\) 個の数字」がつくる順列の数＝\((n-2)!\) だけマイナス・カウントされるので、
第２項\(=-{}_{n}\mr{C}_{2}\cdot(n-2)!\)
です。同様に考えて全体をまとめると、
| 第１項\(=\) | \(+\) | \({}_{n}\mr{C}_{1}\cdot(n-1)!\) |
| 第２項\(=\) | \(-\) | \({}_{n}\mr{C}_{2}\cdot(n-2)!\) |
| 第３項\(=\) | \(+\) | \({}_{n}\mr{C}_{3}\cdot(n-3)!\) |
| \(\vdots\) | ||
| 第\(\bs{n}\)項\(=\) | \((-1)^{n-1}\cdot\) | \({}_{n}\mr{C}_{n}\cdot0!\) |
となります。従って、不完全順列の数はこれらを合算して、
\(|P_{ip}(n)|\)
\(\begin{eqnarray}
&&\:\: &=&n\cdot(n-1)!-\dfrac{n!}{(n-2)!2!}\cdot(n-2)!\\
&&&&+\dfrac{n!}{(n-3)!3!}\cdot(n-3)!-\cd\:+(-1)^{n-1}\cdot1\\
&&&=&n!\left(1-\dfrac{1}{2!}+\dfrac{1}{3!}-\:\cd\:+(-1)^{n-1}\dfrac{1}{n!}\right)\\
\end{eqnarray}\)
と計算できます。完全順列の数は、
\(|P_{cp}(n)|\)
\(=n!-|P_{ip}(n)|\)
\(=n!\left(\dfrac{1}{2!}-\dfrac{1}{3!}+\:\cd\:-(-1)^{n-1}\dfrac{1}{n!}\right)\)
\(=n!\left(\dfrac{1}{2!}-\dfrac{1}{3!}+\:\cd\:+(-1)^n\dfrac{1}{n!}\right)\)
です。
マッチング成立・不成立の確率
以上の不完全順列の個数をもとに、マッチングが成立する確率 \(\mathcal{P}_{match}(n)\) を計算すると、
\(\begin{eqnarray}
&&\:\:\mathcal{P}_{match}(n)&=\dfrac{|P_{ip}(n)|}{n!}\\
&&&=1-\dfrac{1}{2!}+\dfrac{1}{3!}-\:\cd\:+(-1)^{n-1}\dfrac{1}{n!}\\
&&&=\displaystyle\sum_{k=1}^{n}(-1)^{k-1}\dfrac{1}{k!}\\
\end{eqnarray}\)
となります。マッチングが不成立の確率 \(\mathcal{P}_{unmatch}(n)\) は、
\(\begin{eqnarray}
&&\:\:\mathcal{P}_{unmatch}(n)&=\dfrac{|P_{cp}(n)|}{n!}\\
&&&=\dfrac{1}{2!}-\dfrac{1}{3!}+\:\cd\:+(-1)^n\dfrac{1}{n!}\\
&&&=\displaystyle\sum_{k=2}^{n}(-1)^k\dfrac{1}{k!}\\
\end{eqnarray}\)
であり、これが「くじによる席替え」が成功する確率です。
ここで、\(\displaystyle\lim_{n\rightarrow\infty}\mathcal{P}_{match}(n)\)、\(\displaystyle\lim_{n\rightarrow\infty}\mathcal{P}_{unmatch}(n)\) の値を求めます。これにはテイラー展開の特別の場合であるマクローリン展開を使います。自然対数の底を \(e\) とすると、\(e^x\) のマクローリン展開は、
\(e^x=1+x+\dfrac{1}{2!}x^2+\dfrac{1}{3!}x^3+\dfrac{1}{3!}x^4+\:\cd\)
です。この式で \(x=-1\) とすると、
\(\dfrac{1}{e}=\dfrac{1}{2!}-\dfrac{1}{3!}+\dfrac{1}{4!}-\:\cd\)
\(1-\dfrac{1}{e}=1-\dfrac{1}{2!}+\dfrac{1}{3!}-\dfrac{1}{4!}+\:\cd\)
なので、
\(\begin{eqnarray}
&&\:\:\displaystyle\lim_{n\rightarrow\infty}\mathcal{P}_{match}(n)&=1-\dfrac{1}{e}\\
&&&=0.6321205588285577\cd\\
&&\:\:\displaystyle\lim_{n\rightarrow\infty}\mathcal{P}_{unmatch}(n)&=\dfrac{1}{e}\\
&&&=0.3678794411714423\cd\\
\end{eqnarray}\)
となります。ちなみに、この値を初めて求めたのは大数学者のオイラーだそうです。
\(\mathcal{P}_{unmatch}(n)\) の値（＝順列の中の完全順列の割合）を、\(n=3\) ～ \(13\)（＝カードの枚数） について計算し、小数点以下\(10\)桁だけを表示すると次の表の通りになります。
| \(3\) | \(0.3333333333\) |
| \(4\) | \(0.3750000000\) |
| \(5\) | \(0.3666666666\) |
| \(6\) | \(0.3680555555\) |
| \(7\) | \(0.3678571428\) |
| \(8\) | \(0.3678819444\) |
| \(9\) | \(0.3678791887\) |
| \(10\) | \(0.3678794642\) |
| \(11\) | \(0.3678794392\) |
| \(12\) | \(0.3678794413\) |
| \(13\) | \(0.3678794411\) |
| \(\vdots\) | \(\vdots\) |
| \(\infty\) | \(0.3678794411\) |
\(n=6\) あたりから急速に極限値である \(\dfrac{1}{e}=0.3678794411\cd\) に近づき、\(n=13\) では小数点以下\(10\)桁までが極限値と一致します。以降はほぼ一定の値になり、もちろん\(40\)人クラスの席替えの成功率も極限値とほぼ一致します。ということで、\(n\) が極端に少ない場合（\(5\) 以下）を除き、
| マッチング成立の確率 | ：\(63.2\:\%\) | |
| マッチング不成立の確率 | ：\(36.8\:\%\) |
としてよいのでした。つまり、くじによる席替えの成功確率は約\(\bs{36.8\:\%}\) であり、クラスの人数によらない。これが結論です。この「\(n\) の値にかかわらず確率がほぼ一定」というところが、少々直感に反する結果になるのでした。
| 補記：漸化式 |
本文では包除原理を使って完全順列の個数を求めましたが（包除原理の証明が記事の目的の一つでした）、完全順列の個数を示す漸化式を作ることができます。それを説明します。簡潔に書くために、\(n\) 個の数字の完全順列の数を \(D(n)\) とします（攪乱順列：derangement の \(D\) で、本文では \(|P_{cp}(n)|\) としたのもです）。
わかりやすく説明するために、\(n\) 個の箱があり、\(1\) ～ \(n\) の番号が振ってあるとします。また \(n\) 枚のカードがあり、\(1\) ～ \(n\) の番号が書かれています。このカードを１枚づつ順に箱に入れるとします。入れる順番は任意ですが、１つの箱には１枚のカードしか入れられません。箱に入れていないカードを "残っているカード"、カードが入っていない箱を "残っている箱" と表現します。
この状況で、カードと箱の対応パターンは \(n!\) 通りあります。
ここで「カードの番号と同じ番号の箱には入れない」というルールを設けます。このルールがあると、\(n\) 個の箱への \(n\) 枚のカードの対応パターンは完全順列の数である \(D(n)\) 通りになります。
入れる順序は任意なので、最初にカード \(\bs{1}\) を箱 \(\bs{i\:\:(i\neq1)}\) に入れるとします。\(i\) の選び方は \(n-1\) 通りあります。次に、カード \(\bs{i}\) を残っているどれかの箱に入れるとします。どの箱に入れるかを２つに分けて考えます。
カード \(i\) を箱 \(1\) に入れる場合
入れた後では、箱 \(1\) にカード \(i\)、箱 \(i\) にカード \(1\) がある状態です。残っているのは、
| カード | ：\(2,\:3,\:\cd,\:i-1,\:i+1,\:\cd\:,\:n\) | |
| 箱 | ：\(2,\:3,\:\cd,\:i-1,\:i+1,\:\cd\:,\:n\) |
であり、これらの \((n-2)\) 枚のカードをルールに沿って \((n-2)\) 個の箱に入れるパターンは、定義から \(D(n-2)\) 通りです。
カード \(i\) を箱 \(1\) に入れない場合
この場合、カード \(i\) は "箱 \(1\) 以外の残っている箱" に入れることになります。ここで、カードの番号 \(i\) を \(1\) に書き換えてしまいます。こうしたとしても（書き換えた結果の）カード \(1\) は、"箱 \(1\) 以外の残っている箱" に入れることになります。カード \(1\) は箱 \(1\) に入れてはいけないというルールがあるからです。つまり、カード番号 の \(i\) を \(1\) に書き換えたとしても、「ルールに沿ってカードを箱に入れるパターンの数」は変わりません。
カードの番号を書き換えた直後の状態で、残っているのは、
| カード | ：\(1,\:2,\:3,\:\cd,\:i-1,\:i+1,\:\cd\:,\:n\) | |
| 箱 | ：\(1,\:2,\:3,\:\cd,\:i-1,\:i+1,\:\cd\:,\:n\) |
となり、これらの \((n-1)\) 枚のカードをルールに沿って \((n-1)\) 個の箱に入れるパターンは、定義から \(D(n-1)\) 通りです。\((n-1)\) 枚を箱に入れ終わったあとで、\(1\) に書き換えたカードを \(i\) に戻せば、\(1\) から \(n\) のカードをすべて箱に入れたことになります。
まとめると、最初の \(i\) の選び方は \(n-1\) 通りあり、それぞれについて、
| カード \(i\) を箱 \(1\) に入れる場合 | ：\(D(n-2)\) 通り | |
| カード \(i\) を箱 \(1\) に入れない場合 | ：\(D(n-1)\) 通り |
があり、この２つは排他的です。従って、
\(D(n)=(n-1)(D(n-1)+D(n-2))\)
の漸化式が得られます。\(D(1)=0,\:\:D(2)=1\) なので、
\(D(1)=0\)
\(D(2)=1\)
\(D(3)=2\cdot(1+0)=2\)
\(D(4)=3\cdot(2+1)=9\)
などとなります。
\(D(n)\) の一般項を求めるために漸化式を変形します。
\(D(n)=(n-1)(D(n-1)+D(n-2))\)
\(D(n)=nD(n-1)-D(n-1)+(n-1)D(n-2)\)
\(D(n)-nD(n-1)=-(D(n-1)-(n-1)D(n-2))\)
\(B(n)=D(n)-nD(n-1)\) とおくと、
\(B(2)=D(2)-2\cdot D(1)=1\)
\(B(n)=-B(n-1)\)
です。従って \(B(n)\) の一般項は、
\(B(n)=(-1)^n\)
であり、\(D(n)\) に戻すと、
\(D(n)-nD(n-1)=(-1)^n\)
になります。この両辺を \(n!\) で割ると、
\(\dfrac{D(n)}{n!}-\dfrac{D(n-1)}{(n-1)!}=(-1)^n\dfrac{1}{n!}\)
が得られます。この式の両辺を \(2\) から \(n\) までたし算して整理すると、
\(\dfrac{D(n)}{n!}-\dfrac{D(1)}{1!}\)
\(=\dfrac{1}{2!}-\dfrac{1}{3!}+\:\cd+(-1)^n\dfrac{1}{n!}\)
\(D(n)=n!\cdot\displaystyle\sum_{k=2}^{n}(-1)^k\dfrac{1}{k!}\)
となり、包除原理を使った計算（\(|P_{cp}(n)|\)）と一致します。
エレガントな解法ですが、漸化式を求めるのが難しい。特に「カード \(i\) を箱 \(1\) に入れない場合の数が \(D(n-1)\) である」ことをゼロから発想するのは大変でしょう。「カード \(i\) を箱 \(1\) に入れない」ということを「ルール上、カード \(1\) は箱 \(1\) に入れられない」と同一視する発想が必要です。また、漸化式から一般項を求める際にも、「式の変形」と「\(n!\) で割る」という、２つの "一般項生成テクニック" がポイントになっています。
ということで、本文では包除原理を使った説明にしました。この方がマッチング問題の本質をとらえています。
ただ、問題の本質をとらえた正攻法で "丹念に" 証明するしかないと "一見思える" 問題でも、漸化式という大変エレガントな解答がある。そのあたりに数学の深さの一端が現れていると思います。
2024-09-21 15:36
nice!(0)
