数学A / 確率

完全順列(プレゼント交換)

★★★★ 難関包除原理順列

問題

何人かで $1$ 個ずつプレゼントを持ち寄り、全員に $1$ 個ずつ無作為に配り直す。

(1) $4$ 人のとき、誰も自分のプレゼントを受け取らない確率を求めよ。

(2) $5$ 人のとき、誰も自分のプレゼントを受け取らない確率を求めよ。

ヒントを見る

『少なくとも $1$ 人が自分の物』を直接数えるのは重なりだらけで難しい — 『自分の物を受け取る人の集合』で場合分けする包除の出番だ。まず $4$ 人で構造をつかめ。

解答・解説

方針

「誰も自分の物を受け取らない」の反対は「少なくとも $1$ 人が自分の物を受け取る」。人 $k$ が自分の物を受け取る場合の集合を $A_{k}$ とし、包除原理で $∣ A_{1} \cup \dots \cup A_{n} ∣$ を数えて全体から引く。

解答

⓪ 発想 — どう考え始めるか。 「誰も自分の物を受け取らない」を正面から数えるのは難しい。反対を数える。

反対は「少なくとも $1$ 人が自分の物を受け取る」。人 $k$ が自分の物を受け取る場合の集合を $A_{k}$ として、 $∣ A_{1} \cup \dots \cup A_{n} ∣$ を包除原理で数える。

包除原理では「 $1$ 人固定」「 $2$ 人固定」…と、 $j$ 人が自分の物を受け取る場合を $(j n) (n - j)!$ で数え、符号を交互につけて足す。全体 $n!$ から引けば、誰も自分の物を受け取らない場合(完全順列)の数が出る。

定理包除原理:

∣ A \cup B \cup C ∣ = \sum ∣ A_{i} ∣ - \sum ∣ A_{i} \cap A_{j} ∣ + ∣ A_{1} \cap A_{2} \cap A_{3} ∣ - \dots

(符号を交互に)

① 数える対象を決める。 配り方の総数は $4$ 人なら $4! = 24$ 通りで、どれも同様に確からしい。人 $k$ が自分の物を受け取る配り方の集合を $A_{k}$ とすると、求めるのは「どの $A_{k}$ にも入らない」配り方の割合である。

② (1) 包除原理で数える。 $i$ 人を固定して自分の物を受け取らせると、残りは自由だから

$∣ A_{k} ∣ = 3!$ が $(1 4) = 4$ 個
$∣ A_{j} \cap A_{k} ∣ = 2!$ が $(2 4) = 6$ 個
$3$ 人交わりは $1!$ が $(3 4) = 4$ 個、 $4$ 人交わりは $0! = 1$ が $1$ 個

少なくとも $1$ 人が自分の物を受け取る配り方は

$4 \cdot 3! - 6 \cdot 2! + 4 \cdot 1! - 1 = 24 - 12 + 4 - 1 = 15$

よって誰も受け取らないのは $24 - 15 = 9$ 通りで、確率は $\frac{9}{24} = \frac{3}{8}$ 。

③ (2) 同じ構造で $5$ 人。 総数は $5! = 120$ 。同様に

$120 - ((1 5) 4! - (2 5) 3! + (3 5) 2! - (4 5) 1! + (5 5) 0!)$

$= 120 - (120 - 60 + 20 - 5 + 1) = 120 - 76 = 44$

よって確率は $\frac{44}{120} = \frac{11}{30}$ 。

まとめ:「全員が外れる」順列(完全順列)の個数は、 $n! (1 - \frac{1}{1 !} + \frac{1}{2 !} - \dots + \frac{( - 1 ) ^{n}}{n !})$ という交代和になる。 $4$ 人で $9$ 、 $5$ 人で $44$ — この $2$ つの数は覚えておくと検算が速い。

発展 — 一歩先へ。 完全順列の確率 $\frac{D _{n}}{n !} = k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}$ は、 $n \to \infty$ で $e^{- 1} \approx 0.368$ に収束する。だから人数が多くても「誰も自分の物を受け取らない」確率は約 $37%$ で、 $n$ にほとんどよらない。プレゼント交換で全員が他人の物になる確率が、人数によらずほぼ一定、という意外な事実だ。

答

(1) $\frac{3}{8}$ (2) $\frac{11}{30}$

別解

別解 — 完全順列の漸化式で数える(得意な人向けの高い視点)。 完全順列の個数 $D_{n}$ (誰も自分の位置に来ない並べ方)には、きれいな漸化式がある。

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

(理由: $1$ 番の人が受け取る品を $k$ 番とすると $n - 1$ 通り。 $k$ 番の人が $1$ 番の品を受け取るか否かで $D_{n - 2}$ と $D_{n - 1}$ に分かれる。)

順に計算すると $D_{3} = 2 \cdot (1 + 0) = 2$ 、 $D_{4} = 3 \cdot (2 + 1) = 9$ 、 $D_{5} = 4 \cdot (9 + 2) = 44$ 。

確率は $\frac{D _{4}}{4 !} = \frac{9}{24} = \frac{3}{8}$ 、 $\frac{D _{5}}{5 !} = \frac{44}{120} = \frac{11}{30}$ 。

包除原理(本解)で $D_{n} = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}$ と一発で書けるが、漸化式なら小さい $n$ から手計算で積み上げられる。 $\frac{D _{n}}{n !} \to \frac{1}{e} \approx 0.368$ に近づくのも、この $\sum \frac{( - 1 ) ^{k}}{k !}$ が $e^{- 1}$ の展開だからだ。

ポイント

「少なくとも $1$ 人」は包除原理:選んだ人数ごとに $(i n) (n - i)!$ を交互に足し引き。
完全順列の個数: $4$ 人で $9$ 、 $5$ 人で $44$ 。

よくある間違い

「誰も自分の物を受け取らない」を直接数えようとして場合が爆発する(反対=包除で攻める)。
包除原理の符号を交互にせず、 $j$ 人固定の項を全部足してしまう。
$(j n) (n - j)!$ の $(n - j)!$ (残りの自由な並べ方)を誤る。