基礎問
168 第6章 順列組合せ
104 道の数え方
(1) 右図のような道をAからBまで行くこと
を考える。
(最短経路は何通りあるか.
(6) (i)のうち,Cを通るものは何通りある
か
A
C
(右図のように p, q が通れない道をAか
らBまで行くことを考える. 最短経路は何
通りあるか.
q
P
A
代
(1) たとえば,右図の色の線で表される道に
D
|精講
ついて考えてみましょう。 この道をタテ,
ヨコで分割して一列に並べると|, 一, 一,
1, -, 1, -, -となっています. 他の道も「一」
A
5本と 「」 3本を並べかえたものになります. 一例として, ADB2
外の辺をまわる道は|||—————と表せます。 よって、 97 で学んだ
じものを含む順列で片付けられます。
あるいは、8個のワク□□□□□□□□のうち、「|」を入れる
所を選ぶ (C3) と考えれば,組合せでも計算できます。
(2) 道が欠けているとき (通ってはいけない道があるとき)の考え方はいろい
ろあります。 ここでは2つ紹介します。