>>570
n×2の方眼紙内において
(0,0)を出発して(n,1), (n,0)に行き着く道順の総数をそれぞれb_n, c_nとおく
a_nのうち(n,0)→(n,1)の順路を含むものの数をa'_nとする
c_nのうち(n,2)→(n,1)の順路を含む物の数をc'_nとする
a_0 = a'_0 = b_0 = c_0 = 1, c'_0 = 0 となる
漸化式を図から考えて
a_n = a_(n-1) + b_(n-1) + c_(n-1) + a'_(n-1)
b_n = a_(n-1) + b_(n-1) + c_(n-1)
c_n = a_(n-1) + b_(n-1) + c_(n-1)  + c'_(n-1)
a'_n = c_(n-1) + a'_(n-1)
c'_n = a_(n-1) + c'_(n-1)

…もっときれいな解法あるんだろうな