168 第6章 順列組合せ 基礎問 104 道の数え方 (1)右図のような道をAからBまで行くこと を考える。 (1) か、 は何通りあるか Cを通るものは何通りある (2) 右図のように p q が通れない道をAか らBまで行くことを考える。 最短経路は何 通りあるか。 p A (2) (解1) pを通ってAからBまで行く最短経路 の総数は 2C1X6C2=20 (通り) qを通ってAからBまで行く道の総数は C2 ×2C1=20 (通り) とを通ってAからBまで行く方法は 2C1×2Ci×2C1=8 (通り) よって,P, qの少なくとも一方を通って, AからBに行く道の総数は 20+20-8=32 (通り) Ppを通る Q:gを通る よって, pもqも通らないでAからBまで行く方法は 56-32=24(通り) (解Ⅱ) 右の上図において、 ある点Zに到達する 道は1つ左の点X経由と1つ下の点Y経由の 2つがあり,それ以外にはない。よって、点X, 点Yに到達する道の数がそれぞれ, 通り,y 通りあるとき, 点Zに到達する道の数は (x+y) 通りある. 169 X → Z +y)通り 通り (1) たとえば、右図の色の線で表される道に D 精講 B ついて考えてみましょう。 この道をタテ ヨコで分割して一列に並べると|, -, - 通り Y , -, 1, -, -となっています。 他の道も「一」 A 5本と 「」 3本を並べかえたものになります. 一例として, A→D→Bと 8 14 17 B 24 じものを含む順列で片付けられます。 -一と表せます. よって, 97 で学んだ同 3 4643 7 よって, 求める道の数は右の下図より 24通り P 2 12 13 A111 1 の口コ のうち、「|」を入れる3 16