禁止位置のある順列とルーク多項式

禁止されたマスの集まり（盤）に、どの 2 個も同じ行・列にない $k$ 個のルークを置く方法の数 $r_{k}$ を求め、禁止位置をすべて避ける置換の個数を $\sum_{k} (- 1)^{k} r_{k} (n - k)!$ で求められる（夫婦が自分・配偶者のプレゼントを受け取らない配り方など）

前提

攪乱順列（大学数学離散数学・組合せ論）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

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

説明

ある要素がある位置に行ってはいけない、という制限（禁止位置）が要素ごとにばらばらに与えられたとき、制限をすべて守る並べ方（置換）の個数を数える方法です。禁止されたマスの集まりを「盤」とみなし、そこに互いに取り合わないルーク（同じ行・同じ列に 2 個置かない駒）を $k$ 個置く方法の数 $r_{k}$ を求めます。すると答えは $\sum_{k} (- 1)^{k} r_{k} (n - k)!$ で求まります。攪乱順列は「対角線だけが禁止」という特別な場合で、夫婦のプレゼント交換や席替えのように禁止が複数ある問題にも使えます。

なぜそうしてよいのか

$n$ 個の要素 $1, \dots, n$ の置換 $σ$ を、 $n \times n$ のマス目に「 $i$ 行 $σ (i)$ 列」に印を付けたものと考えます。各行・各列にちょうど 1 個ずつ印が入ります。禁止位置とは「 $σ (i) = j$ になってはいけない」マス $(i, j)$ のことで、その集まりを盤 $B$ とよびます。禁止マス $c = (i, j)$ ごとに、事象 $E_{c}$ を「 $σ (i) = j$ となる置換全体」とします。求めたいのは、どの $E_{c}$ にも入らない置換の個数です。

包除原理を使うには、禁止マスをいくつか選んだ集合 $S$ について $⋂_{c \in S} E_{c}$ が要ります。 $S$ の中に同じ行のマスが 2 つあると、 $σ (i)$ が 2 つの値をとることになって 0 個です。同じ列のマスが 2 つあると $σ$ が単射でなくなるので、これも 0 個です。 $S$ のどの 2 マスも行・列を共有しないとき、つまり $S$ が互いに取り合わない $∣ S ∣ = k$ 個のルークの配置のときは、 $k$ 個の値が決まり、残り $n - k$ 個の要素を残り $n - k$ 個の値に自由に並べられます。よって $(n - k)!$ 個です。そのような $S$ は $r_{k}$ 通りあるので、包除原理から
$N = k = 0 \sum n (- 1)^{k} r_{k} (n - k)!$
となります。 $k = 0$ は何も置かない 1 通りなので $r_{0} = 1$ です。対角線だけが禁止の盤では、対角線から $k$ マスを選べば必ず互いに取り合わないので $r_{k} = (k n)$ となり、攪乱順列の公式に戻ります。

$r_{k}$ を数えやすくする道具が「ルーク多項式」 $R_{B} (x) = \sum_{k} r_{k} x^{k}$ です。盤 $B$ が、互いに行も列も共有しない 2 つの部分 $B_{1}, B_{2}$ に分かれているとします。このとき $B$ への配置は、「 $B_{1}$ への配置」と「 $B_{2}$ への配置」を自由に組み合わせたものと 1 対 1 に対応します（片方のルークがもう片方を取ることはないからです）。積の法則から $r_{k} (B) = \sum_{i} r_{i} (B_{1}) r_{k - i} (B_{2})$ となり、これは多項式の積の係数そのものです。よって $R_{B} (x) = R_{B_{1}} (x) R_{B_{2}} (x)$ が成り立ちます。

手順

盤を作る：行を要素 $i$ 、列を行き先 $j$ とする $n \times n$ のマス目で、 $σ (i) = j$ が禁止のマス $(i, j)$ に印を付ける。印の集まりが盤 $B$ である。
盤を分ける：行も列も互いに共有しない小さな部分 $B_{1}, B_{2}, \dots$ に分けられるなら分ける（行や列の番号を並べ替えて、ブロック状に見える形にするとよい）。
各部分の $r_{k}$ を数える：小さな部分では、同じ行・列に 2 個置かないルーク $k$ 個の置き方を直接数える（ $r_{0} = 1$ ）。たとえば $2 \times 2$ のマスがすべて禁止なら $1 + 4 x + 2 x^{2}$ となる。
ルーク多項式を掛ける： $R_{B} (x) = R_{B_{1}} (x) R_{B_{2}} (x) \dots$ を展開し、 $x^{k}$ の係数として $r_{k}$ を読み取る。展開の検算には、 $x = 1$ を代入した値が各部分の $R (1)$ の積に一致することを使える。
公式に代入する： $N = \sum_{k = 0}^{n} (- 1)^{k} r_{k} (n - k)!$ を計算する。

