例題 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