英単語や文章の文字を並べ替えたときに何通りの組み合わせができるかを求める問題は、順列の考え方を理解するうえで非常に重要です。特に同じ文字が複数回登場する場合は、単純に階乗を計算するだけでは正しい答えになりません。この記事では「Start over!」を例に、考え方から途中式まで丁寧に解説します。
まず文字数を確認する
「Start over!」に含まれる文字を1文字ずつ数えてみましょう。
空白を除いて考えると、次の10文字になります。
S, t, a, r, t, o, v, e, r, !
したがって並べ替える対象は全部で10文字です。
重複する文字を探す
次に、同じ文字が何回登場するかを確認します。
| 文字 | 出現回数 |
|---|---|
| t | 2回 |
| r | 2回 |
| その他 | 各1回 |
もし全て異なる文字なら、10個の文字の並べ替えは10!通りになります。
しかし今回はtが2個、rが2個あるため、そのままでは同じ並びを重複して数えてしまいます。
重複文字がない場合の並べ方
まずは重複を無視して考えてみます。
10個の異なる文字を並べる順列は次の式で求められます。
10! = 10×9×8×7×6×5×4×3×2×1
計算すると3,628,800通りになります。
ただし、この中にはt同士を入れ替えただけの同じ並びや、r同士を入れ替えただけの同じ並びが含まれています。
重複分を取り除く考え方
tが2個ある場合、t同士を入れ替えても見た目は変わりません。
そのため、tについては2!で割る必要があります。
同様にrについても2!で割ります。
したがって求める式は次のようになります。
10! ÷ (2! × 2!)
数値を代入すると、
3,628,800 ÷ (2 × 2)
= 3,628,800 ÷ 4
= 907,200
なぜ割り算をするのか
重複文字を含む順列では、「同じもの同士を交換しても別の並びとはみなさない」という考え方を使います。
例えば「ABB」という文字列を考えると、B同士を交換しても見た目は変わりません。
そのため、全順列3!を求めた後、重複して数えた分を2!で割ります。
「Start over!」も同じ考え方で、tとrの重複分をそれぞれ除いているのです。
まとめ
「Start over!」を空白を除いた10文字として考えると、tが2個、rが2個含まれています。
まず10文字を異なるものとして並べると10!通りですが、重複しているtとrによる重複計算を除くため、2!と2!で割ります。
途中式は次の通りです。
10! ÷ (2! × 2!)
= 3,628,800 ÷ 4
= 907,200
したがって、「Start over!」の文字を並べ替えた組み合わせは907,200通りとなります。
コメント