A099331 Number of Catalan knight paths from (0,0) to (n,3) in the region between and on the lines y=0 and y=3. (See A096587 for the definition of Catalan knight.).
0, 0, 0, 2, 1, 4, 3, 12, 16, 40, 56, 122, 197, 408, 695, 1352, 2368, 4512, 8096, 15202, 27529, 51196, 93339, 172852, 316368, 584104, 1071160, 1974458, 3625613, 6677104, 12269359, 22583120, 41513728, 76387712, 140454656, 258398850, 475182353
Offset: 0
Keywords
Examples
a(6) counts 3 paths from (0,0) to (6,3); the final move in 1 path is from (4,2) and the final move in the other 2 paths is from (5,1).
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 > 6.
G.f.: x^3*(-x^2 + x - 2)/((-x^4 + 2*x^3 + 1)*(x^3 + x^2 + x - 1)). (End)