68 最短経 図のような市街路をA地点からB地点まで,最短 経路で行く方法は何通りあるか, 以下の各場合につ いて答えよ. ただし, 斜線部分は池があって通行で きないものとする。 (1) C地点を通って行く場合. (2) C地点を通らないで行く場合. ( 北海学園大) A C B

合計5か所のうちの3か所を決めると考えて 156 第5章 順列と組合せ なお, 12個, 3個を並べる方法は 合計5か所のうち↑の2か所を決めると考えて 5C2通りとしても求まりますし、 1番目2番目、3番目、4番 合せの数 日,5番目から2つを選ぶ 5C 通りとしても求まります. 「ところで、通行できない部分があるときは,次 のように考えるのが有効です. 右図で, AからBまで最短の経路で行くときに Pip ついて考えてみましょう. PP' QHQ R R このとき 「Aを含む領域とBを含む領域に分ける」 のです.しかも, 通行できない道 (図の青い道) と交差するように境界線(点線)を引きます. た とえば,右図のように境界線を引くと, AからB まで行くには PP', QQ', RR', SS', TT' のいずれかで境界線をまたぐことになります。 (1)では, CからBまでの経路について境界線を 用意します. A > C SS' TT