Question

アルフィー

どなたか解説お願いいたします

(2) 右図のようにp, qが通れない道をAか
らBまで行くことを考える.最短経路の数
はいくつあるか.
B
q
p
A

185
12) (解I) Pを通ってAからBまで行く最短経路
の総数は
2CI×,C2=20(通り)
qを通ってAからBまで行く道の総数は
C2×2C1=20(通り)
pとqを通ってAからBまで行く方法は
2CIX&C1×2C1=8(通り)
よって, p, qの少なくとも一方を通って,
AからBに行く道の総数は
P:pを通る
Q:qを通る
20+20-8=32(通り)
よって, pもqも通らないでAからBまで行く方法は
56-32=24(通り)
Z
(2+9)通り
X-
(解I)右の上図において, ある点Zに到達する
道は,1つ左の点X経由と1つ下の点Y経由の
2つがあり,それ以外にはない. よって, 点X,
点Yに到達する道の数がそれぞれ, む通り, y
通りあるとき、点Zに到達する道の数は
(エ+y)通りある.
通り
9通り
Y
8 14 17
B
24
3
4 6 g
3
7
12
3
4
2
p
よって, 求める道の数は右の下図より
A 1
24通り
11
P
4
11