「同じ文字が含まれているときの並べ替えってどう計算するの？」
「街路樹のようなグリッド（格子）上の『最短経路』の問題が苦手…」
これまでに学んだ順列（$_nP_r$）では、すべてのものが「区別できる（異なるもの）」ことが前提でした。
しかし、実際のテストでは「Aが3個、Bが2個あるときの並べ替え」のように、区別がつかない同じものが含まれるパターンが頻出します。
今回は、同じものを含む順列の公式 $\frac{n!}{p!q!r!}$ の仕組みと、受験・テスト必出の「最短経路（道順）の問題」への応用解法を分かりやすく解説します！
1. 同じものを含む順列とは？
例えば、「A, A, A, B, B」 という5つの文字を一列に並べる場面を考えてみましょう。
もしこれらがすべて異なる文字（A₁, A₂, A₃, B₁, B₂）であれば、並べ方は $5! = 120$ 通りです。
しかし実際には、「A」同士、「B」同士の区別がつきません。
そのため、$5!$ のままだと「同じ並び順」を何度も重複して数えてしまうことになります。
重複して数えてしまった分を割り算で取り除くのが、同じものを含む順列の基本的な考え方です。
2. 同じものを含む順列の公式
💡 【同じものを含む順列の公式】
全体 $n$ 個のうち、$p$ 個、$q$ 個、$r$ 個…のように同じものがそれぞれ含まれているとき、これらすべてを一列に並べる場合の数は、
$$\mathbf{\frac{n!}{p!q!r!\cdots} \quad \text{通り}}$$
（※ただし $p + q + r + \cdots = n$）
なぜ階乗で割るの？（公式の成り立ち）
先ほどの 「Aが3個、Bが2個（計5個）」 を並べる例で考えてみましょう。
- 仮に区別をつけて並べる $\to$ $5!$ 通り
- A の内部での入れ替えを解消する3個の A（A₁, A₂, A₃）の並べ替えは $3! = 6$ 通りあります。見た目上はすべて同じ「A A A」になるため、$3!$ で割ります。
- B の内部での入れ替えを解消する2個の B（B₁, B₂）の並べ替えは $2! = 2$ 通りあります。見た目上はすべて同じ「B B」になるため、$2!$ で割ります。
したがって、計算式は以下のようになります。
$$\frac{5!}{3!2!} = \frac{120}{6 \times 2} = \mathbf{10 \text{通り}}$$
3. 【実践例題1】文字列の並べ替え問題
定期テストでよく出る英語の単語を使った並べ替え問題です。
【例題】
「INDIAN」の6つの文字すべてを使ってできる順列は何通りあるか。
解答・解説
まず、含まれている文字の内訳を整理します。
- I ： 2個
- N ： 2個
- D ： 1個
- A ： 1個
- 合計 ： 6個
同じものが 「Iが2個」「Nが2個」 含まれているので、公式 $\frac{n!}{p!q!}$ を使います。
$$\frac{6!}{2!2!} = \frac{720}{2 \times 2} = \mathbf{180 \text{通り}}$$
【答え】 180通り
4. 【超重要】最短経路（道順）問題への応用！
同じものを含む順列の考え方は、図形問題である「格子状の最短経路」を求める際に大活躍します。
なぜ「道順」が「同じものを含む順列」になるの？
下図のような、地点 A から地点 B へ行く最短ルートを考えてみましょう。
B ○---○---○---○
| | | |
○---○---○---○
| | | |
A ○---○---○---○
最短で行くためには、どのようなルートを通っても必ず「右に3コマ（→→→）」「上に2コマ（↑↑）」進む必要があります。
つまり、どんなルートを通るかということは、「→」3個と「↑」2個の計5個をどう並べるかという問題と完全に同じなのです！
【例1】 → → → ↑ ↑ （右へ3つ行ってから上へ2つ）
【例2】 → ↑ → ↑ → （ジグザグに進む）
【実践例題2】途中の点を通る最短経路
下の図のような道路網がある。A から C を通って B まで行く最短の道順は何通りあるか。
(C) (B) ○---○---○---○---○ | | | | | ○---○---○---○---○ | | | | | ○---○---○---○---○ (A)※ A は左下 $(0,0)$、C は $(1,2)$ の位置、B は右上 $(4,2)$ の位置とする。
解答・解説
「A $\to$ C」と「C $\to$ B」の 2つの区間に分けて計算し、積の法則で掛け合わせます。
- A から C への道順
- 右方向（→）：1コマ
- 上方向（↑）：2コマ
- 計3コマ の並べ替え $\to$ $\frac{3!}{1!2!} = \mathbf{3 \text{通り}}$
- C から B への道順
- 右方向（→）：3コマ
- 上方向（↑）：0コマ（直線）
- ※上には進まないため、右に進む 1通り だけです。
- （計算で書くなら $\frac{3!}{3!0!} = \mathbf{1 \text{通り}}$）
- 積の法則で掛け合わせる$$3 \times 1 = \mathbf{3 \text{通り}}$$
【答え】 3通り
5. まとめ
- 同じものを含む順列：同じものの個数の階乗（ $p!, q! \cdots$ ）で全体（ $n!$ ）を割る！
- 公式： $\mathbf{\frac{n!}{p!q!r!}}$
- 最短経路問題：右方向「→」と上方向「↑」の並べ替え問題に置き換えて解く！
同じものを含む順列マスターになれば、一見難しそうな道のり計算も秒殺できるようになります。
次回は、いよいよ「選ぶだけで並べない」グループ作りの基本「第37回：組み合わせ C の計算方法と順列 P との違い」を解説します！
参考PR
- 安さ＆予備校級の講義動画なら 👉 [スタディサプリ高校講座]
- 定期テスト＆推薦入試対策なら 👉 [進研ゼミ高校講座]
- 難関大突破＆記述・添削なら 👉 [Ｚ会の通信教育]
コメント