重複を含む文字列の並べ方では、「同じ文字が隣り合わない」という条件が付くと、単純な順列の公式だけでは解けなくなります。特にaabbcccのような問題では、余事象や包除原理を正しく使えるかどうかが重要です。この記事では、a同士が隣り合わない並べ方と、すべての同じ文字が隣り合わない並べ方の考え方を解説します。
まず全体の並べ方を求める
文字列aabbcccの総数は、重複順列の公式から求められます。
総数 = 7! ÷ (2!×2!×3!)
= 5040 ÷ 24
= 210通り
まずこの210通りを出発点として考えます。
a同士が隣り合わない並べ方
余事象を利用します。まずaが隣り合う場合を数えます。
aaを一つの塊と考えると、対象は
(aa), b, b, c, c, c
の6個になります。
したがって並べ方は
6! ÷ (2!×3!)
= 60通り
よって求める個数は
210 – 60 = 150通り
a同士が隣り合わない並べ方は150通りです。
なぜaから余事象を引く方法で迷いやすいのか
この問題ではaについては単純に余事象で解けます。しかしbやcも同時に考え始めると重複計算が発生します。
例えば「aが隣接」「bが隣接」を別々に引くと、aもbも隣接しているケースを二重に引いてしまいます。
このような場合には包除原理が必要になります。
すべての文字が隣り合わない並べ方
条件は
- a同士が隣接しない
- b同士が隣接しない
- c同士が隣接しない
です。
包除原理を用います。
A：aが隣接する集合
B：bが隣接する集合
C：cが隣接する集合
とすると
|A|=60
|B|=60
|C|=90
です。
さらに
|A∩B|=20
|A∩C|=24
|B∩C|=24
|A∩B∩C|=6
となります。
したがって包除原理より
210-(60+60+90)+(20+24+24)-6
=62
となります。
つまり全ての同じ文字が隣り合わない並べ方は62通りです。
挿入法で確認する考え方
別解として、まずcccを配置し、その隙間にaとbを入れる方法もあります。
ただし重複文字が複数存在するため場合分けが多くなり、試験では包除原理の方が整理しやすいことが多いです。
大学入試レベルでは、余事象だけで済むのか、それとも包除原理まで必要なのかを見抜くことが重要になります。
まとめ
aabbcccの総数は210通りです。a同士が隣り合わない並べ方は、余事象を利用して210−60=150通りとなります。
さらにa・b・cのいずれも隣接しない場合は、単純な余事象では重複計算が発生するため包除原理を用います。その結果、求める個数は62通りとなります。
この種の問題では、「余事象だけで済むか」「包除原理が必要か」を判断することが解法のポイントです。
コメント