同じ文字が隣り合わない並べ方

方針

解答

⓪ 発想 — どう考え始めるか。 「$\mathrm{a}$ が隣り合わない」も、$\mathrm{a}$ 以外を先に並べて隙間に $\mathrm{a}$ を入れる型だ。

まず $\mathrm{a}$ 以外の $\mathrm{b},\mathrm{b},\mathrm{c}$ を並べる。同じ $\mathrm{b}$ が $2$ 個あるので $\frac{3!}{2!}=3$ 通り。

$3$ 文字の間と両端で、隙間は $4$ か所。ここから $3$ か所を選んで $\mathrm{a}$ を $1$ 個ずつ入れる($\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ 通り)。同じ隙間に $2$ 個入れなければ $\mathrm{a}$ は隣り合わない。$3\times 4=12$。

① $\mathrm{a}$ 以外を並べる。 $\mathrm{b},\mathrm{b},\mathrm{c}$ の $3$ 文字の並べ方は、$\mathrm{b}$ が $2$ 個ダブるので

$$\frac{3!}{2!}=3\text{通り}$$

② 隙間を数えて $\mathrm{a}$ を入れる。 $3$ 文字を並べると、間と両端に隙間が $4$ か所できる。

この $4$ か所から $3$ か所を選んで $\mathrm{a}$ を $1$ つずつ入れる($\mathrm{a}$ は同じ文字なので順序は関係ない):

$${}_4{\mathrm{C}}_3=4\text{通り}$$

③ 積をとる。

$$3\times 4=12\text{通り}$$

まとめ:「同じ文字が隣り合わない」は「他を並べて隙間に入れる」。$\mathrm{a}$ 以外の並べ方(ダブりを $2!$ で割る)と、隙間の選び方 ${}_4{\mathrm{C}}_3$ の積。両端も隙間に数えることを忘れない($3$ 文字なら隙間は $4$ か所)。

発展 — 一歩先へ。 「同じ文字が隣り合わない」の一般的な数え上げは、包除原理や隙間法で扱う。文字の種類と個数が増えると難しくなり、「$\mathrm{aa}\cdots \mathrm{a}$($p$ 個)が隣り合わない」は、他の文字の並びの隙間から $p$ か所を選ぶ問題。連続を禁止する配置は、DNA配列やスケジューリングなど応用も広い。

別解

別解 — 総数から「$\mathrm{a}$ が隣り合う」を引く(補集合のルート)。 $6$ 文字全体の並べ方は $\frac{6!}{3!2!}=60$ 通り。ここから「$\mathrm{a}$ が隣り合う場合」を引く。ただし「隣り合う」の数え上げは包除が要る。

「$\mathrm{aa}$ が少なくとも $1$ 組できる」を数える。$\mathrm{aa}$ を $1$ かたまり $[\mathrm{aa}]$ とみて、$[\mathrm{aa}],\mathrm{a},\mathrm{b},\mathrm{b},\mathrm{c}$ の $5$ 個を並べると $\frac{5!}{2!}=60$…だが、これは $\mathrm{aaa}$($3$ 個連続)を二重に数える。$\mathrm{aaa}$ を $1$ かたまりとみると $[\mathrm{aaa}],\mathrm{b},\mathrm{b},\mathrm{c}$ で $\frac{4!}{2!}=12$ 通り。包除で「隣り合う」$=60-12=48$。

答え $=60-48=12$。

隙間法(本解)が「隣り合わない」を直接作るのに対し、補集合は「全体 $-$ 隣り合う」。ただし「隣り合う」の数え上げに包除が必要で、$\mathrm{aaa}$ の二重計上に注意が要る。同じ $12$ に着くが、隙間法の方が明快だ。