A096608 Triangle read by rows: T(n,k)=number of Catalan knight paths in right half-plane from (0,0) to (n,k), for 0 <= k <= 2n, n >= 0. (See A096587 for the definition of a Catalan knight.)

1, 0, 0, 1, 2, 1, 0, 0, 1, 0, 2, 3, 2, 0, 0, 1, 8, 6, 1, 3, 4, 3, 0, 0, 1, 6, 12, 16, 12, 3, 4, 5, 4, 0, 0, 1, 44, 33, 18, 21, 27, 20, 6, 5, 6, 5, 0, 0, 1, 60, 76, 95, 72, 40, 34, 41, 30, 10, 6, 7, 6, 0, 0, 1, 256, 210, 154, 155, 177, 135, 75, 52, 58, 42, 15, 7, 8, 7, 0, 0, 1, 460, 520, 581, 480

Offset

0,5

Links

Paolo Xausa, Table of n, a(n) for n = 0..9999 (rows 0..99 of triangle, flattened)

Jean-Luc Baril, Nathanaël Hassler, Sergey Kirgizov, and José L. Ramírez, Grand zigzag knight's paths, arXiv:2402.04851 [math.CO], 2024.

Rémy Sigrist, Representation of the odd terms for n = 0..2^11

Formula

T(0, 0) = 1, T(0, 1) = 0, T(0, 2) = 0; T(1, 0) = 0, T(1, 1) = 0, T(1, 2) = 1.

For n >= 2, T(n, 0) = 2*T(n-2, 1) + 2*T(n-1, 2); T(n, 1) = T(n-2, 0) + T(n-2, 2) + T(n-1, 3) + T(n-1, 1); for 2 <= k <= 2n, T(n, k) = T(n-2, k-1) + T(n-2, k+1) + T(n-1, k-2) + T(n-1, k+2).

T(n, 0) + 2*Sum_{k = 1..2*n} T(n, k) = A002605(k). - Rémy Sigrist, Jun 29 2022

Example

Rows:
  1;
  0, 0, 1;
  2, 1, 0, 0, 1;
  0, 2, 3, 2, 0, 0, 1;
T(3,2) counts these paths:
  (0,0)-(1,-2)-(2,0)-(3,2);
  (0,0)-(1,2)-(2,0)-(3,2);
  (0,0)-(1,2)-(2,4)-(3,2).

Mathematica

A096608[rowmax_]:=Module[{T}, T[0, 0]=1; T[n_, k_]:=T[n, k]=If[k<=2n, T[n-1, Abs[k-2]]+T[n-2, Abs[k-1]]+T[n-1, k+2]+T[n-2, k+1], 0]; Table[T[n, k], {n, 0, rowmax}, {k, 0, 2n}]]; A096608[10] (* Generates 11 rows *) (* Paolo Xausa, May 09 2023 *)

Prog

(PARI) row(n) = { my (rr=0, r=1); for (k=1, n, [rr, r]=[r, r*(1+'X^4)+rr*('X^3+'X^5)]); Vec(r)[1+2*n..1+4*n] } \\ Rémy Sigrist, Jun 29 2022

Crossrefs

Cf. A096587, A096609, A096610, A096611, A096612, A355320.

Sequence in context: A101676 A056560 A345415 * A155102 A237621 A214625

Adjacent sequences: A096605 A096606 A096607 * A096609 A096610 A096611

Keyword

nonn,tabf

Author

Clark Kimberling, Jun 29 2004

Extensions

Offset changed to 0 by Rémy Sigrist, Jun 29 2022

Status

approved