離散数学・組合せ論の問題

方針 割り当て方は、学生 $\{A,B,C,D\}$ から係 $\{1,2,3,4\}$ への全単射、つまり $4$ 文字の置換に対応する。禁止位置をすべて避ける置換の個数は、包除原理により
$$N=\sum _{k=0}^4(-1{)}^k{r}_k(4-k)!$$
で求められる。ここで $r_k$ は禁止マスの盤 $B$ に互いに攻撃し合わない $k$ 個のルークを置く方法の数である（$k$ 個の禁止マスを同時に使う割り当てが $(4-k)!$ 通りあるため）。

盤 $B$ 禁止マスは $(A,1),(A,2),(B,2),(C,3),(C,4),(D,4)$ の $6$ マス。

$r_k$ の計算
- $r_0=1$。
- $r_1=6$（禁止マスの個数）。
- $r_2$：$6$ マスから $2$ マス選ぶ方法は ${}_6{\mathrm{C}}_2=15$ 通り。このうち同じ行にあるもの $\{(A,1),(A,2)\},\{(C,3),(C,4)\}$ の $2$ 組、同じ列にあるもの $\{(A,2),(B,2)\},\{(C,4),(D,4)\}$ の $2$ 組を除いて $r_2=15-4=11$。
- 盤は、行 $A,B$・列 $1,2$ の部分 $B_1=\{(A,1),(A,2),(B,2)\}$ と、行 $C,D$・列 $3,4$ の部分 $B_2=\{(C,3),(C,4),(D,4)\}$ に分かれ、$B_1$ と $B_2$ は行も列も共有しない。各部分には $1$ 個置く方法が $3$ 通り、$2$ 個置く方法が $1$ 通り（$B_1$ では $(A,1),(B,2)$、$B_2$ では $(C,3),(D,4)$）で、$3$ 個以上は置けない。
- $r_3$：一方に $2$ 個、他方に $1$ 個なので $1\cdot 3+3\cdot 1=6$。
- $r_4$：両方に $2$ 個ずつなので $1\cdot 1=1$。
（$r_2$ も同様に $1+3\cdot 3+1=11$ となり、上の計算と一致する。）

ルーク多項式は $R(x)=(1+3x+x^2{)}^2=1+6x+11x^2+6x^3+x^4$ である。

公式に代入
$$N=1\cdot 4!-6\cdot 3!+11\cdot 2!-6\cdot 1!+1\cdot 0!=24-36+22-6+1=5.$$

確認 A は係 $3$ か $4$。A$=3$ のとき、B は $\{1,4\}$、C は $\{1,2\}$、D は $\{1,2\}$ から選ぶ。B$=1$ では C, D に $\{2,4\}$ が残るが、C$=4$ は禁止なので不可。B$=4$ では C, D に $\{1,2\}$ を割り当てて $2$ 通り。A$=4$ のとき、B$=1$ なら C$=2$, D$=3$ の $1$ 通り、B$=3$ なら C, D に $\{1,2\}$ を割り当てて $2$ 通り。合計 $2+1+2=5$ 通りで一致する。

よって答えは $5$ 通り。

禁止マスは A1, A2, B2, C3, C4, D4 の 6 個である。これは次の 2 つの部分に分かれ、互いに行も列も共有しない。
- 部分盤 1: {A1, A2, B2}(行 A, B、列 1, 2)
- 部分盤 2: {C3, C4, D4}(行 C, D、列 3, 4)

部分盤 1 のルーク多項式を求める。1 個置く方法は 3 通り。2 個置く方法は A1 と B2 の組だけである(A1 と A2 は同じ行、A2 と B2 は同じ列)ので 1 通り。よって $R_1(x)=1+3x+x^2$。部分盤 2 も同じ形で、$R_2(x)=1+3x+x^2$。

互いに独立な部分盤なので、積をとる。
$R(x)=(1+3x+x^2{)}^2=1+6x+11x^2+6x^3+x^4$
したがって $r_0=1,r_1=6,r_2=11,r_3=6,r_4=1$。

包除原理により、禁止をすべて避ける割り当ての総数は
${\sum }_{k=0}^4(-1{)}^k{r}_k(4-k)!=24-6\cdot 6+11\cdot 2-6\cdot 1+1=5$。

検算として直接数える。許される係は A:{3,4}、B:{1,3,4}、C:{1,2}、D:{1,2,3}。
- A=3 のとき、B=1 だと C=2 となり D が 4 になって不可。B=4 のとき (C,D)=(1,2),(2,1) の 2 通り。
- A=4 のとき、B=1 なら C=2, D=3 の 1 通り。B=3 なら (C,D)=(1,2),(2,1) の 2 通り。
合計 2+3=5 で一致する。