問題
図のような碁盤の目状の道路がある．地点を出発して，道路上を東または北に進んで地点に到達する経路を考える．(図1の太線はそのような経路の一例である．)
(1) 地点から地点に至る経路は何通りあるか．
(2) 地点から地点に至る経路のうち，図2の地点と地点をともに通る経路は何通りあるか．
(3) 図3のa，bの2か所が通行止めのとき，地点から地点に至る経路は何通りあるか．
% 図は省略% 図は省略% 図は省略
方針
基本は格子経路の数え上げである。全体では東6回・北4回の並べ替えを数える。(2)は図から 、、 の移動量を読み取り、積の法則で数える。(3)は通行止め 、 を通る経路を除く問題なので、包除原理を用いる。 と の両方を通る経路を最後に加え戻すことを忘れない。
解答
(1)
図より、 から へ到達するには、東へ6回、北へ4回進む必要がある。合計10回の移動のうち北へ進む4回を選べば経路が1つ定まるので 通りである。
(2)
図2より、 から までは東3回・北3回であるから 通りである。 から までは図の位置関係から1通りに決まる。また、 から までは東2回・北1回なので 通りである。したがって、、 をともに通る経路は 通りである。
(3)
まず、通行止めを考えない全経路は(1)より210通りである。
図3の通行止め を通る経路は、 の手前の端点までが東1回・北1回、その後 までが7回の移動のうち北3回であるから 通りである。
また、通行止め を通る経路は、図2の 、 をともに通る経路と同じ数え方になり 通りである。
ただし、 と の両方を通る経路は、 を通る経路としても を通る経路としても数えられているので、1回加え戻す必要がある。図3より、その数は
通りである。
したがって包除原理より、求める経路数は である。