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

手順 1：禁止マス（盤）を書き出す。
行を人、列を仕事とすると、禁止されたマスは
$$(A,1),(A,2),(B,2),(C,3),(C,4),(D,4)$$
の 6 個である。前半の 3 個は行 $A,B$・列 $1,2$ に、後半の 3 個は行 $C,D$・列 $3,4$ にあり、2 つの部分は行も列も共有しない。

手順 2：ルーク数 $r_k$ を求める。
$r_k$ は、禁止マスの中に、どの 2 個も同じ行・同じ列にない $k$ 個のルークを置く方法の数である。

• $r_0=1$（何も置かない）。
• $r_1=6$（禁止マスの個数）。
• $r_2$：前半の 3 マスの中だけで 2 個置く方法は $(A,1),(B,2)$ の 1 通り（$(A,1),(A,2)$ は同じ行、$(A,2),(B,2)$ は同じ列）。後半も同様に $(C,3),(D,4)$ の 1 通り。前半から 1 個・後半から 1 個置く方法は、行も列も重ならないので $3\times 3=9$ 通り。よって $r_2=1+1+9=11$。
• $r_3$：一方の部分に 2 個（1 通り）、他方に 1 個（3 通り）置くので $1\times 3+3\times 1=6$。
• $r_4$：両方の部分に 2 個ずつ置くので $1\times 1=1$。

（ルーク多項式で書くと、各部分が $1+3x+x^2$ なので $(1+3x+x^2{)}^2=1+6x+11x^2+6x^3+x^4$ となり、上と一致する。）

手順 3：公式に代入する。
禁止マスを避ける置換の個数は
$$\sum _{k=0}^4(-1{)}^k{r}_k(4-k)!=1\cdot 4!-6\cdot 3!+11\cdot 2!-6\cdot 1!+1\cdot 0!$$
$$=24-36+22-6+1=5.$$

確認： $A\in \{3,4\}$、$C\in \{1,2\}$ で場合分けすると、$(A,B,C,D)$ の仕事は $(3,4,1,2),(3,4,2,1),(4,3,1,2),(4,1,2,3),(4,3,2,1)$ の 5 通りで、一致する。

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

禁止マスは A1, A2, B2, C3, C4, D4 の 6 個である。

この盤は 2 つの成分 {A1, A2, B2} と {C3, C4, D4} に分かれ、2 つの成分は行も列も共有しない。
各成分のルーク多項式は、1 個置く方法が 3 通り、2 個置く方法が (A1, B2) の 1 通りなので $1+3x+x^2$ である。

全体のルーク多項式は
$(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$ である。

包除原理より、禁止マスを 1 つも含まない割り当ての数は
${\sum }_k(-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 のとき、(C=1, B=4, D=2) と (C=2, B=4, D=1) の 2 通り。
- A=4 のとき、(C=1, B=3, D=2)、(C=2, B=1, D=3)、(C=2, B=3, D=1) の 3 通り。

合計 5 通りで、包除原理の結果と一致する。