６同じものを含む順列と最短経路問題：公式と経路数計算のコツ

当ページのリンクには広告が含まれています。

順列の中でも、並べるものの中に同じ種類のものが含まれている場合があります。例えば、「success」という単語の文字を並べ替える場合などです。このような「同じものを含む順列」の計算方法と、その考え方が応用される典型的な問題である「最短経路問題」について、詳しく解説していきます。特に最短経路問題は、一見すると順列の問題には見えませんが、考え方を変えると同じものを含む順列の問題に帰着できる点が重要です。

第1章：同じものを含む順列とは？

まずは、同じものを含む順列の基本的な考え方を理解しましょう。

1. 定義：同じものが含まれる場合の並べ方

n 個のもののうち、p 個は同じ種類 A、q 個は同じ種類 B、r 個は同じ種類 C、… (ただし p + q + r + … = n) であるとき、これら n 個のものすべてを一列に並べる順列を「同じものを含む順列」といいます。
ポイント： 同じ種類のものは、互いに区別しません。例えば、3つの赤い玉がある場合、どの赤い玉がどの位置に来ても区別しません。

2. 具体例：a, a, b の並べ方

a が2個、b が1個の合計3文字を並べる場合を考えます。
もし、2つの a を区別して a1, a2 とすると、並べ方は (a1, a2, b), (a2, a1, b), (a1, b, a2), (a2, b, a1), (b, a1, a2), (b, a2, a1) の 3! = 6 通りです。
しかし、実際には a1 と a2 の区別はありません。
- (a1, a2, b) と (a2, a1, b) は、区別をなくすとどちらも (a, a, b) になります。
- (a1, b, a2) と (a2, b, a1) は、区別をなくすとどちらも (a, b, a) になります。
- (b, a1, a2) と (b, a2, a1) は、区別をなくすとどちらも (b, a, a) になります。
このように、a1 と a2 を入れ替えただけの並び (2! = 2 通り) が、区別をなくすと同一視されます。
したがって、元の 3! = 6 通りを、重複度である 2! = 2 で割ることで、求める場合の数が得られます。
計算： 3! / 2! = 6 / 2 = 3 通り。
実際に書き出すと (a, a, b), (a, b, a), (b, a, a) の3通りであり、計算結果と一致します。

3. なぜ階乗で割るのか？ – 区別の消去

上記の例のように、同じものが p 個ある場合、それらをすべて区別すると p! 通りの並べ替えが考えられます。
しかし、実際にはこれらの区別はないため、全体を区別があるものとして計算した順列 (n!) の中には、この p! 通りの並びがすべて含まれてしまっています。
これらを同一視するために、全体の順列 n! を、同じものの内部での並び替えの数 p! で割ることで、重複を除去します。
同じように、q 個の同じものがあれば q! で、r 個の同じものがあれば r! で割る、という操作を繰り返します。

第2章：同じものを含む順列の計算方法

公式とその使い方を学び、具体的な問題を解いてみましょう。

1. 計算公式：n! / (p! q! r! …)

n 個のもののうち、p 個が同じ種類、q 個が同じ種類、r 個が同じ種類、… (p + q + r + … = n) であるとき、これら n 個すべてを一列に並べる順列の総数は、次の公式で計算できます。
- 総数 = n! / (p! × q! × r! × …)

2. 公式の使い方と例題 (文字の並び替え)

例題1： 「banana」という単語の6文字すべてを使ってできる文字列は何通りあるか？
考え方：
- 全体の文字数 n = 6。
- 同じ文字の種類と個数を確認する：a が 3個 (p=3)、n が 2個 (q=2)、b が 1個 (r=1)。 (3 + 2 + 1 = 6)
- 公式を適用する。
計算：
- 6! / (3! × 2! × 1!) = (6 × 5 × 4 × 3 × 2 × 1) / {(3 × 2 × 1) × (2 × 1) × 1}
- = 720 / (6 × 2 × 1) = 720 / 12 = 60
答え： 60通り
例題2： 赤玉4個、白玉3個、青玉2個の合計9個の玉をすべて一列に並べる方法は何通りあるか？
考え方：
- 全体の個数 n = 9。
- 赤玉が p = 4 個、白玉が q = 3 個、青玉が r = 2 個。(4 + 3 + 2 = 9)
- 公式を適用する。
計算：
- 9! / (4! × 3! × 2!) = (9×8×7×6×5×4×3×2×1) / {(4×3×2×1) × (3×2×1) × (2×1)}
- = 362880 / (24 × 6 × 2) = 362880 / 288 = 1260
答え： 1260通り

