問題
図のような碁盤の目状の道路がある．地点を出発して，道路上を東または北に進んで地点に到達する経路を考える．（図1の太線はそのような経路の一例である．）
(1) 地点から地点に至る経路は何通りあるか．
(2) 地点から地点に至る経路のうち，図2の地点と地点をともに通る経路は何通りあるか．
(3) 図3のの部分が通行止めのとき，地点から地点に至る経路は何通りあるか．
% 図は省略% 図は省略% 図は省略
方針
東へ進む回数と北へ進む回数を固定し、進む順序を選ぶ組合せとして数える。(1)は全体で東6回・北4回の並べ替えである。(2)は図から 、、 の移動量を読み取り、区間ごとの経路数を掛ける。(3)は全経路から通行止め を通る経路を引く。通行止めを通る場合は、その道の直前の端点まで、通行止めの1歩、そこから までに分けて数える。
解答
(1)
図より、 から へ行くには、東へ6回、北へ4回進めばよい。合計10回の移動のうち、北へ進む4回の位置を選べば経路が1つ決まるので、経路数は である。
(2)
図2より、 から までは東3回・北3回である。したがって である。また、 から までは図の指定された位置関係により1通りに決まる。さらに、 から までは東2回・北1回なので である。よって、、 をともに通る経路数は である。
(3)
通行止めがない場合は(1)より210通りである。図3の通行止め の道を通る経路を数えて、それを全体から除けばよい。
図3より、 の手前の端点までは東1回・北1回で到達するので 通りである。通行止め の道そのものは1通りであり、その後、 までは残り7回の移動のうち北へ3回進む形になるので 通りである。したがって、 を通る経路は 通りである。
求める経路数は、全経路からこれを除いて である。