A099329 Number of Catalan knight paths from (0,0) to (n,1) in the region between and on the lines y=0 and y=3. (See A096587 for the definition of Catalan knight.).

0, 0, 1, 1, 3, 2, 7, 10, 26, 38, 79, 127, 261, 452, 877, 1540, 2916, 5244, 9837, 17853, 33159, 60486, 111923, 204974, 378334, 694018, 1278939, 2348795, 4325129, 7948424, 14628953, 26893256, 49482888, 90987448, 167388697, 307825273

Offset

1,5

Links

Table of n, a(n) for n=1..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 > 7.

G.f.: x^3*(x^3 - x^2 - 1)/((-x^4 + 2*x^3 + 1)*(x^3 + x^2 + x - 1)). (End)

Example

a(6) counts 7 paths from (0,0) to (6,1); the final move in 4 of the paths is from the point (5,3), the final move in 1 path is from (4,2) and the final move in the other 3 paths is from (4,0).

Crossrefs

Cf. A099328, A099330, A099331.

Sequence in context: A034423 A193859 A174330 * A182871 A143329 A365227

Adjacent sequences: A099326 A099327 A099328 * A099330 A099331 A099332

Keyword

nonn

Author

Clark Kimberling, Oct 12 2004

Status

approved