問題
右の図のように，道路が碁盤の目のようになった街がある．地点から地点までの長さが最短の道を行くとき，次の場合は何通りの道順があるか．
% 図は省略
(1) 地点を通る．
(2) 地点は通らない．
(3) 地点および地点は通らない．
方針
図から格子を座標化する。、、 であり、点 は横道路の途中、すなわち から への1歩の上にある。同様に は から への1歩の上にある。最短経路は右5回、上6回なので、通過条件は必要な部分経路の積、通らない条件は余事象と包除で数える。
解答
図より、 を 、 を とみなす。最短経路では、右へ5回、上へ6回進むだけであるから、全体の道順は 通りである。
(1)
図より である。 から までは右へ1回、上へ2回なので 通りである。 から までは右へ4回、上へ4回なので 通りである。したがって、 を通る道順は 通りである。
(2)
点 は交差点ではなく、横道路の途中にある。図から、 を通るためには、 から へ右に進む1歩を通らなければならない。 から までは右へ2回、上へ3回なので 通りである。その後、 から への1歩は固定される。さらに から までは右へ2回、上へ3回なので 通りである。したがって、 を通る道順は 通りである。よって を通らない道順は 通りである。
(3)
同様に、 を通るためには、 から へ右に進む1歩を通る必要がある。 から までは右へ3回、上へ4回なので 通りである。その後の1歩は固定され、 から までは右へ1回、上へ2回なので 通りである。したがって を通る道順は 通りである。
次に、 と の両方を通る道順を数える。 から までは10通り、 を通る1歩は固定、 から までは上へ1歩だけ、 を通る1歩も固定、 から までは3通りである。よって両方を通る道順は 通りである。
包除原理より、 も も通らない道順は 通りである。