【期待値マスター講座43】モンモール数の漸化式と確率1/eへの収束を理解する

この記事では、「だれも自分のカードを受け取らない」並べ方の総数 ${D_n}$ について、漸化式 ${D_n = (n-1)(D_{n-1} + D_{n-2})}$ を立てます。

第IV部・第V部のヒット問題の「ヒット0」のケースを正面から数える、組合せ論の古典題です。

公式LINEでテキスト配布中
公式LINE追加→ 期待値テキスト と送信
で120ページ超えのテキストを自動送信！
ㅤ
無料勉強相談も受付中
学習相談も受け付けています。
ゴウカライズは情報の少ない獣医学部や医学部受験にも精通しています。
一般入試はもちろん、総合型選抜や推薦など、なんでもお問い合わせください！

シリーズ全体の流れを先に見たい方は、まず 期待値マスター講座の導入記事 からどうぞ。全56回の構成と読み進め方をまとめています。

https://note.com/goukalize/n/n9de4e3c6c4fb

完全順列とは

$${n}$$ 人がそれぞれ自分の名前を書いたカードを集めて、ランダムに1枚ずつ配り直すとき、 「全員が自分以外のカードを受け取る」並べ方 を 完全順列 と呼びます。

その総数を $${D_n}$$ と書きます。 $${D_n}$$ は モンモール数 とも呼ばれ、組合せ論で古典的な対象です。

便宜上、 $${D_0 = 1}$$ と定義します。「0人の完全順列は1通り」と見る空配置の約束で、後の漸化式や級数表現で必要になる規約です。

漸化式

定理：$${n\ge 3}$$ で

$$
D_n = (n-1)(D_{n-1} + D_{n-2}).
$$

境界条件は $${D_1 = 0, D_2 = 1}$$。

導出

人 $${1}$$ がカード $${k\in{2, 3, \ldots, n}}$$ を受け取ったとする（ $${n-1}$$ 通り）。このとき、

ケース1：人 $${k}$$ がカード $${1}$$ を受け取る

人1と人 $${k}$$ が「お互いのカードを交換した」状態。残りの $${n-2}$$ 人について、それぞれ自分のカードを受け取らないように配るパターンは $${D_{n-2}}$$ 通り。

ケース2：人 $${k}$$ がカード $${1}$$ を受け取らない

人 $${k}$$ にとってカード $${1}$$ が「自分以外のカード」の代わりになります。 $${k}$$ を「もとのカード $${1}$$ を受け取る役」と見立てると、人 $${2, 3, \ldots, n}$$ の $${n - 1}$$ 人で完全順列を作る話に帰着します。これは $${D_{n-1}}$$ 通り。

合計

$$
D_n = (n - 1)(D_{n-1} + D_{n-2}).
$$

小さな $${n}$$ での値

漸化式を使って計算します。

• $${D_0 = 1}$$
• $${D_1 = 0}$$
• $${D_2 = 1}$$
• $${D_3 = 2\cdot (D_2 + D_1) = 2\cdot (1 + 0) = 2}$$
• $${D_4 = 3\cdot (D_3 + D_2) = 3\cdot 3 = 9}$$
• $${D_5 = 4\cdot (D_4 + D_3) = 4\cdot 11 = 44}$$
• $${D_6 = 5\cdot (D_5 + D_4) = 5\cdot 53 = 265}$$

確認：$${n = 3}$$ で $${D_3 = 2}$$ は、 $${(2, 3, 1)}$$ と $${(3, 1, 2)}$$ の2通り（巡回的にずらした並び）。たしかに2通りで合っています。

「だれも当たらない」確率

カードの配り方は $${n!}$$ 通りで等確率。完全順列が $${D_n}$$ 通りなので、ヒットが0になる確率は

$$
P(X = 0) = \frac{D_n}{n!}.
$$

包除原理を経由すると

$$
\frac{D_n}{n!} = \sum_{k=0}^{n}\frac{(-1)^k}{k!}.
$$

$${n\to\infty}$$ では、これがマクローリン展開 $${e^{-1} = \sum_{k=0}^{\infty}\frac{(-1)^k}{k!}}$$ に近づいて

$$
\frac{D_n}{n!}\to e^{-1}\approx 0.368.
$$

「 $${n}$$ が大きいとき、 だれも自分のカードを受け取らない確率は約37% 」というのは、感覚的にとらえやすい結論です。

$${E(X) = 1}$$ と $${P(X = 0) \approx 0.368}$$ の両立

シリーズ第V部の記事31で、ヒット数 $${X}$$ の期待値 $${E(X) = 1}$$ と分散 $${V(X) = 1}$$（ $${n\ge 2}$$ ）を出しました。一方、ここで見た $${P(X = 0) \approx 0.368}$$。

「平均1人が自分のカードを受け取るのに、約37%の確率で0人」というのは、 分布が右に長い尾を持つ偏った形 をしていることを意味します。