3. 注意点：すべてを並べる場合に使う

この公式は、与えられた n 個のものをすべて使って並べる場合に適用されます。
もし、n 個の中から一部を選んで並べる場合は、単純にこの公式を使うことはできず、場合分けなど別の考え方が必要になることがあります。

第3章：最短経路問題への応用

同じものを含む順列の考え方は、格子状の経路を数える「最短経路問題」を解く際に非常に有効です。

1. 最短経路問題とは？ – 格子上の移動

下図のような碁盤の目状の道路（格子）において、ある地点 A から別の地点 B まで、遠回りをせずに（例えば、右または上にしか進めないという条件で）進む経路が何通りあるかを問う問題です。B (終点) | +-+-+ | | | +-+-+ --- A (始点) から右に3、上に2進む経路 | | | A-+-+

2. なぜ同じものを含む順列で解けるのか？

上の図で A から B へ最短経路で進むためには、必ず「右 (→) に3回」「上 (↑) に2回」進む必要があります。どのような経路をたどっても、この回数は変わりません。
つまり、最短経路は、「→」「→」「→」「↑」「↑」という 5回の移動の順番 を決めることと同じになります。
例えば、
- →→→↑↑ という順番は、Aから右に3回進み、次に上に2回進む経路に対応します。
- →↑→↑→ という順番は、右、上、右、上、右と進む経路に対応します。
このように、最短経路の総数は、「→」という文字3個と、「↑」という文字2個の、合計5個の文字を一列に並べる順列の総数と同じになります。
これはまさに「同じものを含む順列」の問題です。

3. 計算方法：「右」と「上」の並び替え

上記の例 (右に3回、上に2回) の場合：
- 全体の移動回数 n = 3 + 2 = 5 回。
- 「→」の個数 p = 3 個。
- 「↑」の個数 q = 2 個。
- 同じものを含む順列の公式を適用します。
計算：
- 5! / (3! × 2!) = (5 × 4 × 3 × 2 × 1) / {(3 × 2 × 1) × (2 × 1)}
- = 120 / (6 × 2) = 120 / 12 = 10
答え： A から B への最短経路は 10通り。

4. 組合せ(C)を用いた計算方法

最短経路問題は、組合せ (C) を使っても解くことができます。
全体の移動回数が (p + q) 回であるとき、そのうちのどのタイミングで「右」に進むか (p 回分) を選ぶ、と考えます。
(p + q) 回の移動の中から、「右」に進む p 回を選ぶ組合せなので、(p+q)Cp と計算できます。
あるいは、(p + q) 回の移動の中から、「上」に進む q 回を選ぶ組合せと考えて、(p+q)Cq と計算することもできます。
nCr = nC(n-r) の性質から、(p+q)Cp = (p+q)Cq となるため、どちらで計算しても結果は同じです。
上記の例 (右に3回、上に2回) で計算：
- 全移動回数 5回。右に3回、上に2回。
- 5C3 = (5 × 4 × 3) / (3 × 2 × 1) = 10
- または、5C2 = (5 × 4) / (2 × 1) = 10
同じものを含む順列の公式との関係：
- (p+q)! / (p! q!) は、まさに (p+q)Cp (または (p+q)Cq) の定義式 n! / {r! (n-r)!} と同じ形をしています。
- つまり、最短経路問題は、同じものを含む順列としても、組合せとしても解くことができるのです。

第4章：最短経路問題の例題と発展

基本的な計算方法に加え、少し条件が付いた最短経路問題の考え方を見てみましょう。

1. 例題：基本的な格子経路

問題： 下図の地点 A から地点 B まで最短経路で行く方法は何通りあるか？ (右に5、上に4進む) +---+---+---+---+--- B | | | | | +---+---+---+---+--- | | | | | +---+---+---+---+--- | | | | | +---+---+---+---+--- | | | | | A +---+---+---+---+---
考え方：
- 右 (→) に 5回、上 (↑) に 4回進む必要がある。
- 全体の移動回数は 5 + 4 = 9 回。
- 9回の移動のうち、どの5回が「→」かを選ぶ組合せ 9C5 (または、どの4回が「↑」かを選ぶ組合せ 9C4) を計算する。
- または、9個の文字 (→を5個, ↑を4個) の同じものを含む順列 9! / (5! 4!) を計算する。
計算 (組合せ)：
- 9C4 = (9 × 8 × 7 × 6) / (4 × 3 × 2 × 1) = (9 × 2 × 7 × 1) / 1 = 126
計算 (同じものを含む順列)：
- 9! / (5! × 4!) = (9×8×7×6×5!) / (5! × 4×3×2×1) = (9×8×7×6) / (4×3×2×1) = 126
答え： 126通り

