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

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

combination-road-1

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

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

combination-road-2

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

解き方

combination-road-3

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

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

combination-road-4

combination-road-5

右上に向かって足していくイメージ。各点について、その点の左と下にある数字を足しています。

ゴールにふられた数字は 3 です。よってこの問題の答え、すなわちルートの数は 3 通りとなります。