問題概略
下のような道路があります。黒線が道路です。
A 地点から B 地点に以下のルールを守りながら移動することを考えます。
- 最短距離で進む
- 上方向(縦方向)に連続して進むことはできない
進む経路は何通りあるでしょうか。
解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。
矢印の順列
A から B までの最短経路は 7 個の→と 4 個の↑の順列です。↑は連続しません。
まずは 7 個の→を一列に並べて,次にその隙間と両端の計 8 ヵ所から 4 ヵ所を選んで↑を挿入します。
求める経路数は の「70 通り」です。