A005220 - OEIS

%I M2256 #42 Jun 30 2022 19:41:39

%S 1,0,1,0,3,2,12,14,54,86,274,528,1515,3266,8854,20422,53786,129368,

%T 336103,830148,2145020,5390580,13913325,35378586,91415954,234397542,

%U 606983495,1566013450,4065765499,10540066710,27437831060,71404804002

%N Number of Dyck paths of knight moves.

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

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

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

%C (3) never goes strictly below the x-axis. - _Gheorghe Coserea_, Jan 16 2017

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

%H T. D. Noe, <a href="/A005220/b005220.txt">Table of n, a(n) for n = 0..200</a>

%H Jean-Luc Baril and José L. Ramírez, <a href="http://jl.baril.u-bourgogne.fr/knight.pdf">Knight's paths towards Catalan numbers</a>, Univ. Bourgogne Franche-Comté (2022).

%H J. Labelle and Y.-N. Yeh, <a href="http://dx.doi.org/10.1016/0166-218X(92)90286-J">Dyck paths of knight moves</a>, Discrete Applied Math., 24 (1989), 213-221.

%F 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].

%F 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

%F 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

%F 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

%t 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 *)

%o (Maxima)

%o 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 */

%o (PARI)

%o x='x; y='y;

%o 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;

%o seq(N) = {

%o   my(y0 = 1 + O('x^N), y1=0, dFxy=deriv(Fxy, 'y));

%o   for (k = 1, N,

%o     y1 = y0 - subst(Fxy, 'y, y0)/subst(dFxy, 'y, y0);

%o     if (y1 == y0, break()); y0 = y1);

%o   Vec(y0);

%o };

%o seq(32) \\ _Gheorghe Coserea_, Jan 16 2017

%Y Cf. A285174.

%K nonn,easy,nice,walk

%O 0,5

%A _N. J. A. Sloane_

%E More terms from _Emeric Deutsch_, Dec 17 2003