A005220 Number of Dyck paths of knight moves.
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
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.
Crossrefs
Cf. A285174.
Programs
-
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 *)
-
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
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
Extensions
More terms from Emeric Deutsch, Dec 17 2003
Comments