高校数学A 同じものを含む順列—区別できない並べ替えを除いて個数を数える｜武蔵野個別指導塾

同じ文字の重複を取り除き、通過点のある最短経路にも同じものを含む順列を使います。

よくあるのは、定期テスト前に文字を並べ替える問題を解き、同じ文字の入れ替えまで別扱いしてしまう場面です。例えば、同じ文字に小さな番号を付ければ計算しやすくなりますが、最後に番号を消したとき、見た目が同じ列は1通りです。番号付きの列を何個まとめると1つの列になるのかを調べれば、重複を取り除けます。道を進む順序も文字列に置き換えられるので、同じ考え方を使えます。

何を1通りと数えるか

問われ方の1つは、文字や記号をすべて1列に並べる問題です。同じ文字は見た目で区別せず、異なる文字が置かれた位置に違いがあると別の列として数えます。まず全体の文字数と各文字の個数を数え、同じ文字に仮の番号を付けた場合の重複を除きます。

もう1つは、格子状の道を最短で進む問題です。右へ進む1歩を R、上へ進む1歩を U とすれば、道順は R と U の列で表せます。同じ方向の歩数は区別しないため、文字の並べ替えと同じ数え方です。通過点が指定される場合は、そこまでの道順と、そこから先の道順を分けて数えます。

条件が付いても、最初に確認するのは答えの対象です。番号の付いた札の並びを求めるのか、番号を消した文字列を求めるのかで、同じ入れ替えが別の結果になるかどうかが変わります。ここでは同じ記号を区別せず、重複組合せは扱いません。

番号を消すと何が重なるか

異なる n 個を1列に並べる方法は、最初の場所に n 通り、次に n − 1 通りというように選ぶので n! 通りです。記号 ! は階乗を表し、例えば 4! = 4 × 3 × 2 × 1 = 24 です。0! は 1 と決めます。これは該当する種類がない場合にも、割る数を 1 として扱うために使えます。

同じ A が2個、異なる B が1個ある AAB を考えます。仮に A₁、A₂ と区別すると、A₁A₂B と A₂A₁B は異なる並びです。しかし番号を消すと、どちらも AAB になります。図1のように、見た目が同じ列に戻る番号付きの並びをまとめます。

図1では、AAB という1つの文字列に2通りが対応します。同様に ABA、BAA のそれぞれにも2通りずつ対応するので、番号付きの 3! = 6 通りを 2! = 2 で割ると、区別しない列は 3 通りです。割る理由は「同じものがあるから」という言葉だけで終わらせず、1つの答えが何回数えられたかで説明できます。

一般に、全部で n 個のうち、同じ種類がそれぞれ a 個、b 個、c 個あるとします。ここで a + b + c = n です。仮の番号をすべて付けた n! 通りの中で、見た目の1列には、各種類の番号の入れ替えにより a! × b! × c! 通りが対応します。どの列でも対応する数は同じですから、求める数は n! / (a! × b! × c!) です。種類が2つなら2つの階乗だけを使い、すべて異なる種類なら各個数は1なので割る数は1です。

同じ列に対応する個数が一定であることは、割り算の大事な条件です。例えば A の位置を決めた後、そこに番号を振る方法は、位置がどこでも同じ 2! 通りです。別の種類の番号の振り方も独立に選べるので、種類ごとの階乗を掛けます。全体を種類の数で割るのではなく、同じ種類の個数の階乗で割ります。

文字の種類が増えた場合も、場所を先に決める方法で式の意味を調べられます。例えば同じ C が2個、D が1個、E が1個なら、4か所のうち C の2か所を選んでから、残り2か所のどちらに D を置くかを選びます。C の場所は 4 × 3 / 2 = 6 通り、D の場所は2通りです。残った場所に E を置くので、合計12通りです。階乗を使っても 4! / 2! = 12 となり、同じ結果になります。

この確認では、C の2か所を選ぶ際にも順番を区別していません。先に左の場所を選ぶか右の場所を選ぶかは、完成した列では見えないからです。もし C の場所を順に選んだ 4 × 3 = 12 をそのまま使うと、同じ位置の組を2回数えてしまいます。列の中に残る違いだけを数える、という基準は、階乗の公式を使う場合と位置を選ぶ場合で共通です。

