A274111 Number of equivalence classes of ballot paths of length n for the string ddd.

1, 1, 1, 1, 1, 1, 2, 3, 5, 7, 10, 13, 20, 28, 45, 65, 101, 143, 222, 317, 500, 726, 1143, 1661, 2608, 3796, 5983, 8764, 13835, 20335, 32089, 47251, 74637, 110227, 174302, 258095, 408276, 605664, 958551, 1424659, 2256136, 3359446, 5322449, 7937666, 12580545

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

Crossrefs

Cf. A274110-A274115.

Programs

Mathematica

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

PARI

x='x; y='y;
Fxy = x^2*(1-2*x+x^2-x^4)*y^3 + 2*x*(1-x)^2*y^2 + (1-3*x+x^2)*y - 1;
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(45)  \\ Gheorghe Coserea, Jan 05 2017

Formula

The g.f. satisfies x^2*(1-2*x+x^2-x^4)*A(x)^3 + 2*x*(1-x)^2*A(x)^2 + (1-3*x+x^2)*A(x) - 1 = 0. - R. J. Mathar, Jun 20 2016

Extensions

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