A285174 a(n) is the number of Dyck paths of (2,3)-knight moves of size n.

1, 0, 0, 0, 1, 0, 1, 0, 2, 0, 7, 0, 7, 4, 38, 0, 52, 44, 192, 34, 445, 328, 1061, 658, 3431, 2266, 7293, 7632, 24322, 17946, 58812, 70006, 171467, 166364, 488958, 581520, 1290879, 1599416, 3972675, 4807640, 10523661, 14798098, 31868794, 41478042, 89608805, 131175180, 259840862, 371465030

Offset

0,9

Comments

A Dyck path of (s,r)-knight moves of size n is a path in ZxZ which:

(1) is made only of steps (s,-r),(s,r),(r,-s),(r,s);

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

(3) never goes strictly below the x-axis.

Links

Gheorghe Coserea, Table of n, a(n) for n = 0..400

Gheorghe Coserea, MiniZinc model for generating solutions

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

Formula

0 = x^16*y^8 - x^12*(2*x^3+1)*y^7 + x^11*(2*x^3+x+2)*y^6 - x^8*(2*x^5+2*x^3+x^2+1)*y^5 + x^4*(x^8+4*x^6+1)*y^4 - x^4*(2*x^5+2*x^3+x^2+1)*y^3 + x^3*(2*x^3 + x + 2)*y^2 - (2*x^3+1)*y + 1, where y(x) is the g.f. [Labelle and Yeh, 1989, Theorem 3.4]

From Vaclav Kotesovec, Apr 21 2017: (Start)

a(n) ~ sqrt((s*(-3 + (3 + 2*r + 6*r^3)*s - r*(2 + 3*r^2 + 7*r^3 + 9*r^5)*s^2 + 2*(r + 10*r^7 + 3*r^9)*s^3 - r^5*(4 + 5*r^2 + 11*r^3 + 13*r^5)*s^4 + r^8*(11 + 6*r + 14*r^3)*s^5 - 3*r^9*(2 + 5*r^3)*s^6 + 8*r^13*s^7)) / (r*(2 + r^3*(2 - 3*s) - 6*r^4*s - 6*r^6*s + 2*r^7*(12 - 5*s)*s^2 - 10*r^5*s^3 - 20*r^10*s^3 + 30*r^11*s^4 - 42*r^12*s^5 + 28*r^13*s^6 + 10*r^8*s^3*(-2 + 3*s) + r*(1 - 3*s + 6*s^2) + 3*r^9*s^2*(2 + 5*s^2 - 7*s^3)))) / (sqrt(2*Pi) * r^(n - 1/2) * n^(3/2)), where

r = 0.56519771738363939643752801324703081609848397675955382755548381... and

s = 1.35503954183039159917814688295718993182959905413029119006926443... are roots of the system of equations

1 + r^3*(2 + r + 2*r^3)*s^2 + r^4*(1 + 4*r^6 + r^8)*s^4 + r^11*(2 + r + 2*r^3)*s^6 + r^16*s^8 = (1 + 2*r^3)*s*(1 + r^4*s^2 + r^6*s^2 + r^8*s^4 + r^10*s^4 + r^12*s^6) and

2*r^3*s*(2 + r + 2*r^3 + 2*r*(1 + 4*r^6 + r^8)*s^2 + 3*r^8*(2 + r + 2*r^3)*s^4 + 4*r^13*s^6) = (1 + 2*r^3)*(1 + 3*r^4*s^2 + 3*r^6*s^2 + 5*r^8*s^4 + 5*r^10*s^4 + 7*r^12*s^6).

a(n+1)/a(n) tends to 1/r = 1.769292354238631415240409464335033492670553045898857...

(End)

Example

For n=10 the a(10)=7 solutions are:
3 2 5 4
3 4 5 2
3 5 2 4
3 5 4 2
5 3 2 4
5 3 4 2
5 4 3 2
where the steps are encoded as follows: 2 <-> (2,-3), 3 <-> (2,3), 4 <-> (3,-2), 5 <-> (3,2).

Prog

(PARI)
x='x; y = 'y;
Fxy = x^16*y^8 - x^12*(2*x^3+1)*y^7 + x^11*(2*x^3+x+2)*y^6 - x^8*(2*x^5+2*x^3+x^2+1)*y^5 + x^4*(x^8+4*x^6+1)*y^4 - x^4*(2*x^5+2*x^3+x^2+1)*y^3 + x^3*(2*x^3 + x + 2)*y^2 - (2*x^3+1)*y + 1;
seq(N) = {
  my(y0 = 1 + O('x^N), y1=0, n=1);
  while(n++,
    y1 = y0 - subst(Fxy, y, y0)/subst(deriv(Fxy, y), y, y0);
    if (y1 == y0, break()); y0 = y1); Vec(y0);
};
seq(48)

Crossrefs

Cf. A005220.

Sequence in context: A340197 A340140 A334341 * A269430 A363891 A142709

Adjacent sequences: A285171 A285172 A285173 * A285175 A285176 A285177

Keyword

nonn,walk

Author

Gheorghe Coserea, Apr 15 2017

Status

approved