格子状の通路を左下から右上まで最短で行く方法の問題はよく出題される。そこで、これ
に、
各交差点において直進と左折は許されるがハンドルの不具合で右折が出来ない
の条件下で、出発点(左下)から到着点(右上)まで行ける方法(最短とは限らない)が何通り
あるかを考える。
ただし、同じ交差点は通過できるが、同じ直線路は二度と通過できないものとする。
例えば、下図の東西3、南北3本通路(2×2ブロック)なら、2通りとなる。
(→→↑↑, または →↑↑←↓→→↑)
では、2×3ブロック、3×3ブロック、4×4ブロックの道路ではそれぞれ何通り?
(コメント) 2×3ブロックでは、次の4通り。
→→→↑↑、→→↑↑←↓→→↑、→→↑↑←←↓→→→↑、→↑↑←↓→→→↑
同様にして、3×3ブロックでは、次の11通りかな?
→→→↑↑↑、→→↑↑↑←↓→→↑、→→↑↑↑←↓↓→→↑↑、
→→↑↑↑←←↓→→→↑、→→↑↑↑←←↓↓→→→↑↑、→→↑↑←↓→→↑↑、
→→↑↑←←↓→→→↑↑、→↑↑↑←↓→→→↑、→↑↑↑←↓↓→→→↑↑、
→↑↑←↓→→→↑↑、→↑↑←↓→→↑↑←↓→→↑
公式で求める方法はないのかな?