A005220 -id:A005220 - cp's OEIS frontend

A096587 Triangle read by rows: T(n,k)=number of Catalan knight paths in Quadrant I from (0,0) to (n,k), for 0 <= k <= 2*n, n >= 0. A Catalan knight moves (1 right and 2 up) or (1 right and 2 down) or (2 right and 1 up) or (2 right and 1 down).

1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 2, 2, 0, 0, 1, 3, 3, 1, 2, 3, 3, 0, 0, 1, 2, 4, 9, 8, 3, 3, 4, 4, 0, 0, 1, 12, 12, 10, 11, 18, 15, 6, 4, 5, 5, 0, 0, 1, 14, 22, 42, 39, 27, 22, 30, 24, 10, 5, 6, 6, 0, 0, 1, 54, 61, 64, 72, 98, 87, 56, 38, 45, 35, 15, 6, 7, 7, 0, 0, 1, 86, 128, 213, 217, 181, 167

Offset: 0

Clark Kimberling, Jun 28 2004

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

Paolo Xausa, Table of n, a(n) for n = 0..9999 (rows 0..99 of triangle, flattened)
Jean-Luc Baril and José L. Ramírez, Knight's paths towards Catalan numbers, Univ. Bourgogne Franche-Comté (2022).

Cf. A005220 (column 0), A005221 (column 1), A096588, A096608.

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

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

Offset changed to 0 by Paolo Xausa, May 22 2023

A005221 Number of Dyck paths of knight moves.

Original entry on oeis.org

0, 0, 1, 1, 3, 4, 12, 22, 61, 128, 335, 756, 1936, 4580, 11652, 28402, 72209, 179460, 457274, 1151725, 2945129, 7489680, 19228598, 49256157, 126958030, 327072560, 846173899, 2190012371, 5685200054, 14770728584, 38463268482, 100259225816

Offset: 0

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Jean-Luc Baril and José L. Ramírez, Knight's paths towards Catalan numbers, Univ. Bourgogne Franche-Comté (2022).
Vaclav Kotesovec, Recurrence (of order 11)
J. Labelle and Y.-N. Yeh, Dyck paths of knight moves, Discrete Applied Math., 24 (1989), 213-221.

a = (2*z + Sqrt[-4*z^4 + 4*z^2 - 4*z + 1] - Sqrt[2]*Sqrt[-2*z^4 - 4*z^2 + (2*z + 1)*Sqrt[-4*z^4 + 4*z^2 - 4*z + 1] + 1] + 1)/(4*z^2); gf = z^2*a^2/(1 - z*a); CoefficientList[Series[gf, {z, 0, 31}], z] (* Jean-François Alcover, Dec 21 2012, from g.f. *)

a(n):=sum(m*sum((sum(binomial(i+m,j)*binomial(j,i-j),j,0,i+m))*sum((binomial(2*k+i+m-1,k)*sum(binomial(k,l)*binomial(k-l,n-3*l-k-i-m)*(-1)^(n-l-k-m),l,0,k))/(k+i+m),k,0,n-i-m),i,0,n-m),m,2,n); /* Vladimir Kruchinin, Mar 06 2016 */

G.f.: z^2*A^2/(1-z*A), where A = (1+2*z+sqrt(1-4*z+4*z^2-4*z^4) -sqrt(2)*sqrt(1-4*z^2-2*z^4+(2*z+1)*sqrt(1-4*z+4*z^2-4*z^4)))/(4*z^2).
a(n) ~ c * (1+sqrt(3))^n / n^(3/2), where c = 4/sqrt(Pi*(27 + 17*sqrt(3) - sqrt(2*(730 + 929*sqrt(3))/3))) = 0.5480566813380593118... - Vaclav Kotesovec, Feb 29 2016
a(n) = Sum_{m=2..n} (m*Sum_{i=0..n-m }((Sum_{j=0..i+m }(binomial(i+m,j)*binomial(j,i-j)))*Sum_{k=0..n-i-m }((binomial(2*k+i+m-1,k)*Sum_{l=0..k}(binomial(k,l)*binomial(k-l,n-3*l-k-i-m)*(-1)^(n-l-k-m)))/(k+i+m)))). - Vladimir Kruchinin, Mar 06 2016
A(x) = x^2*A005220(x)^2/(1-x*A005220(x)). - Gheorghe Coserea, Jan 16 2017

