>>367
進む方向は「下もしくは斜め下」だから、左下、下、右下の3通りでしょ

3×5の例なら、パスカルの三角形のように

1 1 1 1 1
2 3 3 3 2
5 8 9 8 5

と1段ごとに状態数を（左上＋上＋右上）で求め、最下段を集計すればおｋ

一般的なmとnに対しては、n次正方行列

┌ 1, 1, 0, 0, ..., 0 ┐
│ 1, 1, 1, 0, ..., 0 │
│ 0, 1, 1, 1, ..., 0 │
│　 　・・・ 　 　 　│＝A ※対角線とその隣の要素が1、他はすべて0
│ 0, ..., 1, 1, 1, 0 │
│ 0, ..., 0, 1, 1, 1 │
└ 0, ..., 0, 0, 1, 1 ┘

に対して A^m を計算し、各要素の和を求める
計算は得意な人に任せた