基礎問
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