A274113 Number of equivalence classes of ballot paths of length n for the string dud.

1, 1, 1, 1, 2, 3, 5, 7, 11, 16, 26, 39, 63, 95, 154, 235, 381, 585, 948, 1464, 2373, 3682, 5967, 9293, 15060, 23531, 38131, 59741, 96801, 152020, 246310, 387611, 627985, 990027, 1603893, 2532609, 4102726, 6487600, 10509114, 16639214, 26952186, 42722941, 69199472

Offset: 0

Author

N. J. A. Sloane, Jun 17 2016

Keywords

• nonn
• walk

Links

• Gheorghe Coserea, Table of n, a(n) for n = 0..300
• K. Manes, A. Sapounakis, I. Tasoulas, P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015, proposition 3.6.

Crossrefs

Cf. A274110, A274111, A274112, A274114, A274115.

Programs

Mathematica

terms = 43; y[] = 0; Do[y[x] = (-1+x^2-x^4+(2x-3x^2-2x^3+2x^4+2x^5-2x^6) y[x]^2 + (x^2-x^3-x^4) y[x]^3)/(-1+3x+x^2-3x^3-x^4+ x^5) + O[x]^terms, terms]; CoefficientList[y[x], x] (* Jean-François Alcover, Oct 07 2018 *)

PARI

x='x; y='y;
Fxy = x^2*(1-x-x^2)*y^3 + 2*x*(1-3/2*x-x^2+x^3+x^4-x^5)*y^2 + (1-3*x-x^2+3*x^3+x^4-3*x^5)*y - 1+x^2-x^4;
seq(N) = {
  my(y0 = 1 + O('x^N), y1=0);
  for (k = 1, N,
    y1 = y0 - subst(Fxy, y, y0)/subst(deriv(Fxy, y), y, y0);
    if (y1 == y0, break()); y0 = y1);
  Vec(y0);
};
seq(43)  \\ Gheorghe Coserea, Jan 05 2017

Formula

G.f. y satisfies: 0 = x^2*(1-x-x^2)*y^3 + 2*x*(1-3/2*x-x^2+x^3+x^4-x^5)*y^2 + (1-3*x-x^2+3*x^3+x^4-3*x^5)*y - 1+x^2-x^4. - Gheorghe Coserea, Jan 05 2017

Extensions

a(0)=1 prepended by Gheorghe Coserea, Jan 05 2017