攪乱順列

包除原理で攪乱順列の個数 $D_{n} = n! \sum_{k = 0}^{n} \frac{( - 1 ) ^{k}}{k !}$ を導き、漸化式 $D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})$ で $D_{n}$ を求められる。指定した $m$ 個の要素だけに $σ (i) \neq = i$ を課す $n$ 文字の置換の個数を $\sum_{k = 0}^{m} (- 1)^{k} (k m) (n - k)!$ で求められる

前提

一般の包除原理（大学数学離散数学・組合せ論）

この技能までの道筋（9 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
包除原理（数学A 場合の数と確率）
同じものを含む順列・重複組合せ（数学A 場合の数と確率）
一般の包除原理（大学数学離散数学・組合せ論）

説明

$1, 2, \dots, n$ の並べ替え（置換） $σ$ のうち、すべての $i$ について $σ (i) \neq = i$ となるもの、つまりどの要素も元の位置に来ないものを攪乱順列（完全順列）といい、その個数を $D_{n}$ と書きます。この技能では、包除原理から $D_{n}$ の公式を導き、漸化式を使って $D_{n}$ を順に計算します。プレゼント交換で誰も自分の品を受け取らない配り方や、手紙をすべて宛先違いの封筒に入れる入れ方の数がこれにあたります。また、指定した一部の要素だけに「元の位置に来ない」という条件を課した場合の個数も求められます。

なぜそうしてよいのか

$n$ 文字の置換は全部で $n!$ 個あります。 $A_{i}$ を「 $σ (i) = i$ となる置換の集合」とすると、攪乱順列の集合は $A_{1} \cap \dots \cap A_{n}$ です。 $∣ I ∣ = k$ となる添字の集合 $I$ をとると、 $I$ に属する $k$ 個の要素は行き先が自分自身に決まり、残りの $n - k$ 個は自由に並べ替えられます。よって $⋂_{i \in I} A_{i} = (n - k)!$ です。この値は $I$ の選び方によらない（対称な条件）ので、包除原理の $\sum_{k} (- 1)^{k} (k n) N_{k}$ の形に $N_{k} = (n - k)!$ を入れて $D_{n} = k = 0 \sum n (- 1)^{k} (k n) (n - k)! = k = 0 \sum n (- 1)^{k} \frac{n !}{k !} = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}$ が得られます。 $n = 0$ のときは空の並べ替えが 1 個あると考えて $D_{0} = 1$ とします。

漸化式は場合分けで導きます。 $n \geq 2$ とし、攪乱順列 $σ$ で $σ (n) = i$ とします。 $i \neq = n$ なので $i$ の選び方は $n - 1$ 通りです。
(a) $σ (i) = n$ のとき： $i$ と $n$ が入れ替わっていて、残りの $n - 2$ 個はその中で攪乱順列になるので $D_{n - 2}$ 通りです。
(b) $σ (i) \neq = n$ のとき： ${1, \dots, n - 1}$ 上の置換 $τ$ を、 $σ (j) = n$ となる $j$ については $τ (j) = i$ 、それ以外の $j$ については $τ (j) = σ (j)$ と定めます。 $σ (i) \neq = n$ より $σ (j) = n$ となる $j$ は $i$ と異なるので、 $τ (j) = i \neq = j$ です。また $τ (i) = σ (i) \neq = i$ です。したがって $τ$ は $n - 1$ 文字の攪乱順列です。この対応は逆にたどれる 1 対 1 対応なので、 $D_{n - 1}$ 通りです。
以上より $D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})$ （ $n \geq 2$ ）が成り立ち、 $D_{0} = 1, D_{1} = 0$ から順に計算できます。

指定した $m$ 個の要素（ $0 \leq m \leq n$ ）だけに条件を課す場合も、考え方は同じです。条件が $m$ 個なので、そのうち $k$ 個を選ぶ方法は $(k m)$ 通りです。選んだ $k$ 個を固定すると、残りの $n - k$ 個は自由に並べられるので $(n - k)!$ 通りです。したがって個数は $\sum_{k = 0}^{m} (- 1)^{k} (k m) (n - k)!$ となります。 $m = n$ のときは $D_{n}$ に一致します。

