練習 図1と図2は碁盤の目状の道路とし,す
③30
べて等間隔であるとする。
(1) 図1において,点Aから点Bに行
く最短経路は全部で何通りあるか。
また、このうち次の条件を満たすもの
は何通りあるか。
(ア) 点Cを通る。
(イ) 点Cと点 D の両方を通る。
12!
6!6!
(ア) 点Cを通る最短経路は
図 1
D
(ウ) 点Cまたは点Dを通る。
(エ) 点Cと点Dのどちらも通らない。
(2)図2において,点Aから点Bに行く最短経路は全部で何通りあるか。ただし,斜線の部分
は通れないものとする。
[類 九州大]
(1) 右に1区画進むことを,上に1区画進むことを ↑で表すと,
点Aから点 B に行く最短経路の総数は, 6個のと6個の↑
を1列に並べる順列の総数に等しいから
(イ) 点Cと点 D の両方を通る最短経路は
4! 4! 4!
2!2!
x ·X
2!2!
2!2!
B
=216 (通り)
図2
=924 (通り)
←126 から求めてもよい。
4!
8!
× =420 (通り) ←A→C, C→B
2!2! 4!4!
10
←A→C, C→D,
D→B