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
Examples
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).
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
Programs
-
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 *)
-
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
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
Extensions
Offset changed to 0 by Rémy Sigrist, Jun 29 2022