最短経路 | 同じものを含む順列の考え方で問題を解く
" 最短経路 “についての問題を高校一年の数学で学習します。
最短の経路が何通りあるのかを求めるときに、順列が何通りあるのかを計算する公式を同じものが含まれているということで修正する必要があります。
異なる n 個もので順列を考えると n! 通りですが、n 個の中に同じものが含まれているときに、どうするのか。
何通りあるのかを数えるという観点から、越えるべき壁にどう対処するのかを解説します。
最短経路の問題を解くために使う同じものを含む順列の数え方から説明します。
最短経路 :同じものを含む順列で準備
最短経路の問題を解くためには、基礎となる理論を押さえることが大切になります。
基礎をしっかりと築き足場を固めるところからスタートします。
この基礎となるのが「同じものを含む順列」の数え方です。
抽象的な証明もできるのですが、具体的な状況で、着実に数えられるようにすることに焦点を当て、難しい公式の証明をしないことにします。
実は、同じものを含む順列が何通りあるのかということを示すためには組合せの発想を使いまして、組合せの公式については、リンク先の記事で大学の数学を使って厳密証明をしています。
同じものを含む順列の公式の厳密な証明はしませんが、その考え方自体は、具体的に数えながら伝えるようにしています。
具体的に数える練習
【同じものを含む順列の例】
JAPAN に使われている 5 つの文字を並び替えた順列が何通りあるのかを数えます。
英語の意味は気にせず、J, A, P, A, N の 5 つの文字を一列に並べて順列を可能な限り作ります。
このときに、順列が全部で何通りできるのかを考えます。
A と A が区別のない文字なので、異なる 5 つを並べるという公式がストレートに使えない状況です。
5 つの文字が異なっていると順列の総数を求める公式が使えるという状況でもあります。
そこで、A1, A2 と番号をつけて一旦は区別をします。
JA1PA2N だと異なる 5 つの文字なので、順列の総数が何通りかを計算することができます。
5! = 5・4・3・2・1
= 120 （通り）
とりあえず区別をして 120 通りと仮に数えておきます。
この 120 通りの中には、
JA1PA2N と JA2PA1N が、それぞれ区別されて、どちらも 1 通りとしてカウントされ、120 通りの中の 2 通りとなっています。
ここで、区別をなくします。
すると、JAPAN と JAPAN は同じなので、1 通りです。
つまり、120 通りの順列の中で、A1 と A2 だけが入れ替わっていて、他の文字の並びが同じものが 1 つに集約されます。
A1 と A2 の入れ替え方は、2! なので、区別のない 2 つの文字を含んだ 5 つの文字の並べ方は、次のように計算できます。
5! ÷ 2! = 120 ÷ 2
= 60 （通り）
この計算をよく見ると、
(5・4 ÷ 2!) × 3! です。
5・4 ÷ 2! は、5C2 という組合せの公式です。
上の内容を組合せを使って考えることができるということも分かります。
□□□□□ という 5 つの箇所から、はじめに区別のない A を置く位置を指定します。
□A□□A□ というように 5 ヵ所から A を置く 2 ヵ所の位置を選ぶ方法は、組合せを使って計算できます。
5C2 通りが、区別のない A を置く 2 ヵ所の選び方です。
□A□□A□ のように 2 つの A を置くと、残りの 3 ヵ所に異なる 3 つの文字を置くことになります。
異なる 3 つの文字を異なる 3 ヵ所に並べるので、3! 通りの並べ方と分かります。
樹形図の発想で積の法則を使うと、
全部で 5C2 × 3! 通りとなります。
計算をすると、
5! ÷ 2! と同じ値になっています。
最短経路の問題を解く前に、もう少し同じものを含む順列の数え方を練習しておきます。
より複雑な順列で練習
【同じものを含む順列の例２】
NIPPON に使われている 6 つの文字を並び替えた順列が何通りあるのかを数えます。
区別のない N が 2 個、区別のない P が 2 個あります。
先ほどの組合せの発想で攻めます。
□□□□□□ という 6 ヵ所から、まず N を配置する 2 ヵ所を選びます。
6C2 通りの選び方があります。
この 6C2 の一つは、例えば、
□N□□N□ というようになっています。
このように、4 ヵ所の □ が残っています。
この 4 ヵ所から、2 つの区別のない P を配置する 2 ヵ所を選びます。
4C2 通りの選び方があります。
これで、区別のない 4 個の文字を配置する位置を選びました。
全部で、6C2・4C2 通りの区別のない文字の配置する位置が決めりました。
そのうちの一つは、例えば、
□NP□NP というような形です。
6C2・4C2 通りのそれぞれについて、残った 2 つの □ の位置に I と O を配置します。
異なる 2 個を 2 ヵ所に並べるので、2! 通りです。
樹形図の発想で積の法則を使うと、
6C2・4C2 × 3! 通りとなります。
これが求める場合の総数です。
このように、組合せの考え方で、区別のない文字の配置先を決定しておいてから、残りの位置に異なる残りの文字を並べるという数え方です。
この考え方で、最短経路の問題の経路を数えます。
最短経路 :問題を実践練習
最短というくらいで、戻らずに進む移動になります。
そのため、A 地点から B 地点への移動は、← と ↓ しか選択肢がありません。
↑ や → の方向へ移動してしまうと、戻ってしまうので、最短経路の移動としては← と ↓ しか移動する方向を考えません。
この最短経路は、上の例に示しているようにデジタルな考え方になります。
←↓←↓↓←← と 7 ヵ所に ← や ↓ を並べると、1 通りの最短経路の移動となります。
4 つの ← と 3 つの ↓ を 7 ヵ所に配置する並べ方の総数が、最短経路の移動の総数となります。
つまり、同じものを含む順列が何通りあるのかということになります。
では、A 地点から B 地点への最短経路の移動が全部で何通りあるのかを数えます。
最短経路の移動が何通りか
7 つの矢印を 7 ヵ所に並べるのですが、4 つの ← は区別がありません。
そして、3 つの ↓ も区別がありません。
そこで、7 ヵ所から、4 つの ← を配置する 4 ヵ所を選びます。
7C4 通りの組合せです。
この組合せの一つ一つについて、それぞれ 3 ヵ所が残っています。
その 3 ヵ所に区別のない 3 つの ↓ を配置します。
区別のないものを配置する場所を選ぶのは組合せを計算します。
3C3 通りです。
これで、7 ヵ所が全て埋まりました。
全部で 7C3・3C3 通りです。
3C3 = 1 なので、計算するのは 7C3 だけです。
(7・6・5) ÷ (3・2・1)
= (7・6・5) ÷ 6
= 7・5 = 35 （通り）
これで、求める最短経路の移動が 35 通りと分かりました。
このように、区別のない同じものを含む順列の総数の数え方の基礎を組合せで理解をしておくと、最短経路のような難しそうな内容でも考えて求めることができます。
最短経路の問題では、↙ のような今回とは異なる移動方法を付け加えたものが出題されることもあります。
ただ、この記事では、基礎に集中して、同じものを含む順列の総数を数えることを解説しました。
場合の数、確率の単元の基礎となる内容は、扱う内容が長いので、息切れせずに、基礎となる内容たちをしっかりと理解して使いこなせるようになることが大切かと思います。
区別について
今回は、区別のない同じものを含む順列の考え方で、最短経路が何通りかを数えました。
要素の個数については、個数定理という記事を投稿しています。
ただ、高校数学で、区別のないものを、どのように処理するのかということについて、確率を定義するために理論上の区別をするというときがあります。
確率を定義するときには、同様に確からしいということが前提になります。
この同様な確からしさとの関わりから、区別のないものだけど、番号をつけるなどして区別するときがあります。
確率についての重要な基礎となる内容なので、これについては他の記事で十分な記述量で解説をしています。
それでは、これで今回の記事を終了します。
読んで頂き、ありがとうございました。