同じ文字が並ぶとき、隣り合わせをどう避けるか？

a、a、b、b、c の 5 文字を並べる並べ方は 30 通り。そのうち a どうしが隣り合わないのは 18 通りです。

同じ文字が混ざると、隣接の条件は 2 段構えになります。まず同じものを含む順列で全体を数え、そのうえで隣接を処理する。

隣り合う場合は塊にする

まず易しいほうから確かめます。a どうしが必ず隣り合う並べ方を数える。

$aa$ をひとまとめにすると、並べるものは $[aa]$、b、b、c の 4 つ。このうち b が 2 つ同じです。

$$\frac{4!}{2!}=12$$

12 通りになります。塊の中で a と a を入れ替えても同じ文字なので、$2!$ を掛けません。

ここが人を並べる問題との違いです。区別できる 2 人なら塊の中で 2 通りありますが、同じ文字なら 1 通りだけ。

隣り合わないは引き算で

全体から、隣り合う場合を引きます。全体は $\frac{5!}{2!2!}=30$ 通り。

$30-12=18$ 通りです。同じ文字が 2 個だけなら、この引き算で足ります。

すき間法でも同じ値

引き算を使わない道筋もあります。a 以外を先に並べ、そのすき間へ a を入れる。

b、b、c を並べる並べ方は $\frac{3!}{2!}=3$ 通り。並んだ 3 文字が作るすき間は、両端を含めて 4 か所。

a は区別しないので、4 か所から 2 か所を選ぶだけ。${}_4{\mathrm{C}}_2=6$ 通りです。

$$3\times 6=18$$

引き算と一致しました。同じものなので、選んだあとに並べ替えを掛けない点に注意します。

3 個以上あるときは引き算が使えない

同じ文字が 3 個以上になると、引き算が重くなります。「3 個のうち 2 個だけ隣り合う」場合が混ざるため。

すき間法なら影響を受けません。他を先に並べて、すき間から必要な数だけ選ぶだけ。

例：a が 3 個ある場合

a、a、a、b、b の 5 文字で、a どうしが隣り合わない並べ方を数えます。

b、b を並べるのは 1 通り。すき間は両端を含めて 3 か所です。

a を 3 個入れるには、3 か所すべてを使うしかありません。${}_3{\mathrm{C}}_3=1$ 通り。

答えは 1 通り、$ababa$ だけです。全体は $\frac{5!}{3!2!}=10$ 通りなので、9 通りは a が隣り合っている。

例：赤 3 個、白 2 個、青 1 個

6 個の玉を並べ、赤どうしが隣り合わないようにします。同じ色は区別しない。

赤以外の 3 個、つまり白、白、青を並べて $\frac{3!}{2!}=3$ 通り。すき間は 4 か所です。

赤 3 個を入れる場所を 4 か所から選んで ${}_4{\mathrm{C}}_3=4$ 通り。

$$3\times 4=12$$

12 通りになります。全体は $\frac{6!}{3!2!1!}=60$ 通りなので、条件を満たすのは 5 分の 1。

2 種類とも隣り合わない場合

条件が 2 つ重なると、すき間法だけでは足りません。包除原理に切り替えます。

a、a、b、b、c で、a どうしも b どうしも隣り合わない並べ方を数える。

全体は 30 通り。a が隣り合うのは 12 通り、b が隣り合うのも 12 通りです。

両方が隣り合うのは、$[aa]$、$[bb]$、c の 3 つを並べる $3!=6$ 通り。

$$30-12-12+6=12$$

12 通りになります。引きすぎたぶんを足し戻すところが要です。

例：塊が 2 つ必要な場合

a、a、b、b、c で、a どうしが隣り合い、かつ b どうしも隣り合う並べ方。

$[aa]$、$[bb]$、c の 3 つを並べるだけなので $3!=6$ 通りです。塊の中身は同じ文字なので掛け算なし。

区別できる 5 人で同じ条件なら、$3!\times 2!\times 2!=24$ 通り。同じものかどうかで 4 倍の差が出ます。

例：文字列で確かめる

「ももたろう」の 5 文字を並べ替えます。「も」が 2 個、「た」「ろ」「う」が 1 個ずつ。

全体は $\frac{5!}{2!}=60$ 通り。「も」どうしが隣り合うのは、塊にして $4!=24$ 通り。

隣り合わないのは $60-24=36$ 通りです。すき間法でも、「た」「ろ」「う」を並べる $3!=6$ 通りに、すき間 4 か所から 2 か所を選ぶ ${}_4{\mathrm{C}}_2=6$ 通りを掛けて 36 になります。

例：数字を並べる

1、1、2、2、3、3 の 6 枚を並べ、同じ数字が隣り合わない並べ方を数えます。3 種類とも条件が付く形。

全体は $\frac{6!}{2!2!2!}=90$ 通り。1 が隣り合うのは、塊にして $\frac{5!}{2!2!}=30$ 通りで、2 と 3 も同じ。

2 種類が隣り合うのは $\frac{4!}{2!}=12$ 通りで、その組み合わせが 3 通り。3 種類とも隣り合うのは $3!=6$ 通り。

$$90-30\times 3+12\times 3-6=90-90+36-6=30$$

30 通りです。条件が 3 つになっても、符号を交互に変えて足し引きするだけ。

例：隣り合ってよい種類が混ざる

赤 2 個、白 2 個、青 1 個で、赤どうしだけを離します。白は隣り合ってよい。

赤以外の白、白、青を並べて $\frac{3!}{2!}=3$ 通り。すき間 4 か所から 2 か所を選んで ${}_4{\mathrm{C}}_2=6$ 通り。

$3\times 6=18$ 通りです。条件が 1 種類だけなら、種類が増えてもすき間法で押し切れます。

検算のしかた

答えが出たら、小さい場合に落として書き出します。a、a、b の 3 文字なら全体が 3 通り、a が隣り合わないのは $aba$ の 1 通り。

すき間法で確かめると、b を並べて 1 通り、すき間 2 か所から 2 か所を選んで 1 通り。値が合いました。

全体から引く形でも、$aab$ と $baa$ の 2 通りを引いて 1 通り。3 つの道筋がそろえば安心です。

よくある誤り

離したい種類が 1 つならすき間法、2 つ以上なら包除原理。この切り替えだけ覚えておけば足ります。

参考文献

^[1] が同じものを含む順列、^[2] がすき間を使う数え方、^[3] が引き算と足し戻し、^[4] と ^[5] が各国語での公式です。