この記事では高校数学「数学A」で学ぶ単元「場合の数」で出てくる、最短経路の道順について解説をしていきます。
最短経路の道順を求める問題のポイントは、
最短経路の数＝横と縦の矢印の並べ方
となっていることを利用することです。
すると、組合せの考え方を使って簡単に最短経路の道順を求めることができますよ！
それでは、順番に見ていきましょう。
【準備】同じものを含む順列
問題1 5つの文字 A，A，B，B，B を一列に並べたとき、並べ方は何通りあるか。
2つのAと3つのBを入れる、5つの枠を用意します。
この5つの枠からAを入れる2つの枠を選ぶと、Bは残った場所に入れるしかありません。
したがって、5つの枠からAを入れる2つの選び方を計算して
\[ {}_5 \mathrm{C}_2=\frac{5\cdot 4}{2\cdot 1}=10 \]
よって、答えは10通りとなります。
問題2 7つの文字 ↑，↑，↑，→，→，→，→ を一列に並べたとき、並べ方は何通りあるか。
先ほどの文字であったものが、矢印に変わっただけです。
矢印は全部で7つあるので、7つの枠を用意します。
この7つの枠から「↑」を入れる3つの枠を選ぶと、「→」は残った4カ所に入れるしかありません。
したがって、7つの枠からを入れる「↑」を入れる3つの枠の選び方を計算して
\[ {}_7 \mathrm{C}_3=\frac{7\cdot 6 \cdot 5}{3\cdot 2\cdot 1}=35 \]
よって、答えは35通りとなります。
最短経路の道順は矢印の並べ方と同じ
まずは次の問題を考えてみましょう。
問題3 図のような道路があるとき，A地点からB地点まで行く最短経路の道順は何通りあるか求めなさい。
ここでは、最短経路と矢印が対応してることに注目します。
例えば、青色の経路は、「縦、縦、縦、横、横、横、横」と進んでいます。つまり、これは７つの矢印を並べた「↑↑↑→→→→」と対応しています。
オレンジ色の経路は「横、縦、縦、横、横、縦、横」と進んでいます。これは７つの矢印を並べた「→↑↑→→↑→」と対応しています。
赤色の経路は「横、横、横、縦、横、縦、縦」と進んでいます。これは７つの矢印を並べた「→→→↑→↑↑」と対応しています。
このように考えると
最短経路の数＝7つの矢印「↑↑↑→→→→」の並べ方
となります。
「↑↑↑→→→→」の並べ方は「同じものを含む順列」なので
\[ {}_7 \mathrm{C}_3=\frac{7\cdot 6 \cdot 5}{3\cdot 2\cdot 1}=35 \]
よって、答えは35通りとなります。
もう１問解いてみましょう。
問題4 図のような道路があるとき，A地点からB地点まで行く最短経路の道順は何通りあるか求めなさい。
ここでも同様に、最短経路と矢印が対応してることに注目します。
AからBまで行くためには「横に5区画、縦に4区画」進む必要があります。
すなわち、最短経路の道順は「→→→→→↑↑↑↑」を並べたものと等しくなります。
したがって
\[ {}_9 \mathrm{C}_5={}_9 \mathrm{C}_4=\frac{9\cdot 8 \cdot 7 \cdot 6}{4\cdot 3\cdot 2\cdot 1}=126 \]
よって、答えは126通りとなります。
最短経路を求める公式
最後に、最短経路を求める公式をご紹介します。
（長方形の経路の場合）
横の区画が\( m \) 個、縦の区画が\( n \) 個のとき，最短経路の総数は
\( \quad {}_{m+n} \mathrm{C}_m 通り\)
となります。
これは最短経路が、縦向きの矢印「↑」が\( m \) 個と横向きの矢印「→」\( n \) 個を並べる並べ方と同じであることから、明らかですね。
今回は以上です。
最後までお読みいただきありがとうございました。