実際、 $${n}$$ が大きいとき $${X}$$ は近似的に 平均1のポアソン分布 に従います。ポアソン分布 $${\mathrm{Po}(1)}$$ では $${P(X = k) = \frac{e^{-1}}{k!}}$$ で、 $${k = 0}$$ で $${e^{-1}\approx 0.368}$$、 $${k = 1}$$ で同じく $${0.368}$$、 $${k = 2}$$ で $${0.184}$$、…という分布。 $${X = 0}$$ と $${X = 1}$$ が同程度に大きく、 $${X}$$ が大きい値はかなりまれ、という非対称な振る舞いです。

漸化式が効いた理由

ヒット数 $${X}$$ の 期待値 $${E(X) = 1}$$ は、指示関数 $${+}$$ 線形性で2行で出ました。 数 $${D_n}$$ そのものは、対象ごとの $${0/1}$$ 変数の和には書けないので、漸化式で順に計算する必要があります。

「期待値は線形性」「個数は漸化式」という、 求めたいものに応じて道具を切り替える 必要が、この問題では顕著に出ています。

練習問題

5人のプレゼント交換で、だれも自分のプレゼントを受け取らない並べ方は何通りあるか。

$${D_5 = 44}$$ 通り。全 $${5! = 120}$$ 通りのうちの $${\frac{44}{120}\approx 36.7}$$ % が「だれも当たらない」並べ方です。 $${e^{-1}\approx 0.368}$$ にすでに近い値であることに注目してください。 $${n = 5}$$ でも近似が十分よく効いている、というのが感覚的なメッセージです。

補足：包除原理経由の式

$${D_n}$$ の閉じた式は

$$
D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}.
$$

包除原理から出ます。 $${A_i}$$ を「人 $${i}$$ が自分のカードを受け取る事象」とすると

$$
|\overline{A_1}\cap \cdots \cap \overline{A_n}| = n! - |A_1\cup \cdots\cup A_n|
$$

で、包除原理を展開すると

$$
|A_1\cup \cdots\cup A_n| = \sum_{k=1}^{n}(-1)^{k-1}\binom{n}{k}(n-k)!.
$$

$${\binom{n}{k}(n-k)! = \frac{n!}{k!}}$$ なので

$$
D_n = n! - \sum_{k=1}^{n}(-1)^{k-1}\frac{n!}{k!} = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}.
$$

漸化式と閉じた式の両方が知られているのが、モンモール数の特徴です。

次に読む記事

次回は、 コイン投げで初めて表が出るまでの回数 の期待値を、漸化式で扱います。記事42の導入で軽く触れた問題を、もう少し丁寧に整理します。

【無料相談受付中】学習マネジメントはゴウカライズにおまかせを！

「成績が伸び悩んでいるけどどうやって打破すればいいかわからない…」
「塾・予備校に行ってるけど、全体の成績が思ったように上がらない…」

そんな悩みをお持ちの受験生・保護者の皆様、ゴウカライズにご相談ください！

入試を突破するため、私たちはあなたの志望校や受験方式に必要なすべてをトータルサポートします。

【一般入試】完全オーダーメイドの学習計画 ：
入試は、わずかな失点が合否を分けることもあります。
あなたの現状と志望校の出題傾向を分析し、合格ラインに到達するための最短ルートを設計。
日々の進捗管理で、学習の遅れも見逃しません。

【推薦・総合型選抜】面接・小論文もプロが対応 ：
推薦入試や総合型選抜で必須となる「面接・小論文・志望理由書」の対策もお任せください。
医学部や獣医系特有のテーマ（動物倫理や獣医療時事など）に対応できるプロ講師が、合格レベルの答案作成と受け答えを指導します。

プロ講師・優秀学生講師の個別指導 ：
学習管理だけでなく、経験豊富なプロ講師や、高倍率から選抜された優秀な学生講師による完全個別指導も提供。
苦手科目の克服や過去問解説など、あなたのニーズに合わせた1対1の指導が可能です。

【医学部・獣医学部対策】特殊な対策に完全対応 ：
医学部入試、獣医学部入試は特殊な対策が必要です。
面接などがある入試形式の場合、面接対策も侮れません。
そんな入試に精通したプロがゴウカライズには多数在籍しています。
ゴウカライズ代表の大北も医学部・獣医学部受験の指導経験は15年を超える大ベテランです。

まずは無料相談で、あなたの合格までのロードマップを一緒に描きませんか？
無理な勧誘は一切ありません。
予備校選びに迷っているなどの相談でも、客観的にアドバイスを行います。

公式LINEでいつでも無料相談を受け付けています！

https://goukalize.com/

https://goukalize-official-line-harness.tiny-atlas.workers.dev/r/Expected-Value

#オンライン予備校 #大学受験 #数学 #モンモール #漸化式