例題 179 最短経路の問題(1)
****
からB地点に最短経路で行くとき,次のような道
順は全部で何通りあるかのよ
右の図のような格子状の道路網がある. A地点 B
E
D
C
(1) A地点からB地点へ行く場合
(2)途中でC,D 両地点を通る場合
A
考え方 (i) 右へ 1区画進むことを→, 上へ1区画進むことを
と表すと, 右の図のような道順は,
→-
表される. どの道順を通っても、上のように, 6個
と4個の↑で表される.つまり, 6個のと4個
↑を1列に並べる順列と考える
A
(11↑→→→→→ ] 1~10の番号から○をつける4つを選び,
1②③④5 6 7 8 9 10 そこに↑を入れると考える.
【解答 1 右へ1区画進むことを→, 上へ1区画進むことを↑と表
ごすと, A地点からB地点へは右へ6区画, 上へ4区画進め
ばよい.つまり,6個のと4個の↑の順列である。
80
(1)
10!
6!4!
-=210(通り)
1
(2) A地点からC地点までの道順は,
2個のと1個の↑の順列だから,
3!
同じものを含む順列
下の図のように,A
からCまで,Cから
-=3(通り)
2!1!
2個のと1個のの順列だから.
D地点からB地点までの道順は,
C地点からD地点までの道順は,
3!
2!1!=3(通り)
D まで, DからBま
での道順で考える。
ID
[CL
よって,
2個のと2個の↑の順列だから、
3×3×6=54 (通り)
4!
-=6(通り)
A°
2!2!
積の法則
解答2 (1) 104=210 (通り)
A
(2) 3C1 ×3C1×4C2=3×3×6=54 (通り)
8888
AからCCから
A
DからBで分けて考
a2-
Focus
るときの
最短経路は,同じものを含む順列で考える
SA
練習
例題179の図において, A地点からB地点に最短経路で行くとき、次のような
179 道順は全部で何通りあるか.
**
(1) D地点を通る場合 (2) E地点を通る場合
E