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,4

Links

Table of n, a(n) for n=0..36.

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)

Example

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).

Crossrefs

Cf. A099328, A099329, A099330.

Sequence in context: A032662 A185413 A138509 * A260319 A146001 A091879

Adjacent sequences: A099328 A099329 A099330 * A099332 A099333 A099334

Keyword

nonn

Author

Clark Kimberling, Oct 12 2004

Status

approved