A099330 Number of Catalan knight paths from (0,0) to (n,2) in the region between and on the lines y=0 and y=3. (See A096587 for the definition of Catalan knight.).
0, 1, 0, 1, 1, 5, 6, 14, 18, 43, 70, 147, 243, 475, 828, 1596, 2852, 5365, 9676, 18037, 32853, 60929, 111394, 205770, 377142, 695519, 1276818, 2351975, 4320935, 7954167, 14620472, 26904824, 49467208, 91010153, 167357080, 307868201
Offset: 1
Keywords
Examples
a(6) counts 6 paths from (0,0) to (6,2); the final move in 1 path is from the point (4,3), the final move in 3 paths is from (4,1) and the final move in the other 2 paths is from (5,0).
Formula
Taking A099328 to A099331 as the rows of an array T, the recurrences for these row sequences are given for n>=2 by T(n, 0) = T(n-1, 2) + T(n-2, 1), T(n, 1) = T(n-1, 3) + T(n-2, 0) + T(n-2, 2), T(n, 2) = T(n-1, 0) + T(n-2, 1) + T(n-2, 3), T(n, 3) = T(n-1, 1) + T(n-2, 2), with initial values T(0, 0)=1, T(1, 2)=1.
From Chai Wah Wu, Aug 09 2016: (Start)
a(n) = a(n-1) + a(n-2) - a(n-3) + 3*a(n-4) + a(n-5) + a(n-6) - a(n-7) for n > 7.
G.f.: -x^2*(x^3 - x + 1)/((-x^4 + 2*x^3 + 1)*(x^3 + x^2 + x - 1)). (End)