74
の
北
基本例題 27 最短経路の数
(1) 0地点を出発し, A地点を通り, P地点へ最短距
ま 西
A
右の図のように、 南北に7本, 東西に6本の道がある。
(2)) 0地点を出発し, B地点を通り, P地点へ最短距
0°
離で行く道順は何通りあるか。
B
離で行く道順は何通りあるか。 ただし, C地点は通
[類島根大)
南
基
れないものとする。
MOT
HART O SOLUTION
C
最短経路 同じものを含む順列で考える
右へ1区画進むことを→,上へ1区画進むことを↑で表
すとき,例えば右の図のようにO地点からA地点に最短距
離で行く道順は→↑→↑↑ と表される。
最短経路の総数は→2個, 13個を1列に並べる同じもの
を含む順列の総数に等しい。
(1) O→A, A→Pと分けて考える。積の法則を利用。
(2) 0→B→P の道順の数から, O→B→C→P の道順の数を引けばよい。
0
著
つ地点からA地点までの道順は
5!
-=10(通り)
2!3!
合→2個, ↑ 3個の
点からP地点までの道順は
6!
-=15(通り)
4!2! AO
て, 求める道順は
10×15=150(通り)
合↓4個, 1 2個の
也点からB地点までの道順は
5!
積の辻前
U