数学A / 場合の数

完全順列の漸化式

最難関編完全順列漸化式の導出

問題

$n$ 人が1個ずつプレゼントを持ち寄り、全員が自分の持ってきたもの以外のプレゼントを1個ずつ受け取る配り方の総数を $D_{n}$ とする( $D_{1} = 0, D_{2} = 1$ )。

(1) $n \geq 3$ のとき、 $D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})$ が成り立つことを示せ。

(2) $D_{6}$ を求めよ。

ヒントを見る

全体をいきなり数えず、1番の人の受け取る品で場合分けしてみる。その相手が1番の品を受け取るかどうかで、残りの状況は2種類 — どちらも「同じ問題の小さい版」と言い切れるか。特に「受け取らない」側の言い換えが勝負どころ。

解答・解説

方針

1番の人が誰の品を受け取るかで場合分けし(n−1通り)、さらにその相手が1番の品を受け取るかどうかで2つに割る。「受け取り合う」なら残りは人数が2減った同じ問題、「受け取らない」なら禁止先を付け替えると人数が1減った同じ問題になる。

解答

⓪ 発想 — どう考え始めるか。 $D_{6}$ を直接数え上げるのは現実的でない。数え上げの定石は、「最初の1手で場合分けし、残りを同じ形の小さい問題に帰着させて漸化式を作る」ことだ。

1番の人が受け取る品の持ち主を $k$ とする( $k$ は $n - 1$ 通り)。次の分かれ目は、「 $k$ 番の人が1番の品を受け取るか」。

受け取るなら、2人が品を交換して退場し、残りは $n - 2$ 人の同じ問題。受け取らないなら、 $k$ 番の人の「受け取ってはいけない品」を付け替えることで、 $n - 1$ 人の同じ問題に化ける。この言い換えが急所だ。

重要数え上げの漸化式: 最初の選択で場合分けし、残りの状況を「同じ問題の小さい版」に言い換える。言い換えの1対1対応が正しさの根拠

① 場合分けの枠組み((1)の証明)。 1番の人が $k$ 番の人の品を受け取るとする。 $k$ の選び方は $2$ 〜 $n$ の $n - 1$ 通りで、どの $k$ でも以下の勘定は同じだから、最後に $n - 1$ 倍すればよい。

② $k$ 番の人が1番の品を受け取る場合。 1番と $k$ 番は品を交換して確定。残る $n - 2$ 人は、自分の品以外を受け取る同じ問題そのもの。配り方は $D_{n - 2}$ 通り。

③ $k$ 番の人が1番の品を受け取らない場合。 残っている品は「1番の品」と「 $k$ 番以外の $n - 2$ 人の品」。受け取る人は「 $k$ 番」と「1番・ $k$ 番以外の $n - 2$ 人」だ。ここで $k$ 番の人にとって禁止されているのは1番の品だけ。そこで、1番の品に「 $k$ 番の品」と名札を付け替える。すると「 $n - 1$ 人がそれぞれ自分の名札の品を受け取らない」完全順列そのものになる(付け替えは1対1の言い換えで、数は変わらない)。よって $D_{n - 1}$ 通り。

②と③は排反ですべてを尽くすから

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

④ $D_{6}$ を計算する((2)の答え)。 $D_{1} = 0, D_{2} = 1$ から

$D_{3} = 2 (1 + 0) = 2, D_{4} = 3 (2 + 1) = 9, D_{5} = 4 (9 + 2) = 44$

$D_{6} = 5 (44 + 9) = 5 \cdot 53 = 265$

まとめ: 「交換して2人退場( $D_{n - 2}$ )」と「禁止先の付け替えで1人減( $D_{n - 1}$ )」。この2つの帰着が完全順列の漸化式の心臓部だ。漸化式さえ立てば、 $D_{6}$ は足して掛けるだけで届く。

発展 — 一歩先へ。 $\frac{D _{6}}{6 !} = \frac{265}{720} = 0.3680 \dots$ 。この「誰も自分の品を受け取らない確率」は、人数を増やしても約 $36.8%$ ( $\frac{1}{e}$ 、 $e$ は自然対数の底)に張りつく。プレゼント交換の失敗率は、6人でもう極限とほぼ同じなのだ。

答

(1) 1番の人の受け取る品で場合分けして帰着(証明) (2) $D_{6} = 265$

別解

包除原理で一撃の式を作る(得意な人向け)。 漸化式を経由せず、 $D_{n}$ を閉じた式で出す道もある。

「少なくとも1人が自分の品を受け取る」場合を包除原理で除く。自分の品を受け取る人の集合を $j$ 人指定すると、その $j$ 人は確定し、残り $n - j$ 人は自由だから $(n - j)!$ 通り。指定のしかたは $_{n} C_{j}$ 通り。符号を交互につけて

$D_{n} = j = 0 \sum n (- 1)^{j}_{n} C_{j} (n - j)! = n! (1 - \frac{1}{1 !} + \frac{1}{2 !} - \dots + (- 1)^{n} \frac{1}{n !})$

$n = 6$ で計算すると

$720 (\frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120} + \frac{1}{720}) = 360 - 120 + 30 - 6 + 1 = 265$

漸化式(本解)は「隣とつなぐ」、包除は「一気に書き下す」。同じ265に、性格の違う2本の道が通じている。交互に符号のつく和の形は、そのまま $\frac{1}{e}$ への収束(発展)の理由にもなっている。

ポイント

1番の受け取る品の持ち主 $k$ で場合分け( $n - 1$ 通り)。
$k$ が1番の品を受け取るなら $D_{n - 2}$ 、受け取らないなら名札の付け替えで $D_{n - 1}$ 。
$D_{3} = 2, D_{4} = 9, D_{5} = 44, D_{6} = 265$ 。

よくある間違い

「受け取り合う」場合( $D_{n - 2}$ )を落として $D_{n} = (n - 1) D_{n - 1}$ としてしまう。2つの場合は排反で両方要る。
③の名札の付け替えが1対1であること(数が変わらないこと)を言わずに $D_{n - 1}$ と断定する。ここが証明の資格。
初期値を $D_{1} = 1$ などと置く。1人が自分の品以外を受け取る方法は存在しない( $D_{1} = 0$ )。 $D_{2} = 1$ (交換の1通り)とセットで確認。