【例題】 右図において, 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 同様に考えれば