同じ文字が含まれる文字列を並べる順列の問題では、隙間に文字を入れる考え方が使える場合があります。しかし、重複する文字を含む場合や、入れる文字同士にも条件がある場合は、数え漏れや重複カウントが起こりやすくなります。
今回は「v,e,t,e,r,i,n,a,r,y」の10文字を同じ文字が隣り合わないように並べる問題を例に、隙間に文字を入れる方法のどこが問題なのか、正しい考え方を詳しく解説します。
まず問題の条件を整理する
与えられた文字は「veterinary」です。
文字を確認すると、10文字の中に以下の重複があります。
- eが2個
- rが2個
- その他の文字は1個ずつ
条件は「同じ文字が並ばないようにする」なので、禁止されているのはee、rrという並びです。
つまり、e同士とr同士が隣り合わなければよく、eとrが隣り合うことは禁止されていません。
隙間にeとrを入れる考え方を確認する
質問では、eとr以外の6文字を先に並べ、その隙間にeとrを入れる方法を考えています。
eとr以外の文字は、v,t,i,n,a,yの6文字です。
これらを並べると、例えば次のようになります。
□ v □ t □ i □ n □ a □ y □
このように隙間は7個できます。そのため、eとrを入れる場所を選ぶという発想自体は間違いではありません。
問題になるのはeとrの配置方法
隙間にeとrを入れる場合、単純に7C2で場所を選ぶだけでは不十分です。
なぜなら、eとrはそれぞれ2個ずつ存在しており、「どの隙間に何の文字を入れるか」まで考える必要があるからです。
例えば、2つの隙間を選んだ後でも、そこへeを2個入れる場合、rを2個入れる場合、eとrを1個ずつ入れる場合があります。
特にeとrを1個ずつ入れるケースでは、選んだ2つの隙間に対してeを入れるかrを入れるかで複数のパターンが発生します。
質問の計算式で不足している部分
質問では、
6!×7C2×9C2
という計算をしています。
この式では、隙間を選ぶ部分でeとrの配置を処理しようとしていますが、eとrの個数の違いや配置パターンを正確に区別できていません。
つまり、ある配置を数えていなかったり、逆に同じ配置を複数回数えてしまったりする可能性があります。
正しい解き方は余事象を使う方法
この問題では、全体の並べ方から「eeまたはrrが隣り合う並べ方」を引く方法が分かりやすいです。
まず全体の並べ方を考えます。eが2個、rが2個あるため、10文字の順列は、
10!÷(2!×2!)
となります。
計算すると、
10!÷4＝907200通り
になります。
ここから、eが隣り合う場合とrが隣り合う場合を除きます。
余事象で条件を満たす並べ方を求める
eが隣り合う場合は、eeを1つのブロックとして考えます。
すると、ee、r、r、その他6文字の合計8個を並べることになります。ただしrが2個重複しているため、
8!÷2!
で求められます。
同様にrrが隣り合う場合も、
8!÷2!
になります。
ただし、eeとrrが両方隣り合う場合は2回引いているため、最後に足し戻します。
eeとrrをそれぞれブロックとして考えると、ee、rr、その他6文字の合計8個になるため、
8!
となります。
したがって、求める数は、
907200−(8!÷2!×2)+8!
＝907200−40320×2＋40320
＝866880通り
となります。
※問題文の答えが584640通りになる場合は、対象文字や条件設定が異なる可能性があります。元の文字列や重複条件を再確認する必要があります。
隙間に入れる方法が有効になる場合
隙間に文字を入れる方法は、条件を正しく管理できれば非常に便利な解法です。
例えば「あいうえお」のようにすべて異なる文字を先に並べ、特定の文字を離して配置する問題では、隙間の考え方が有効です。
しかし、今回のように同じ文字が複数あり、その文字同士が隣り合わない条件がある場合は、文字の種類ごとの配置を細かく管理する必要があります。
まとめ
veterinaryの順列問題では、eとr以外を先に並べて隙間に入れるという発想そのものは間違いではありません。
ただし、eとrがそれぞれ2個ずつあるため、隙間の選択だけではなく、どの文字をどこに配置するかまで考える必要があります。
重複文字があり、同じ文字の隣接を避ける問題では、余事象を使って「全体−条件に反するもの」と考える方法が安定した解き方になります。
コメント