cp's OEIS Frontend

A005220 Number of Dyck paths of knight moves.

%I A005220 M2256 #42 Jun 30 2022 19:41:39
%S A005220 1,0,1,0,3,2,12,14,54,86,274,528,1515,3266,8854,20422,53786,129368,
%T A005220 336103,830148,2145020,5390580,13913325,35378586,91415954,234397542,
%U A005220 606983495,1566013450,4065765499,10540066710,27437831060,71404804002
%N A005220 Number of Dyck paths of knight moves.
%C A005220 A Dyck path of knight moves of size n is a path in ZxZ which:
%C A005220 (1) is made only of steps NNE, NEE, SSE and SEE;
%C A005220 (2) starts at (0,0) and ends at (n,0);
%C A005220 (3) never goes strictly below the x-axis. - _Gheorghe Coserea_, Jan 16 2017
%D A005220 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005220 T. D. Noe, <a href="/A005220/b005220.txt">Table of n, a(n) for n = 0..200</a>
%H A005220 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 A005220 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 A005220 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 A005220 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 A005220 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 A005220 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 A005220 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 A005220 (Maxima)
%o A005220 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 A005220 (PARI)
%o A005220 x='x; y='y;
%o A005220 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 A005220 seq(N) = {
%o A005220   my(y0 = 1 + O('x^N), y1=0, dFxy=deriv(Fxy, 'y));
%o A005220   for (k = 1, N,
%o A005220     y1 = y0 - subst(Fxy, 'y, y0)/subst(dFxy, 'y, y0);
%o A005220     if (y1 == y0, break()); y0 = y1);
%o A005220   Vec(y0);
%o A005220 };
%o A005220 seq(32) \\ _Gheorghe Coserea_, Jan 16 2017
%Y A005220 Cf. A285174.
%K A005220 nonn,easy,nice,walk
%O A005220 0,5
%A A005220 _N. J. A. Sloane_
%E A005220 More terms from _Emeric Deutsch_, Dec 17 2003