基礎問
184 第6章 順列・組合せ
112 道の数え方
(1) 右図のような道をAからBまで行くこと
を考える.
(i) 最短経路の数はいくつあるか.
(i)(i) のうち,Cを通るものはいくつある
か.
(2) 右図のように p q が通れない道をAか
らBまで行くことを考える. 最短経路の数
はいくつあるか.
PEDate
精講
A
A
解答
(1)(i)「|」3本, ｢一｣ 5本を並べると考えて,
8! 8-7-6
5!3! 3-2 =56 (通り) (gCでもよい)
D
(1) たとえば、右図の色の線で表される道に
ついて考えてみましょう. この道をタテ,
ヨコで分割して一列に並べると|, -, -,
A
1, -, 1, -, -となっています。 他の道も「一」
5本と「|」3本を並べかえたものになります. 一例として, A→D→Bと
外の辺をまわる道は|||—————と表せます. よって, 105で学んだ
同じものを含む順列で片付けられます. あるいは, 8個のワクロロ
□□□ のうち,「|」を入れる3か所を選ぶ (8C3) と考えれば,組合せでも
計算できます.
p
() AからC, およびCからBの最短経路の数を考えて,
2!1!3!2! -=3×10=30 (通り)
3! 5!
×
q
N 100
(2) 道が欠けているとき (通ってはいけない道があるとき)の考え方はいろい
ろあります. ここでは2つ紹介します.
B
同時に起こる場合は積
B
(2)(解)を通ってAからBまで行く最短経路
の総数は
2C1×5C2=20 (通り)
を通ってAからBまで行く道の総数は
5C2×2C1=20 (通り)
pとqを通ってAからBまで行く方法は
2C1×2C1×2C1=8 (通り)
よって, p, qの少なくとも一方を通って
AからBに行く道の総数は
20+20-8=32 (通り)
よって, pもqも通らないでAからBまで行く方法は
56-3224 (通り)
( 解ⅡI) 右の上図において, ある点Zに到達する
道は,1つ左の点X経由と1つ下の点Y経由の
2つがあり, それ以外にはない。 よって, 点X,
点Yに到達する道の数がそれぞれ, 通り, y
通りあるとき, 点Zに到達する道の数は
(x+y) 通りある.
よって, 求める道の数は右の下図より
24通り
② ポイント
演習問題 112
A
*
右図のような道をAからBまで行くこと
を考える.
(1) 最短経路の数はいくつあるか.
(2) (1) のうち,Pを通らないものはいくつあ
るか.
4
3
P:pを通る
Q:qを通る
通り
n
P
8
Y
A
(x+y)通り
通り
14 17
185
4 6 q 13
2
最短経路の数は、 縦棒と横棒の並べかえと考える
B
124
17
13 4
11 1 1 1
B
第6章
