数学

【高校数学A】最短経路の道順は「組合せ」で簡単解決!公式も紹介します

記事内に商品プロモーションを含む場合があります

この記事では高校数学「数学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つの矢印を並べた「→↑↑→→↑→」と対応しています。

赤色の経路は「横、横、横、縦、横、縦、縦」と進んでいます。これは7つの矢印を並べた「→→→↑→↑↑」と対応しています。

このように考えると

最短経路の数=7つの矢印「↑↑↑→→→→」の並べ方

となります。

「↑↑↑→→→→」の並べ方は「同じものを含む順列」なので

\[ {}_7 \mathrm{C}_3=\frac{7\cdot 6 \cdot 5}{3\cdot 2\cdot 1}=35 \]

よって、答えは35通りとなります。

 

もう1問解いてみましょう。

問題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 \) 個を並べる並べ方と同じであることから、明らかですね。

今回は以上です。

最後までお読みいただきありがとうございました。

新コース無料プレゼント

シグマ先生が公開しているUdemyコースの

「最安値クーポン」

を差し上げます。

ご希望の方は、登録フォームからご登録をお願いいたします。

※クーポン配信時期は不定期になりますので、ご了承ください。

Udemyクーポンプレゼント登録フォーム

数学・統計学
シグマ先生
数学講師/Udemyベストセラー講師/数学の苦手を治します/塾・予備校・高校講師歴20数年/分かりやすい解説/偏差値40から65へ/数学検定対策/数学で困っている人の役に立ちたい

妻・子供2人と4人暮らし。週末はキャンプやスキー、温泉旅行などアクティブに活動中/数学検定1級
こちらの記事もおすすめ!