方 1 AからBへの経路は, C地点を通る場合と通らない場合の 2つのバターンがある。
融点に最短経路で行くとき, 次のような道順は全部
「右の図のような格子状の道路網がある.A地点から
最短経路の問題2)
202
間のような格子状の道路網がある.A地点から
B
何通りあるか
C地点を通らない場合
C地点もD地点も通らない場合
D
C
よう
A
そこで,n(C)=n(U)-n(C) を利用して、
(Cを通らない道順)= (AからBへの全道順)-(Cを通る道順)
と考える。
0 coD=CUD より, n(CND)=n(CUD)=n(U)-n(CUD) を利用。
(CもDも通らない道順)3D(AからBへの全道順)- (CまたはDを通る道順)
ここで, n(CUD)=n(C)+n(D)-n(CnD)より,
(CまたはDを通る)=(Cを通る)+(Dを通る)- (CかつDを通る)
w
■ 1) A地点からB地点へのすべての道順は,
B
-=462 (通り)
6!5!
B
|AC
C地点を通る道順は,
4!
6!
2!2!
-=120 (通り)
3!3!
よって, 求める道順は,
(2) D地点を通る道順は,
A
462-120=342 (通り)
3!
1!2!
7!
C地点を通る道順
=105(通り)
4!3!
(A→Aの道順)
4!
通り
C地点かつD地点を通る道順は,
2!2!
4!
-X
2!2!
2!
3!
(A'→B'の道順)1通り
-=36 (通り)
1!2!
第6
したがって, C地点またはD地点を通る道順は,
120+105-36=189(通り)
6!
通り
3!3!
(B'→Bの道順)
よって,求める道順は,
Focus
(1)より,C地点を通る道
順は 120 通り
462-189=273 (通り)