Question

アオリ

(3)のPを通る道順の数の求め方がなぜこのようになるのか教えてください。

378
基本例題 30 最短経路の数
右の図のように,道路が碁盤の目のようになった街がある。
地点Aから地点Bまでの長さが最短の道を行くとき、次
の場合は何通りの道順があるか。
[類 東北大]
全部の道順
地点 C を通る。
(3) 地点Pは通らない。 (4) 地点Pも地点Qも通らない。
基本27
指針
AからBへの最短経路は、右の図で右進 または上進 する
ことによって得られる。 右へ1区画進むことを→, 上へ1区
画進むことを ↑ で表すとき, 例えば、 右の図のような2つの
最短経路は
赤の経路なら
1→→11→1→1
青の経路なら 111→→11→1→→
で表される。したがって, AからBへの最短経路は、
つまり
ここで
つまり
(502)
右へ1区画進むことを→, 上へ 1区画進むことを↑で表す。
解答 (1) 最短の道順は5個, 16個の順列で表されるから
UELSSO
11!
5!6!
11･10･9・8･7
5･4･3･2･1
462 (通り)
(2) AからCまでの道順, CからBまでの道順はそれぞれ
20-
3!
1!2!
よって、求める道順は
→5個, 16個の同じものを含む順列で与えられる。
(2) A → C, C → B と分けて考える。 積の法則を利用。
(3) (Pを通らない)=(全道順) (P を通る) で計算。
(4) すべての道順の集合を UPを通る道順の集合を P, Q を通る道順の集合をQと
=3(通り),
すると, 求めるのはn (PnQ)=n(PUQ)=n(U) -n (PUQ) ド・モルガンの
法則
(PもQも通らない)=(全道順)-(PまたはQを通る)
個数定理
n(PUQ)=n(P)+nQnPnQ)
(PまたはQを通る) = (P を通る) +(Qを通る) (PとQを通る)
(3) P を通る道順は
よって, 求める道順は
8!
4!4!
3×70=210 (通り)
-=70(通り)
5! 5!
2!3! 2!3!
× -=10×10=100 (通り)
7!
(4) Q を通る道順は
3!4!
PとQの両方を通る道順は
462-100=362 (通り
3!
1!2!
X
-=35×3=105 (通り)
5! 3! [T=48214
×
-=10×3=30(通り)
2!3!
よって,PまたはQを通る道順は
ゆえに、求める道順は
AL
1!2!
A
100+105-30=175 (通り)
462-175=287 (通り)
C
C
P
7
組合せで考えてもよい
次ページの 別解 参照。
AからCまでで
→1個, 12個
CからBまでで
4個, 14個
を通らない)
=(全体) (Pを通る)
10802
artil
▼PからQに至る最短の
NUE
道順は1通りである。
別
検討
(1
3

A
C
C
P
P
Q
Q
A
*30.0*2
B
B

組み合わせ 順列