【例題】
右図において, P地点からQ地点に至る最短経路の個数はい
くつあるか。
P•
Q
5
「重複組合せ
異なるn個のものの
この場合は,n<r
列に対応させると,
る。
【解答】矢印の順列に対応させて数える
求める最短経路を途中どこを経由するかで5通りに場合分けする。
(i) A を経由: P→A → Q
4! 4!
-=16通り
3! 3!
(ii) B を経由: P→B′ →B→B" → Q
3!
2!
3!
・1・1・9通り
31.-1.1.3-9
2!
(Ⅲ) Cを経由:P→C→Q
4! 4!
3! 3!
=16通り
(iv) D を経由:P→D→Qは,1通り
(v) E を経由:P→E→Qは,1通り
←PAは,→→→ ↑の順列,
A→Qは, ↑↑↑→の順列に
対応する。
D
Q
C
B
B"
B'
A
P
E
↑
(i)~(v)の場合は同時には起こらないので,
16+9+ 16+1+1=43通り
途中, A, B, C,D,E のど
こかを必ず経由し, A~E
のうち重複して経由する経
路も存在しないので,この
場合分けにモレダブりは
無い。
a,b,cの3種類の
例えば, αを2個, b
を求めるのに,次の
た順列を考える。
aabbc は○○IC
すると, abbbc は C
bbbbc は
7個の場所から〇
したがって, C5
a, b, c,d,ea
同様に考えれば