A005221 Number of Dyck paths of knight moves.

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• walk

References

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

Links

• 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.

Programs

Mathematica

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. *)

Maxima

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

Formula

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

Extensions

More terms from Emeric Deutsch, Dec 17 2003