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

人を $1,2,\dots ,8$ とし、夫婦を $\{1,2\},\{3,4\},\{5,6\},\{7,8\}$ とする。人 $i$ が受け取るプレゼントの用意者を $\sigma (i)$ とすると、配り方は置換 $\sigma \in S_8$ に対応し、条件は「各 $i$ について $\sigma (i)$ が $i$ の属する夫婦に含まれない」ことである。

禁止配置と包除原理. $8\times 8$ の盤で、マス $(i,j)$ が禁止であるのは $i,j$ が同じ夫婦に属するときである。禁止マスは対角線上に並んだ $2\times 2$ のブロック 4 つからなる。禁止マスから、どの 2 つも同じ行・同じ列にない $k$ 個を選ぶ方法の数を $r_k$（ルーク数）とすると、包除原理により求める数は
$$N=\sum _{k=0}^8(-1{)}^k{r}_k(8-k)!$$
である（$k$ 個の禁止マスを指定したとき、それを含む置換は $(8-k)!$ 個）。

ルーク数. $2\times 2$ のブロック 1 つでは、0 個の選び方 1 通り、1 個は 4 通り、2 個（互いに行・列が異なる）は 2 通りなので、ルーク多項式は $1+4x+2x^2$。ブロックどうしは行も列も共有しないので、全体のルーク多項式は
$$R(x)=(1+4x+2x^2{)}^4.$$
まず $(1+4x+2x^2{)}^2=1+8x+20x^2+16x^3+4x^4$。これを 2 乗して
$$R(x)=1+16x+104x^2+352x^3+664x^4+704x^5+416x^6+128x^7+16x^8.$$
（係数の和 $2401=7^4$ で検算できる。）

計算.
$$\begin{array}{rl}N& =8!-16\cdot 7!+104\cdot 6!-352\cdot 5!+664\cdot 4!-704\cdot 3!+416\cdot 2!-128\cdot 1!+16\cdot 0!\\ & =40320-80640+74880-42240+15936-4224+832-128+16\\ & =4752.\end{array}$$

検算. 同じ方法で夫婦 2 組なら $24-8\cdot 6+20\cdot 2-16\cdot 1+4=4$ となり、これは「夫婦 $\{1,2\}$ が $\{3,4\}$ のプレゼントを、$\{3,4\}$ が $\{1,2\}$ のプレゼントを受け取る」$2\cdot 2=4$ 通りと一致する。

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

各夫婦 $\{2j-1,2j\}$ について、その 2 人は互いのプレゼントも自分のプレゼントも受け取れない。禁止位置は 4 つの $2\times 2$ のブロックで、各ブロックの rook 多項式は $1+4x+2x^2$。全体は $(1+4x+2x^2{)}^4$。

$(1+4x+2x^2{)}^2=1+8x+20x^2+16x^3+4x^4$。これを 2 乗して係数 $r_k$（$k$ 個の互いに攻撃しない禁止位置の置き方）を求めると
$r_0..r_8=1,16,104,352,664,704,416,128,16$（和 $=7^4=2401$ で検算）。

包除原理より個数 $={\sum }_k(-1{)}^k{r}_k(8-k)!$
$=40320-16\cdot 5040+104\cdot 720-352\cdot 120+664\cdot 24-704\cdot 6+416\cdot 2-128+16$
$=40320-80640+74880-42240+15936-4224+832-128+16=4752$。