基本例題 28
最短経路の数
右の図のように, 南北に7本, 東西に6本の道がある。
(1) 0地点を出発し, A地点を通り, P地点へ最短距
離で行く道順は何通りあるか。
(2) 0地点を出発し,B地点を通り, P地点へ最短距
離で行く道順は何通りあるか。 ただし, C地点は通
れないものとする。
[類 島根大 ]
CHART & SOLUTION
最短経路 同じものを含む順列で考える
右へ1区画進むことを, 上へ 1区画進むことを ↑ で表すとき, 例
えば右の図のように0地点からA地点に最短距離で行く道順は
→↑→↑↑ と表される。
解答
(1) 0地点からA地点までの道順は
最短経路の総数は2個, 13個を1列に並べる 同じものを含む順
列の総数に等しい。
(1) O→A, A P と分けて考える。 積の法則を利用。
(2) O→B→Pの道順の数から, O→B→C→P の道順の数を引けばよい。
5!
2!3!
-=10 (通り)
西
6!
A地点からP地点までの道順は
4!2!
よって, 求める道順は 10×15=150 (通り)
5!
4!1!
=5(通り)
(2) O地点からB地点までの道順は
C地点も通れるとした場合, B地点からP地点までの道順は
6!
2!4!
-=15 (通り)
B地点からC地点を通り, P地点まで行く道順は
2!
1!1!
-X1x -=2×1×3=6 (通り)
3!
1!2!
よって, C地点を通らずにB地点からP地点まで行く道順は
15-6=9 (通り)
したがって, 求める道順は 5×9=45 (通り)
0
-=15 (通り)
A
0
北
南
B
E
P
C
HD
•C東
基本 27
←→2個, 13個の順列。
A
←→4個, 12個の順列。
積の法則。
図のように
D,E地点
を定める。
B→D
2!
1!1!
(通り)
D→C→E_1(通り)
3!
E→P
(通り)
1!2!