2. 発展：特定の点を通る経路

問題： 上記の図で、地点 A から地点 C (右に2, 上に2 の点) を経由して地点 B まで最短経路で行く方法は何通りあるか？
考え方：
- この場合、経路を2つの部分に分けて考え、積の法則を適用します。
- Step1: A から C までの最短経路の数
  - 右に2回、上に2回。全移動4回。
  - 4C2 = (4×3)/(2×1) = 6 通り。
- Step2: C から B までの最短経路の数
  - CからBへは、さらに右に (5-2)=3回、上に (4-2)=2回進む必要がある。
  - 全移動 3 + 2 = 5回。
  - 5C3 = 5C2 = (5×4)/(2×1) = 10 通り。
- Step3: 積の法則で掛け合わせる。
計算：
- (A→C の経路数) × (C→B の経路数) = 6 × 10 = 60
答え： 60通り

3. 発展：通れない点や領域がある経路（考え方）

問題： 格子経路上に、工事中などで通れない点や領域がある場合の経路数はどう数えるか？
考え方1：余事象を利用する
- まず、通れない箇所がない場合の全体の最短経路数を計算する。
- 次に、通れない点（または領域内の代表的な点）を必ず通る最短経路数を計算する（上記「特定の点を通る経路」の方法）。
- 全体の経路数から、通れない箇所を通る経路数を引き算する。
- 複数の通れない点がある場合は、包含と排除の原理などが必要になり複雑化することがある。
考え方2：経路数を書き込む
- 各格子点までに到達する最短経路数を、出発点から順に書き込んでいく方法。
- ある点への経路数は、その点の左隣の点への経路数と、真下の点への経路数の和になる（パスカルの三角形と同じ原理）。
- 通れない点は経路数を 0 として扱う（または書き込まない）。
- 地道な方法だが、複雑な制約がある場合に有効。

第5章：まとめと注意点

同じものを含む順列と最短経路問題は、考え方の転換がポイントです。

1. 同じものを含む順列のポイント整理

対象: 同じ種類のものが含まれる n 個のものすべてを一列に並べる。
計算式: n! / (p! × q! × r! × … ) （n は総数、p, q, r… は各種類の個数）
意味: 全体を区別した場合の n! から、同じものの区別をなくすために、その内部の並び替え (p! など) で割る。

2. 最短経路問題のポイント整理

状況: 格子状の経路を、特定の方向にのみ（例：右または上）進む。
考え方: 結局は、各方向への移動回数（右にp回、上にq回など）が決まった「同じものを含む順列」の問題に帰着できる。
計算:
- 同じものを含む順列: (p+q)! / (p! q!)
- 組合せ: (p+q)Cp または (p+q)Cq
応用: 特定の点を通る場合は積の法則、通れない点がある場合は余事象や書き込みを利用。

3. 混同しやすいポイントと使い分け

同じものを含む順列 vs 通常の順列 (nPr): 同じものが含まれる場合は nPr は使えない。nPr は「異なる n 個から r 個選んで並べる」場合に使う。
同じものを含む順列 vs 重複順列: これらは全く異なる概念です。
- 同じものを含む順列: あらかじめ用意されたもの（aがp個, bがq個…）をすべて使い切って並べる。（例：banana の並び替え）
- 重複順列: いくつかの種類のもの（例：数字 1, 2, 3）を、重複を許して並べる。（例：3桁の暗証番号を作る、111もOK）重複順列は n^r で計算されることが多い。
最短経路： 順列としても組合せとしても解釈できるが、どちらの考え方でも同じ計算式に行き着くことを理解しておく。

潜在的なリスクについて:

この記事では、同じものを含む順列の基本公式と、それが最短経路問題にどのように応用されるかを解説しました。「同じものを含む順列」という名前が「重複順列」と似ているため、混同しないように注意が必要です。これらは異なる状況設定で使われる計算方法です。また、最短経路問題において、通れない点や領域が複雑に設定されている場合、本記事で紹介した余事象や書き込みの方法だけでは対応が難しく、より慎重な場合分けや経路の分割・結合といった工夫が必要になることがあります。立体的な格子経路など、より次元の高い問題についても、基本的な考え方は応用できますが、計算はより複雑になります。