道の経路の場合の数を求める問題

道がマス目のようになっているときに、スタートからゴールまでの最短経路の場合の数（行き方）を求めてみます。まずは縦1マス、横2マスの長方形の道から。

まずはなんとなくルートを想像する

なんとなく見た目で次のルートが想像できるでしょうか？

答えは3通りです。最初に上にいくパターンと、2回目に上にいくパターンと、最後に上にいくパターンの3通り。

解き方

まずは上のように左と下の辺に沿って1という数字を各点にうちます。ここでは点が3個あるので3個うちました。赤い数字に注目。

次に各点の数字を順番に足していきます。

右上に向かって足していくイメージ。各点について、その点の左と下にある数字を足しています。ゴールにふられた数字は3です。よって経路の数は3通りとなります。