A274111 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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