数学A / 場合の数

指定の数が定位置に来ない順列(包除原理)

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

問題

$1, 2, 3, 4, 5, 6$ を $1$ 列に並べる。 $1$ が $1$ 番目に、 $2$ が $2$ 番目に、 $3$ が $3$ 番目に来ることがいずれもないような並べ方は何通りあるか( $4, 5, 6$ の位置は問わない)。

ヒントを見る

「いずれも来ない」= 全体 −「少なくとも $1$ つは定位置に来る」。 $3$ つの条件に包除原理を使う。 $k$ 個の数を定位置に固定すると、残りは $(6 - k)!$ 通り。

解答・解説

方針

全体 $6!$ から「 $1$ が $1$ 番目」「 $2$ が $2$ 番目」「 $3$ が $3$ 番目」の少なくとも $1$ つが起こる並べ方を包除原理で引く。

解答

⓪ 発想 — どう考え始めるか。 「 $1$ が $1$ 番目・ $2$ が $2$ 番目・ $3$ が $3$ 番目のいずれもない」を直接数えるのは難しい。反対(少なくとも $1$ つ起こる)を包除で数える。

$A_{k}$ を「数 $k$ が $k$ 番目に来る並べ方」の集合とする( $k = 1, 2, 3$ )。 $∣ A_{1} \cup A_{2} \cup A_{3} ∣$ を包除原理で。

$j$ 個の位置を固定すると、残り $6 - j$ 個は自由で $(6 - j)!$ 通り。 $∣ A_{1} \cup A_{2} \cup A_{3} ∣ = (1 3) 5! - (2 3) 4! + (3 3) 3!$ 。全体 $6!$ から引く。

定理包除原理 —

∣ A \cup B \cup C ∣ = \sum ∣ A ∣ - \sum ∣ A \cap B ∣ + ∣ A \cap B \cap C ∣

① 部品を用意する。 $A_{i}$ を「数 $i$ が $i$ 番目に来る並べ方」とする( $i = 1, 2, 3$ )。 $k$ 個の条件を同時に満たす( $k$ 個を定位置に固定)並べ方は、残り $6 - k$ 個の並べ方で $(6 - k)!$ 通り。

$∣ A_{i} ∣ = 5! = 120$ ( $3$ 個)
$∣ A_{i} \cap A_{j} ∣ = 4! = 24$ ( $_{3} C_{2} = 3$ 組)
$∣ A_{1} \cap A_{2} \cap A_{3} ∣ = 3! = 6$ ( $1$ 組)

② 少なくとも $1$ つ起こる数(包除)。

$∣ A_{1} \cup A_{2} \cup A_{3} ∣ = 3 \cdot 120 - 3 \cdot 24 + 6 = 360 - 72 + 6 = 294$

③ 全体から引く。

$6! - 294 = 720 - 294 = 426 通り$

まとめ:「どの条件も成り立たない」は「全体 − 少なくとも $1$ つ成り立つ」。重なりを足し引きする包除原理が要。 $k$ 個を定位置に固定すると残りは自由に $(6 - k)!$ 、という部品を、条件の個数ごとに符号を変えて足し合わせる。

発展 — 一歩先へ。 全 $n$ か所に「 $k$ 番目に $k$ が来ない」を課すと完全順列 $D_{n} = n! \sum_{j = 0}^{n} \frac{( - 1 ) ^{j}}{j !}$ 。本問は $3$ か所だけの制限。「禁止位置」が任意に散らばる一般の問題は、禁止を表す盤面(ルーク多項式)で数えられ、包除原理の項がその盤面の配置数になる。

答

$426$ 通り

別解

別解 — 完全順列(かく乱順列)の一般化として捉える(得意な人向けの視点)。 「 $k$ 番目に $k$ が来ない」( $k = 1, 2, 3$ )だけを課し、 $4, 5, 6$ は自由。これは「 $3$ か所に禁止がある順列」で、包除原理の一般形で書ける。

禁止の集合 $A_{1}, A_{2}, A_{3}$ に対し、求める数は

$j = 0 \sum 3 (- 1)^{j} (j 3) (6 - j)! = 6! - 3 \cdot 5! + 3 \cdot 4! - 3! = 720 - 360 + 72 - 6 = 426.$

$j$ 個の位置を「 $k$ が $k$ 番目」に固定すると、残り $6 - j$ 個が自由で $(6 - j)!$ 、その選び方が $(j 3)$ 、符号が $(- 1)^{j}$ 。

もし全 $6$ か所に「 $k$ 番目に $k$ が来ない」を課せば、完全順列 $D_{6} = 265$ 。本問は $3$ か所だけの制限なので、 $4, 5, 6$ の分だけ自由度が増え $426$ になる。「一部の位置にだけ禁止」の順列は、包除の項数を禁止の数に合わせるだけで数えられる。

ポイント

$∣ A_{i} ∣ = 5!$ 、 $∣ A_{i} \cap A_{j} ∣ = 4!$ 、 $∣ A_{1} \cap A_{2} \cap A_{3} ∣ = 3!$ 。
$∣ A_{1} \cup A_{2} \cup A_{3} ∣ = 360 - 72 + 6 = 294$ 、 $6! - 294 = 426$ 。

よくある間違い

直接数えようとする(反対「少なくとも $1$ つ起こる」を包除で引く)。
包除の符号を交互にせず、 $(j 3) (6 - j)!$ を全部足す。
$4, 5, 6$ の位置に制限がない(自由)ことを見落とし、完全順列 $D_{6} = 265$ と混同する。