More terms from Emeric Deutsch, Dec 17 2003

A285174 a(n) is the number of Dyck paths of (2,3)-knight moves of size n.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 1, 0, 2, 0, 7, 0, 7, 4, 38, 0, 52, 44, 192, 34, 445, 328, 1061, 658, 3431, 2266, 7293, 7632, 24322, 17946, 58812, 70006, 171467, 166364, 488958, 581520, 1290879, 1599416, 3972675, 4807640, 10523661, 14798098, 31868794, 41478042, 89608805, 131175180, 259840862, 371465030

Offset: 0

Gheorghe Coserea, Apr 15 2017

A Dyck path of (s,r)-knight moves of size n is a path in ZxZ which:
(1) is made only of steps (s,-r),(s,r),(r,-s),(r,s);
(2) starts at (0,0) and ends at (n,0);
(3) never goes strictly below the x-axis.

			For n=10 the a(10)=7 solutions are:
3 2 5 4
3 4 5 2
3 5 2 4
3 5 4 2
5 3 2 4
5 3 4 2
5 4 3 2
where the steps are encoded as follows: 2 <-> (2,-3), 3 <-> (2,3), 4 <-> (3,-2), 5 <-> (3,2).

Gheorghe Coserea, Table of n, a(n) for n = 0..400
Gheorghe Coserea, MiniZinc model for generating solutions
J. Labelle and Y.-N. Yeh, Dyck paths of knight moves, Discrete Applied Math., 24 (1989), 213-221.

Cf. A005220.