基本例題：5文字の並べ替え

問題：A が3個、B が2個あります。5個すべてを1列に並べるとき、同じ文字を区別しない並べ方は何通りですか。答えは整数で示してください。

まず A を A₁、A₂、A₃、B を B₁、B₂ と区別します。番号付きの5文字はすべて異なるので、図2のように左から置くと、選択肢は順に5個、4個、3個、2個、1個です。

図2の計算を順に書きます。番号付きの並べ方は

5! = 5 × 4 × 3 × 2 × 1 = 120

通りです。番号を消した1つの列に注目すると、A の位置3か所への番号の振り方は 3! = 6 通り、B の位置2か所への振り方は 2! = 2 通りです。したがって、その列は番号付きの数え方の中に 3! × 2! = 12 回現れます。すべての列が同じ回数現れるので、求める数は

5! / (3! × 2!) = 120 / (6 × 2) = 10 通り

です。分母を 3 + 2 とするのでは、各文字の番号を交換する方法を数えられません。A の番号の振り方と B の番号の振り方は組み合わせて選ぶので、6 と 2 を掛けます。

答えを別の見方で場面に戻します。5つの位置から B を置く2か所を選べば、残りの3か所には A が入ります。B の位置の選び方は 5 × 4 / 2 = 10 通りです。どの位置の組も B が2個、A が3個という元の条件を満たし、異なる位置の組は異なる列を作ります。重複も漏れもないことが、この数え方からも確かめられます。

通過点で道順を区切る

問題：格子状の道で、点 O から右へ4区画、上へ3区画進んだ点 G まで最短で進みます。途中で O から右へ2区画、上へ1区画の点 P を通る道順は何通りですか。右と上に隣接する点の間を1歩とし、答えは整数で示してください。

最短で G に着くには、右へ4歩、上へ3歩の計7歩が必要です。左や下へ進むと、その分を戻す歩数も必要になるため7歩を超えます。したがって最短経路では右と上の歩だけを使います。P までは R が2個、U が1個なので、その順序は

3! / (2! × 1!) = 6 / 2 = 3 通り

です。P から G までは右へ2歩、上へ2歩残ります。こちらの順序は

4! / (2! × 2!) = 24 / 4 = 6 通り

です。前半の1つの道順と後半の1つの道順をつなぐと、P を通る道順が1つ決まります。つないだ道順を P で切れば元の前半と後半が一意に戻るため、重複もありません。よって

3 × 6 = 18 通り

です。前半と後半を合わせると、右は 2 + 2 = 4 歩、上は 1 + 2 = 3 歩です。7歩で G に着き、途中の3歩で P に着くので、求めた道順は元の条件を満たします。

P を通る条件がなければ、R が4個、U が3個の7文字を並べて 7! / (4! × 3!) = 35 通りです。18 はその一部です。通過点があるのに全体を一度に並べると、P を通らない道順も含みます。逆に、指定点が右上へ進む途中にない場合は事情が変わります。例えば P が G より右にあれば、右と上だけで G へ向かう途中には通れず、P を通る最短経路は 0 通りです。先に各区間の必要な移動方向を確かめます。

道順を文字に変えるときは、道の形に制限がないかも読み取ります。右と上の隣接する点の間がすべて通れる格子なら、指定された方向の列をたどることで、必ず1本の道順ができます。一方、途中に通れない道があれば、文字列の総数からその道を通る列を取り除く必要があります。通れない区間が複数ある場合は、同じ道順を重ねて除かないように確かめます。前の例には通れない区間がないので、右と上の並べ替えをそのまま使えます。

また、通過点を2つ指定された場合は、順に通過できる位置関係かを先に見ます。右と上だけの道では、一度通った点より左や下へ戻れません。各区間で必要な移動が右と上に限られれば、区間ごとに数えた後、それらを掛けられます。移動方向が条件に合わない区間があれば、その指定順では最短経路はありません。

間違いを列に戻して直す

先ほどの A が3個、B が2個の問題で、誤って 5! / 3! = 20 通りとしたとします。A の番号の交換は取り除けていますが、B₁ と B₂ を交換した2通りがまだ別に残っています。図3のように、番号を消した結果を比べると、重複が見えます。

