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,7

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.

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

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

Prog

(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

Crossrefs

Cf. A274110-A274115.

Sequence in context: A035954 A023192 A064480 * A209000 A115024 A167050

Adjacent sequences: A274108 A274109 A274110 * A274112 A274113 A274114

Keyword

nonn,walk

Author

N. J. A. Sloane, Jun 17 2016

Extensions

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

Status

approved