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