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