図3の2つはどちらも AAABB です。各文字列がまだ2回ずつ数えられているので、20 / 2! = 10 通りに直します。反対に、B が2種類の異なる文字なら、その交換は別の列です。その場合に 2! で割ると、異なる結果までまとめてしまいます。問題文で「同じ」とされる範囲を先に印で囲むと、分母の取り違えを防げます。

経路でも同様です。右へ進む1歩ずつに番号を付けて順列を作っても、番号を消した道順が同じなら1通りです。ただし、前半と後半を区切った後は、それぞれの区間で重複を除きます。各区間を数えた上で、さらに全体の右歩の階乗で割ると、同じ重複を二度除くことになります。

練習問題

いずれも同じ記号は区別せず、答えは整数の通り数で示してください。

1. 赤い札を表す X が2個、青い札を表す Y が2個、白い札を表す Z が1個あります。5個すべてを1列に並べる方法は何通りですか。
2. 数字 1 が2個、数字 2 が3個、数字 3 が1個書かれた6枚の札をすべて1列に並べて6桁の整数を作ります。同じ数字の札は区別しません。何個の整数ができますか。
3. 格子状の道で、点 S から右へ3区画、上へ2区画の点 T まで最短で進みます。隣接点間を1歩とするとき、道順は何通りですか。
4. 格子状の道で、点 A から右へ3区画、上へ3区画の点 C まで最短で進みます。途中で A から右へ1区画、上へ2区画の点 B を通る道順は何通りですか。隣接点間を1歩とします。

練習の答えと確かめ

1. 全体は5個で、X と Y がそれぞれ2個ずつ同じです。番号付きの 5! 通りを、X と Y の交換による 2! × 2! で割ります。5! / (2! × 2!) = 120 / 4 = 30 通りです。X の2位置を選び、残る3位置から Y の2位置を選ぶと、10 × 3 = 30 通りです。残った位置に Z を置けば、各札の個数が元に戻ります。

2. 全体は6枚で、同じ数字の個数は順に2、3、1です。0 がないので、どの札を先頭に置いても6桁になります。6! / (2! × 3! × 1!) = 720 / 12 = 60 個です。例えば 1 の位置を2か所選び、残りから 2 の位置を3か所選ぶと、15 × 4 = 60 通りです。残りの1か所に 3 が入り、それぞれ元の枚数を使い切ります。

3. 最短経路は右3歩と上2歩の計5歩です。右を R、上を U とすると、5! / (3! × 2!) = 10 通りです。U の位置を5歩中2か所選ぶ方法も10通りです。残り3歩が R なので、各列は右3区画、上2区画という目的地の条件に戻ります。左や下の歩があれば余分な歩が必要なので、この列挙で最短経路を漏らしません。

4. A から B は右1歩、上2歩で、3! / (1! × 2!) = 3 通りです。B から C は右2歩、上1歩で、3! / (2! × 1!) = 3 通りです。前後をつなぐと 3 × 3 = 9 通りです。前半で右1、上2、後半で右2、上1なので、合計は右3、上3の6歩です。必ず B を通り、C に最短の6歩で着きます。B で切った2区間の組は一意に戻るので、二重には数えていません。

覚えておくこと

• 同じ文字を仮に区別し、1つの列に対応する番号付きの並びの数で割ります。
• 全体が n 個、同じ種類の個数が a、b、c なら n! / (a! × b! × c!) です。
• 最短経路は方向の列に直し、通過点で区切った道順の数を掛けます。
• 区切った各区間の移動が目的地へ向かう方向か確かめます。

途中式のどこを見るか

答えが大きすぎるときは、まず同じ文字の個数を数え、分母の階乗が全部そろっているか調べます。小さすぎるときは、異なる文字まで同じものとして割っていないか、あるいは既に除いた重複をもう一度割っていないかを見ます。実際に番号を付けて交換し、番号を消した列が変わるかを比べると、原因を特定できます。

個別指導で確かめるなら、5文字の例で「1つの列に番号付きの並びが何通り対応するか」を、A と B の位置を指しながら説明してもらいます。経路では、通過点で前半と後半に切り、各区間の右と上の歩数を書いてもらいます。積を使った後は、できた道順を点で切って元の2区間へ戻せるかも確認します。数える対象と、同じとみなす範囲が定まれば、割る数の意味が見えてきます。