2つの隣接条件(包除原理)

方針

解答

⓪ 発想 — どう考え始めるか。 否定が $2$ つ重なった条件だ。

包除の型どおりに設計する。全体から「$AB$ が隣」と「$CD$ が隣」を引き、両方が隣の分を足し戻す。

足し戻しを忘れると、両方隣の場合を二重に引いてしまう。この包除の仕組みを、ひも縛り(隣接のかたまり化)と組み合わせて使う。総合問題だ。

求めるのは「AB がとなり合わず、かつ CD もとなり合わない」並び方。否定が2つ重なるので、包除を使う。

全体: 6人を1列に並べる方法は $6!=720$ 通り。

AB がとなり合う: A と B をひもで結んで1つのかたまりにすると、「かたまり + 残り4人」の5つの並べ方 $5!$、かたまりの中の並び $2!$ で

$$2\times 5!=2\times 120=240(\text{通り})$$

CD がとなり合う: 同じように $2\times 5!=240$ 通り。

AB も CD もとなり合う: AB のかたまりと CD のかたまりを両方作ると、「2つのかたまり + 残り2人」の4つの並べ方 $4!$、各かたまりの中の並び $2!\times 2!$ で

$$2\times 2\times 4!=4\times 24=96(\text{通り})$$

包除で仕上げる: 「AB 隣接」と「CD 隣接」を引くと、両方となり合う96通りを2回引いているので、足し戻す。

$$6!-2\times 5!-2\times 5!+2\times 2\times 4!=720-240-240+96=336(\text{通り})$$

まとめ:否定が1つなら「全体 − となり合う」で済むが、否定が2つ重なると引き過ぎが出る。これは、$A\cup B$ を引くとき共通部分を2回引くので1回戻す、という個数定理とまったく同じ調整だ。

発展 — 一歩先へ。 この解き方は「隣り合わせたくない組」が増えても効く。互いに人を共有しない($AB$ と $CD$ のように別々の)$k$ 組を、どれも隣り合わせない並べ方は、$n$ 人の列で ${\sum }_{j=0}^k(-1{)}^j(\genfrac{}{}{0ex}{}{k}{j})2^j(n-j)!$ 通りになる。

$k$ 組から $j$ 組を選んでそれぞれ「くっつけたかたまり」にすると、かたまりの中の並びが $2^j$、かたまりを $1$ 人分とみた全体の並べ方が $(n-j)!$、組の選び方が $\left(\genfrac{}{}{0ex}{}{k}{j}\right)$。これに符号を交互につけて足すのが包除だ。いまは $n=6,k=2$ で $720-480+96=336$ になる。

ただしこの式は $k$ 組が人を共有しないときに限る。たとえば $AB$ と $BC$ のように $B$ を共有すると、$2$ 組を同時にくっつけた形が $3$ 人のかたまりになり、内部の並びが $2^2$ でなくなって数え方が崩れる(このときの正しい答えは $288$ で、式の $336$ とはずれる)。並びを円卓に変えたり、$n$ 組の夫婦を男女交互かつどの夫婦も隣り合わないように円卓へ座らせる古典的な「夫婦問題(メナージュ問題)」に進んだりすると、端の重なりや交互条件が加わってさらに難しくなる。禁止したい隣接の形に合わせて包除の項の作り方を変えるのが、数え上げの腕の見せどころだ。

別解

別解 — 隙間法で $AB$ を離してから $CD$ を処理する(別の道具を使うルート)。 包除でなく、隣り合わせない配置を隙間に入れて作る。

まず $A,B$ を離す。ほかの $4$ 人 $C,D,E,F$ を並べると $4!=24$ 通りで、その両端と間に隙間が $5$ か所できる。この $5$ か所から $2$ か所を選んで $A,B$ を入れると、隣り合わない。順序を区別して $5\times 4=20$ 通り。合わせて $24\times 20=480$ 通り。

この $480$ 通りには $CD$ が隣り合うものも混じるので、それを引く。$CD$ を $1$ かたまり $[CD]$(中の並び $2$ 通り)にして、$[CD],E,F$ の $3$ つを並べる($3!=6$)。その $4$ か所の隙間から $2$ か所へ $A,B$ を入れて離すと $4\times 3=12$ 通り。$CD$ が隣り、かつ $AB$ が離れる並びは $2\times 6\times 12=144$ 通り。

引いて

$$480-144=336.$$

包除で一気に出す本解と同じ $336$ 通り。隙間に入れて隣接を断つ道具でも、同じ答えにたどり着く。