高1スタンダードレベル数学ⅠAⅡB
最短経路
例題
図のような道のある町で、 A から B までの最短経路のうち、次のものの総数を求めよ。
(1) 最短経路すべて
(2) P を通らない
(3) P を通り，×を通らない
①最短経路の総数を求めるには，同じものを含む順列の考え方を使おう。
②通らない場合は通る場合の余事象として考えよう。
③ある道を通る→その道の直前の点までの進み方と，直後の点からの進み方に分けよう。
右に 1 区画進むことを→，上に 1 区画進むことを↑で表す。
(1) A から B までの最短経路は，→ 6 個と↑ 5 個の順列で表される。
よって
(
通り
)
(2) P を通る最短経路は， A → P → B
A から P の最短経路は，→ 2 個と↑ 2 個の順列
P から B の最短経路は，→ 4 個と↑ 3 個の順列
よって，
P
を通る最短経路は
(
通り
)
したがって
P
を通らない最短経路は
(
通り
)
(3) ×の両端の点を Q ， R とすると，
P と×の両方を通る最短経路は， A → P → Q → R → B より
(
通り
)
よって P を通り，×を通らない最短経路は
(
通り
)
志望校合格に役立つ全機能が月額2,178円（税込）!!
いかがでしたか？
正直なところ解説を読んだだけではスッキリよく分からない方もいるかもしれません。
そういう方もまったく悩む必要はありません。
数学は基礎の積み重ねです。
「理解」した上で１つ１つ積み重ねていけば、学力は向上していきます。
１つ１つの積み重ねを着実に実行していくには、解き方の丸暗記ではなく、しっかり理解した上で問題を解き，自信のない場合は繰り返したり、もう一つ基礎に戻る、といった反復が必要です。
スタディサプリでは、「授業を聞いて理解」した上で問題を解くことができるようになります。
また、巻き戻しもできますし同じ授業を何回でも見れるので、理解できないまま置いていかれるということはありません。ぜひお試しください。
また学年別に、基礎/ 応用 / 発展の3レベルの講義動画をラインナップしていますので、分からなければ基礎に戻る、理解を深めたければ応用や発展に進む、ということがいつでも可能です。
それぞれの目標や目的に最適なレベルが選択できますので、つまづきや苦手克服を解消でき、確実に実力がアップしていきます！
志望校合格に役立つ全機能が月額2,178円（税込）!!
(1) 最短経路の総数を求めるには，同じものを含む順列の考え方を用います。
この問題の場合， A から B へ最短で進むには必ず右に 6 回と上に 5 回進むことになるので，
「右に進む」 6 個と「上に進む」 5 個を並べる順列の数が，最短経路の総数になります。
よって，同じものを含む順列の考え方から
となります。この計算では分子の 11! の 6 から 1 までの部分は分母の 6! と一致するため，
まとめて約分をしています。
(2) 通らない場合の総数を直接求めるのは難しいので，通る場合の余事象として考えるのが一般的です。点 P を通る点 A から点 B までの最短経路の総数は，点 A から点 P までの最短経路の総数と，点 P から点 B までの最短経路の総数から求められます。
点 A から点 P までの最短経路の総数は，「右に進む」 2 個と「上に進む」 2 個を並べる
順列の数と等しく，同様に点 P から点 B までの最短経路の総数は「右に進む」 4 個と
「上に進む」 3 個を並べる順列の数と等しくなっています。よって，
点 P を通る点 A から点 B までの最短経路の総数は
となるので， (1) で求めた点 A から点 B までの最短経路の総数からこれを引くことで
と求められます。
(3) (2) と同様に余事象の考え方を用います。まずは × の部分を通る最短経路の総数を求めますが，異なるのは (2) ではある点を通る最短経路の総数だったのに対し，
こちらはある道を通る最短経路の総数について考えるということです。
このときには，ある道の直前と直後の点を通る，と考えて総数を求めます。
まず， × のついた道の両端の点を Q ， R とします。
そうすると点 P と×を通る点 A から点 B までの最短経路は
点 P ，点 Q ，点 R の 3 点を通る点 A から点 B までの最短経路となり，
(2) で点 P を通る点 A から点 B までの最短経路の総数を求めたのと同じように求められます。
点 A から点 P までの最短経路の総数は (2) より
通り，点
P
から点
Q
，点
Q
から点
R
は
それぞれ 1 通りずつ，点 R から点 B は「右に進む」 2 個と「上に進む」 3 個を並べる
順列の数と等しいので，
通りとなります。以上より，点
P
と×を通る場合は
となるので，点 P を通り×を通らない最短経路は， (2) で求めた点 P を通る総数からこれを引いて
となります。「～しない場合の数」を求める場合，最後に引くことを忘れないよう注意しましょう。