右の図のような道路があり,2地点を結ぶ最短距離の
道順を考える。地点Pまでの道順がか通り, 地点Q
基本例題 27 では最短経路の数を求めるとき, 右へ進む記号→,上へ進む記号1のいくつ
かを並べる順列の総数として考えた。ここでは,場合の数を書き込んで求める方法を紹
(足最短経路の数を書き込んで求める
介する。
9
p+q
R
までの道順がg通りあるとき, 地点Rまでの道順は、
p+q通りある。
Q
p
P
地点PからRまでは1通りであるから, 地点Pを通るRまでの道順は
p×1=p(通り)
同様に,地点Qを通るRまでの道順は
したがって,地点Rまでの道順は, 和の法則から
q×1=q(通り)
p+q(通り)
この方法で,基本例題 27 を解いてみよう。
基本例題27 (1)
0地点を出発し,A地点に行くから, 線分 OA を1
つの対角線とする長方形内にあるそれぞれの地点ま
での道順の数を書き込む。更に, A地点からP地点
までについても同様に書き込む。
この結果,O→Aの道順は 10通り, 0→A→Pの道
順は 150 通りあることがわかる。
10 30 60 100
150
P
|10 ||20 |30 |40
50
4
1
10
A
3
6
|2
1
3
0
1
1
基本例題27(2)
同様に書き込むと, O→Bの道順は5通りであるこ
5 15
45
P
5
30
とがわかる。
5 E5
|20
5 C1 10
15
地点D, Eを右の図のように定める。C地点は通れ
ないから, D→C→Eの場合はない。
よって,E地点までの道順は5通りであり,
(5+10=)15通りではないことに注意する。図から,
0→B→Pの道順は 45通り あることがわかる。
いま,地点Cは通れないので, 地点Cを通る道路が
欠けた右下の図を考える。
この場合を書き込むと右上の図と同様の道順の数が
得られ,O→B→Pの道順は 45通り ある。
|2 3
4
D
5
5
B
5
0
1
1
1
5
15
5 10
30
しで仕切り」を入れる
5E5
2C
5
10
15
D
2
3
4
5
5
5
B
1
1
1
1
場路の一部が欠けている場合に有効である。
5P9
