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

夫婦に番号 $1,2,3,4$ をつけ、条件 $A_i$ を「夫婦 $i$ が隣り合う」とします $(i=1,2,3,4)$。求める個数は $\left|\overline{A_1}\cap \overline{A_2}\cap \overline{A_3}\cap \overline{A_4}\right|$ です。

手順 1：$k$ 個の条件を同時に満たす並び方を数える。
$k$ 組の夫婦を指定し、その $k$ 組がすべて隣り合う並び方を数えます。指定した各夫婦を 1 つのかたまりとみなすと、並べるものは $8-k$ 個になり、その並べ方は $(8-k)!$ 通りです。さらに、各かたまりの中で夫と妻の左右の入れかえが $2$ 通りずつあります。よって
$$N_k=2^k(8-k)!$$
です。この値はどの $k$ 組を選んだかによらないので、条件は対称です。$k$ 組の選び方は $\left(\genfrac{}{}{0ex}{}{4}{k}\right)$ 通りあります。

手順 2：一般の包除原理を使う。
$$\left|\overline{A_1}\cap \cdots \cap \overline{A_4}\right|=\sum _{k=0}^4(-1{)}^k(\genfrac{}{}{0ex}{}{4}{k})2^k(8-k)!$$

手順 3：各項を計算する。
- $k=0$：$1\cdot 1\cdot 8!=40320$
- $k=1$：$4\cdot 2\cdot 7!=8\cdot 5040=40320$
- $k=2$：$6\cdot 4\cdot 6!=24\cdot 720=17280$
- $k=3$：$4\cdot 8\cdot 5!=32\cdot 120=3840$
- $k=4$：$1\cdot 16\cdot 4!=16\cdot 24=384$

したがって
$$40320-40320+17280-3840+384=13824$$

よって、どの夫婦も隣り合わない並び方は $13824$ 通りです。

包除原理を用いる。夫婦 $i$ が隣り合う事象を $A_i$ とする。$k$ 組が隣り合う並び方は、選んだ $k$ 組を各々ひとまとまり（内部の順序 $2^k$ 通り）として扱い、$(8-k)!$ 通りの並べ方と組み合わせて $\left(\genfrac{}{}{0ex}{}{4}{k}\right)2^k(8-k)!$ となる。

$k=0$: $8!=40320$
$k=1$: $4\cdot 2\cdot 7!=8\cdot 5040=40320$
$k=2$: $6\cdot 4\cdot 6!=24\cdot 720=17280$
$k=3$: $4\cdot 8\cdot 5!=32\cdot 120=3840$
$k=4$: $1\cdot 16\cdot 4!=384$

求める数は
$40320-40320+17280-3840+384=13824$。

検算: 4 組が $n=4$ の場合の既知の値 $13824=2^4\cdot 864$ であり、夫婦を区別しない場合の隣り合わない配置数（夫婦を同一視した多重集合の順列で隣り合わないもの）は 864 であることと整合する。実際、各ペアを同じ文字とみなした $AABBCCDD$ の隣り合う同文字なしの順列数は 864 であり、各文字の 2 人を区別する $2^4=16$ 倍で $13824$ となる。