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