Question

にゃんちゅう

この問題の（2）の解説をお願いしたいです！

基礎問
112 道の数え方
(1)右図のような道をAからBまで行くこと
を考える。
(i) 最短経路の数はいくつあるか。
(i)(i)のうち, Cを通るものはいくつある
A
か。
(2)右図のように p, qが通れない道をAか
らBまで行くことを考える.最短経路の数
はいくつあるか.
q
p
A
(1)たとえば, 右図の色の線で表される道に
ついて考えてみましょう. この道をタテ,
ヨコで分割して一列に並べると|,, 一,
D
精|講
1,-, 1, -, ーとなっています. 他の道も「一」
A
5本と「|」3本を並べかえたものになります。 一例として, A→D→Bと
外の辺をまわる道は||| ーと表せます。 よって, 105で学んだ
同じものを含む順列で片付けられます。あるいは, 8個のワクロロロ00
ロロロ のうち,「|」を入れる3か所を選ぶ(&Cs) と考えれば, 組合せでも
計算できます。
(2) 道が欠けているとき (通ってはいけない道があるとき)の考え方はいろい
ろあります。ここでは2つ紹介します。
解答
(1)(i) 「|」3本, 「一」 5本を並べると考えて,
8!
8.7·6
-=56 (通り) (&C。でもよい)
5!3!
3·2
(i) Aから C, およびCからBの最短経路の数を考えて、
3!
5!
-X
-=3×10=30 (通り)
3!2!
同時に起こる場合は積
100

(解I) Pを通ってAからBまで行く最短経路
の総数は
2C;×,C2=20(通り)
qを通ってAからBまで行く道の総数は
SC2×。C」=20(通り)
pとqを通ってAからBまで行く方法は
2C;×Ci×2Ci=8(通り)
よって, p, qの少なくとも一方を通って
AからBに行く道の総数は
P:p
Q:q
20+20-8=32 (通り)
63839
よって, pもqも通らないでAからBまで行く方法は
56-32=24(通り)
X一
(解I)右の上図において, ある点Zに到達する
道は,1つ左の点X経由と1つ下の点Y経由の
2つがあり,それ以外にはない. よって, 点X,
通り
通り