例題

3 組の夫婦、計 6 人がそれぞれプレゼントを 1 つずつ持ち寄り、6 個のプレゼントを 1 人 1 個ずつ受け取るように配り直す。どの人も、自分が持ってきたプレゼントと配偶者が持ってきたプレゼントは受け取らないとする。このような配り方は何通りあるか求めよ。

例題の解答

【手順1】6 人を $a_{1}, a_{2}$ （1 組目の夫婦）、 $b_{1}, b_{2}$ 、 $c_{1}, c_{2}$ とし、プレゼントにも持ってきた人と同じ名前を付けます。行を人、列をプレゼントとすると、禁止マスは ${a_{1}, a_{2}} \times {a_{1}, a_{2}}$ 、 ${b_{1}, b_{2}} \times {b_{1}, b_{2}}$ 、 ${c_{1}, c_{2}} \times {c_{1}, c_{2}}$ の合計 12 マスです。

【手順2】この 3 つの $2 \times 2$ ブロックは、どの 2 つも行も列も共有しません。よって盤は 3 つの部分 $B_{1}, B_{2}, B_{3}$ に分かれます。

【手順3】 $2 \times 2$ の全マスからなる盤では、ルーク 0 個の置き方が 1 通り、1 個の置き方が 4 通りです。2 個の置き方は、同じ行・列を避けて対角の 2 マスを選ぶことになるので 2 通りです。3 個以上は置けません。よって $R_{B_{i}} (x) = 1 + 4 x + 2 x^{2}$ です。

【手順4】まず 2 つ分を掛けます。
$(1 + 4 x + 2 x^{2})^{2} = 1 + 8 x + 20 x^{2} + 16 x^{3} + 4 x^{4}$
これにもう一度 $1 + 4 x + 2 x^{2}$ を掛けると、
$R_{B} (x) = 1 + 12 x + 54 x^{2} + 112 x^{3} + 108 x^{4} + 48 x^{5} + 8 x^{6}$
となります。検算として係数の和を計算すると $1 + 12 + 54 + 112 + 108 + 48 + 8 = 343 = 7^{3}$ で、 $R_{B_{i}} (1) = 7$ の 3 乗に一致します。

【手順5】 $n = 6$ として公式に代入します。
$N = 6! - 12 \cdot 5! + 54 \cdot 4! - 112 \cdot 3! + 108 \cdot 2! - 48 \cdot 1! + 8 \cdot 0!$
$= 720 - 1440 + 1296 - 672 + 216 - 48 + 8 = 80$
したがって、配り方は 80 通りです。

答え: $80$

よくある誤り

$r_{k}$ を「盤のマス $∣ B ∣$ 個から $k$ 個選ぶ」 $(k ∣ B ∣)$ としてしまう誤り。正しくは、同じ行・列にあるマスを同時に選ぶ配置は除く。たとえば $2 \times 2$ の全マスの盤では $(2 4) = 6$ ではなく $r_{2} = 2$ である。
行か列を共有している部分どうしのルーク多項式を掛けてしまう誤り。たとえばマス $(1, 1)$ と $(1, 2)$ を別々の 1 マスの盤とみて $(1 + x)^{2}$ とすると $r_{2} = 1$ になる。正しくは同じ行にあるので $r_{2} = 0$ で、 $R (x) = 1 + 2 x$ である。積に分けてよいのは、行も列も共有しないときだけ。
$k = 0$ の項を落としてしまう誤り。何も置かない配置が 1 通りあるので $r_{0} = 1$ であり、和は $+ n!$ から始まる。例題でも先頭の $720$ を忘れると答えが合わない。
$(n - k)!$ の $n$ を、盤に現れる行の数や禁止マスの個数にしてしまう誤り。正しくは $n$ は並べる要素全体の個数である。たとえば 6 人のうち 2 人だけに禁止がある場合でも、使うのは $(6 - k)!$ である。

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

禁止位置のある順列とルーク多項式

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題