上野竜生です。図が与えられていて最短経路が何通りあるかを求める方法を紹介します。
基本 ↑に何回・→に何回いくか考える
図のような道がある。今左下の点から右上の点まで最短経路で進む。
(1) 進み方は何通りあるか？
(2) ×がついた道は通行止めであるとする。進み方は何通りあるか？
裏技：効率よく全部数える こともできますがこの程度なら計算でできます。
最短経路は「↑4つと→6つ」を並べ替えてできる数と等しいことがわかりますね。順番はどうであれ↑4回と→6回進まなくてはいけませんからその順番の決め方だけでいいのです。
(2)は全体から通行止めを通るやり方をひけばいいですね。
答え(1) ↑4つと→6つを並べ替えるやり方に等しい。よって10C4=210通り。
(2) 通行止めの道の左の点をP,右の点をQとする。通行止めを通るやり方を数える。
スタートから点Pまでの行き方は「↑3つ→3つ」の並べ替えなので6C3=20通り。
点Qからゴールまでの行き方は「↑1つ→2つ」の並べ替えなので3C1=3通り。
よって通行止めを通るのは20×3=60通り。
通行止めを通らないのは210-60=150通り。
裏技 効率よく全部数える
下の図のように各頂点への行き方が何通りあるかをすべて書き出すこともできます。
スタート地点からまっすぐ上には1通りしかいけません。まっすぐ右も1通りしかいけません。残りの点については「1つ左の点から→」・「1つ下の点から↑」といけるので1つ左の点と1つ下の点に書かれた数字の和になります。
これを繰り返しゴール地点に書かれる数字が求める場合の数となります。
応用
図のような道路がある。後戻りせずに左下の点から右上の点まで行く方法は何通りあるか？なお斜め方向（／）にも道がある。
斜めを1回も通らないとき
↑3個と→5個の並べ替えなので8C3=56通り。
斜めを1回通るとき
↑2個・斜め1個・→4個の並べ替えなので\(\displaystyle \frac{7!}{2!1!4!}=105\)通り。
斜めを2回通るとき
↑1個・斜め2個・→3個の並べ替えなので\(\displaystyle \frac{6!}{1!2!3!}=60\)通り。
斜めを3回通るとき
斜め3個・→2個の並べ替えなので5C2=10通り。
以上より56+105+60+10=231通り。
こちらも図で書くと下のようになります。
解説を読んで数学がわかった「つもり」になりましたか？数学は読んでいるうちはわかったつもりになりますが演習をこなさないと実力になりません。そのためには問題集で問題を解く練習も必要です。オススメの参考書を厳選しました
<高校数学>上野竜生です。数学のオススメ参考書などをよく聞かれますのでここにまとめておきます。基本的にはたくさん買うよりも…
上野竜生です。大学数学の参考書をまとめてみました。フーリエ解析以外は自分が使ったことある本から選びました。 大…
上野竜生です。当サイトでも少し前まで各ページで学習サイトをオススメしていましたが他にもオススメできるサイトはた…
