A005220 Number of Dyck paths of knight moves. (Formerly M2256)

1, 0, 1, 0, 3, 2, 12, 14, 54, 86, 274, 528, 1515, 3266, 8854, 20422, 53786, 129368, 336103, 830148, 2145020, 5390580, 13913325, 35378586, 91415954, 234397542, 606983495, 1566013450, 4065765499, 10540066710, 27437831060, 71404804002

Offset

0,5

Comments

A Dyck path of knight moves of size n is a path in ZxZ which:

(1) is made only of steps NNE, NEE, SSE and SEE;

(2) starts at (0,0) and ends at (n,0);

(3) never goes strictly below the x-axis. - Gheorghe Coserea, Jan 16 2017

References

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

Links

T. D. Noe, Table of n, a(n) for n = 0..200

Jean-Luc Baril and José L. Ramírez, Knight's paths towards Catalan numbers, Univ. Bourgogne Franche-Comté (2022).

J. Labelle and Y.-N. Yeh, Dyck paths of knight moves, Discrete Applied Math., 24 (1989), 213-221.

Formula

G.f.: (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) ~ (2+sqrt(3))*(sqrt(3*(7*sqrt(3)-3)/46)-sqrt((9-5*sqrt(3))/2)) * (1+sqrt(3))^n/(2*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 13 2013

a(n) = Sum_{m=0..n}((Sum_{j=ceiling(m/2)..m}(binomial(j,m-j)*binomial(m+1,j)))* Sum_{k=0..n-m}((binomial(m+2*k,k)*Sum_{l=0..k}(binomial(k,l)*binomial(k-l,n-m-3*l-k)*(-1)^(n-l-k)))/(m+k+1))). - Vladimir Kruchinin, Mar 05 2016

0 = x^4*y^4 - x^2*(2*x+1)*y^3 + x*(x^3+2*x+2)*y^2 - (2*x+1)*y + 1, where y is the g.f. - Gheorghe Coserea, Jan 16 2017

Mathematica

gf = (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); CoefficientList[gf + O[z]^32, z] (* Jean-François Alcover, Jul 16 2015 *)

Prog

(Maxima)
a(n):=sum((sum(binomial(j, m-j)*binomial(m+1, j), j, ceiling(m/2), m))*sum((binomial(m+2*k, k)*sum(binomial(k, l)*binomial(k-l, n-m-3*l-k)*(-1)^(n-l-k), l, 0, k))/(m+k+1), k, 0, n-m), m, 0, n); /*  Vladimir Kruchinin, Mar 05 2016 */
(PARI)
x='x; y='y;
Fxy = x^4*y^4 - x^2*(2*x+1)*y^3 + x*(x^3+2*x+2)*y^2 - (2*x+1)*y + 1;
seq(N) = {
  my(y0 = 1 + O('x^N), y1=0, dFxy=deriv(Fxy, 'y));
  for (k = 1, N,
    y1 = y0 - subst(Fxy, 'y, y0)/subst(dFxy, 'y, y0);
    if (y1 == y0, break()); y0 = y1);
  Vec(y0);
};
seq(32) \\ Gheorghe Coserea, Jan 16 2017

Crossrefs

Cf. A285174.

Sequence in context: A258206 A258019 A057779 * A243660 A220883 A253246

Adjacent sequences: A005217 A005218 A005219 * A005221 A005222 A005223

Keyword

nonn,easy,nice,walk

Author

N. J. A. Sloane

Extensions

More terms from Emeric Deutsch, Dec 17 2003

Status

approved