手順

問題を「 $n$ 個の要素を並べ替え、指定された要素 $i$ を位置 $i$ に置かない」形に言い換え、条件が課される要素の個数（全部なら $n$ 、一部なら $m$ ）を確認する
全要素に条件があるときは公式 $D_{n} = \sum_{k = 0}^{n} (- 1)^{k} \frac{n !}{k !}$ に代入する。 $k = 0$ から $k = n$ まで全項を取り、各項 $\frac{n !}{k !}$ は整数なので整数のまま計算する
初期値 $D_{1} = 0, D_{2} = 1$ から漸化式 $D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})$ で順に求め、公式の結果と照合する
指定した $m$ 個だけに条件があるときは $\sum_{k = 0}^{m} (- 1)^{k} (k m) (n - k)!$ を計算する

例題

5 人が 1 つずつプレゼントを持ち寄り、5 個のプレゼントを 1 人 1 個ずつ配り直す。どの人も自分が持ってきたプレゼントを受け取らない配り方の総数を求めよ。

例題の解答

手順 1: 人に $1, \dots, 5$ の番号を付け、各人のプレゼントにも同じ番号を付けます。すると配り方は 5 文字の置換 $σ$ （人 $i$ がプレゼント $σ (i)$ を受け取る）として表せます。全員について $σ (i) \neq = i$ を課すので、求める数は $D_{5}$ です。

手順 2: $k = 0$ から $5$ までの全項を取って公式に代入します。 $D_{5} = \frac{5 !}{0 !} - \frac{5 !}{1 !} + \frac{5 !}{2 !} - \frac{5 !}{3 !} + \frac{5 !}{4 !} - \frac{5 !}{5 !} = 120 - 120 + 60 - 20 + 5 - 1 = 44$

手順 3: 漸化式で確かめます。 $D_{1} = 0, D_{2} = 1$ から
$D_{3} = 2 (D_{2} + D_{1}) = 2 (1 + 0) = 2$
$D_{4} = 3 (D_{3} + D_{2}) = 3 (2 + 1) = 9$
$D_{5} = 4 (D_{4} + D_{3}) = 4 (9 + 2) = 44$
となり、手順 2 の結果と一致します。

よって配り方は $44$ 通りです。

答え: $44$

よくある誤り

$k$ 個を固定する場合の数を $(n - k)!$ だけにして、 $k$ 個の選び方 $(k n)$ を掛け忘れる誤り。 $n = 3$ なら $3! - 2! + 1! - 0! = 6 - 2 + 1 - 1 = 4$ となってしまう。正しくは $D_{3} = (0 3) 3! - (1 3) 2! + (2 3) 1! - (3 3) 0! = 6 - 6 + 3 - 1 = 2$
漸化式の初期値を $D_{1} = 1$ としてしまう誤り。1 文字の置換は $σ (1) = 1$ しかなく、条件を満たすものはない。正しくは $D_{1} = 0, D_{2} = 1$ （または $D_{0} = 1, D_{1} = 0$ ）から始める
一部の $m$ 個だけに条件があるのに、選び方を $(k n)$ にしたり、和を $k = n$ まで取ったりする誤り。例えば $n = 4$ で要素 $1, 2$ だけに $σ (i) \neq = i$ を課す場合、正しくは $(0 2) 4! - (1 2) 3! + (2 2) 2! = 24 - 12 + 2 = 14$
和の上限を $n - 1$ までにして、最後の項 $(- 1)^{n} \frac{n !}{n !} = (- 1)^{n}$ を落とす誤り。 $n = 5$ なら $120 - 120 + 60 - 20 + 5 = 45$ となってしまう。正しくは $k = n$ の項 $- \frac{5 !}{5 !} = - 1$ まで含めて $D_{5} = 44$

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

禁止位置のある順列とルーク多項式（大学数学離散数学・組合せ論）