x='x; y = 'y;
Fxy = x^16*y^8 - x^12*(2*x^3+1)*y^7 + x^11*(2*x^3+x+2)*y^6 - x^8*(2*x^5+2*x^3+x^2+1)*y^5 + x^4*(x^8+4*x^6+1)*y^4 - x^4*(2*x^5+2*x^3+x^2+1)*y^3 + x^3*(2*x^3 + x + 2)*y^2 - (2*x^3+1)*y + 1;
seq(N) = {
  my(y0 = 1 + O('x^N), y1=0, n=1);
  while(n++,
    y1 = y0 - subst(Fxy, y, y0)/subst(deriv(Fxy, y), y, y0);
    if (y1 == y0, break()); y0 = y1); Vec(y0);
};
seq(48)

0 = x^16*y^8 - x^12*(2*x^3+1)*y^7 + x^11*(2*x^3+x+2)*y^6 - x^8*(2*x^5+2*x^3+x^2+1)*y^5 + x^4*(x^8+4*x^6+1)*y^4 - x^4*(2*x^5+2*x^3+x^2+1)*y^3 + x^3*(2*x^3 + x + 2)*y^2 - (2*x^3+1)*y + 1, where y(x) is the g.f. [Labelle and Yeh, 1989, Theorem 3.4]
From Vaclav Kotesovec, Apr 21 2017: (Start)
a(n) ~ sqrt((s*(-3 + (3 + 2*r + 6*r^3)*s - r*(2 + 3*r^2 + 7*r^3 + 9*r^5)*s^2 + 2*(r + 10*r^7 + 3*r^9)*s^3 - r^5*(4 + 5*r^2 + 11*r^3 + 13*r^5)*s^4 + r^8*(11 + 6*r + 14*r^3)*s^5 - 3*r^9*(2 + 5*r^3)*s^6 + 8*r^13*s^7)) / (r*(2 + r^3*(2 - 3*s) - 6*r^4*s - 6*r^6*s + 2*r^7*(12 - 5*s)*s^2 - 10*r^5*s^3 - 20*r^10*s^3 + 30*r^11*s^4 - 42*r^12*s^5 + 28*r^13*s^6 + 10*r^8*s^3*(-2 + 3*s) + r*(1 - 3*s + 6*s^2) + 3*r^9*s^2*(2 + 5*s^2 - 7*s^3)))) / (sqrt(2*Pi) * r^(n - 1/2) * n^(3/2)), where
r = 0.56519771738363939643752801324703081609848397675955382755548381... and
s = 1.35503954183039159917814688295718993182959905413029119006926443... are roots of the system of equations
1 + r^3*(2 + r + 2*r^3)*s^2 + r^4*(1 + 4*r^6 + r^8)*s^4 + r^11*(2 + r + 2*r^3)*s^6 + r^16*s^8 = (1 + 2*r^3)*s*(1 + r^4*s^2 + r^6*s^2 + r^8*s^4 + r^10*s^4 + r^12*s^6) and
2*r^3*s*(2 + r + 2*r^3 + 2*r*(1 + 4*r^6 + r^8)*s^2 + 3*r^8*(2 + r + 2*r^3)*s^4 + 4*r^13*s^6) = (1 + 2*r^3)*(1 + 3*r^4*s^2 + 3*r^6*s^2 + 5*r^8*s^4 + 5*r^10*s^4 + 7*r^12*s^6).
a(n+1)/a(n) tends to 1/r = 1.769292354238631415240409464335033492670553045898857...
(End)

A005222 Number of Dyck paths of knight moves.

Original entry on oeis.org

1, 0, 1, 0, 4, 4, 18, 26, 86, 158, 462, 976, 2665, 6082, 16040, 38338, 99536, 244880, 631923, 1583796, 4081939, 10358670, 26728731, 68425494, 176964795, 455967376, 1182454137, 3061954102, 7962768190, 20702327552, 53983118006, 140817757006

Offset: 0

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
Vaclav Kotesovec, Recurrence (of order 11)
J. Labelle and Y.-N. Yeh, Dyck paths of knight moves, Discrete Applied Math., 24 (1989), 213-221.

A[x_] = (s*(r-1+x-x^3) + x*(1+x)*(3+r*(x-1) + x*(6*x-5)))/(4*x^3) /. s -> Sqrt[2]*Sqrt[1+r-2*x*(2*x+x^3-r)] /. r -> Sqrt[1-4*x*(1-x+x^3)];
A[x] + O[x]^32 // CoefficientList[#, x]& (* Jean-François Alcover, Mar 26 2017, after Gheorghe Coserea *)

G.f.: A+z^4A^3/(1-zA)^2, where A=(1+2z+sqrt(1-4z+4z^2-4z^4)-sqrt(2)*sqrt(1-4z^2-2z^4+(2z+1)sqrt(1-4z+4z^2-4z^4)))/[4z^2].
a(n) ~ c * (1+sqrt(3))^n / n^(3/2), where c = sqrt(341*sqrt(3) - 225 + 3*sqrt(46*(197*sqrt(3) - 22))) / (4*sqrt(23*Pi)) = 0.794168381329... - Vaclav Kotesovec, Feb 29 2016
A(x) = x^2*A005220(x)*A005221(x) + x*A005221(x)^2 + A005220(x). - Gheorghe Coserea, Jan 16 2017

More terms from Emeric Deutsch, Dec 17 2003

A005223 Number of Dyck paths of knight moves.

Original entry on oeis.org

0, 0, 1, 0, 2, 2, 7, 10, 29, 52, 142, 294, 772, 1732, 4451, 10482, 26715, 64908, 165194, 409720, 1044629, 2627712, 6721492, 17079076, 43853111, 112273270, 289390434, 745262022, 1928015211, 4988699442, 12949776427, 33638741110, 87590340673

Offset: 0

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Harvey P. Dale, Table of n, a(n) for n = 0..1000
J. Labelle and Y.-N. Yeh, Dyck paths of knight moves, Discrete Applied Math., 24 (1989), 213-221.

CoefficientList[Series[1-1/(((1+2z+Sqrt[1-4z+4z^2-4z^4])-Sqrt[2] Sqrt[ 1-4z^2-2z^4+(2z+1)Sqrt[1-4z+4z^2-4z^4]])/(4z^2)),{z,0,40}],z] (* Harvey P. Dale, Oct 11 2011 *)

G.f.=1-1/A, where A=(1+2z+sqrt(1-4z+4z^2-4z^4)-sqrt(2)*sqrt(1-4z^2-2z^4+(2z+1)sqrt(1-4z+4z^2-4z^4)))/[4z^2].
a(n) ~ (23*sqrt(2*(9-5*sqrt(3))) + sqrt(138*(7*sqrt(3)-3))) * (1+sqrt(3))^n / (184*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 10 2014
A(x) = 1 - 1/A005220(x). - Gheorghe Coserea, Jan 16 2017

More terms from Emeric Deutsch, Dec 17 2003

A368375 Arises from enumeration of a certain class of partial knight's paths on the square grid.

Original entry on oeis.org

0, 1, 0, 2, 1, 9, 10, 42, 64, 213, 400, 1180, 2510, 6918, 15842, 42134, 100966, 263894, 650688, 1687746, 4238855, 10968196, 27888906, 72187356, 185141385, 480025465, 1238940890, 3219591600, 8350054339, 21752631006, 56634075418, 147899071110, 386293111740

Offset: 0

N. J. A. Sloane, Feb 17 2024

nonn

It would be nice to have a more precise definition.

Jean-Luc Baril and José L. Ramírez, Knight's paths towards Catalan numbers, Univ. Bourgogne Franche-Comté (2022). Also arXiv:2206.12087 [math.CO], Jan 2023. See Section 2.1.

Cf. A005220, A005221.

aa = (1 + 2z + Sqrt[1 - 4z + 4z^2 - 4z^4] - Sqrt[2]*Sqrt[1 - 4z^2 - 2z^4 + (2z + 1)*Sqrt[1 - 4z + 4z^2 - 4z^4]])/(4z^2);
a1 = z^2 aa^2 / (1 - z aa);
gf = (z (u z + 1) aa + u z a1 - u^2) / (u^4 z + u^3 z^2 + u z^2 - u^2 + z);
Table[SeriesCoefficient[gf,{u,0,2},{z,0,n}], {n,0,30}] (* Andrei Zabolotskii, Jul 25 2025 *)

G.f.: (1 - (1+x) * A(x) + (x+x^4) * A(x)^2) / (x * (x * A(x) - 1)), where A(x) is the g.f. of A005220. - Andrei Zabolotskii, Jul 25 2025

Terms a(10) and beyond from Andrei Zabolotskii, Jul 25 2025

cp's OEIS Frontend

A096587 Triangle read by rows: T(n,k)=number of Catalan knight paths in Quadrant I from (0,0) to (n,k), for 0 <= k <= 2*n, n >= 0. A Catalan knight moves (1 right and 2 up) or (1 right and 2 down) or (2 right and 1 up) or (2 right and 1 down).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A005221 Number of Dyck paths of knight moves.

Views

Author

Keywords

References

Links

Programs

Mathematica

Maxima

Formula

Extensions

A285174 a(n) is the number of Dyck paths of (2,3)-knight moves of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A005222 Number of Dyck paths of knight moves.

Views

Author

Keywords

References

Links

Programs

Mathematica

Formula

Extensions

A005223 Number of Dyck paths of knight moves.

Views

Author

Keywords

References

Links

Programs

Mathematica

Formula

Extensions

A368375 Arises from enumeration of a certain class of partial knight's paths on the square grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions