A274111 - OEIS

%I #27 Oct 07 2018 03:17:14

%S 1,1,1,1,1,1,2,3,5,7,10,13,20,28,45,65,101,143,222,317,500,726,1143,

%T 1661,2608,3796,5983,8764,13835,20335,32089,47251,74637,110227,174302,

%U 258095,408276,605664,958551,1424659,2256136,3359446,5322449,7937666,12580545

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

%H Gheorghe Coserea, <a href="/A274111/b274111.txt">Table of n, a(n) for n = 0..300</a>

%H K. Manes, A. Sapounakis, I. Tasoulas, P. Tsikouras, <a href="http://arxiv.org/abs/1510.01952">Equivalence classes of ballot paths modulo strings of length 2 and 3</a>, arXiv:1510.01952 [math.CO], 2015, proposition 3.2.

%F 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

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

%o (PARI)

%o x='x; y='y;

%o 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;

%o seq(N) = {

%o   my(y0 = 1 + O('x^N), y1=0);

%o   for (k = 1, N,

%o     y1 = y0 - subst(Fxy, y, y0)/subst(deriv(Fxy, y), y, y0);

%o     if (y1 == y0, break()); y0 = y1);

%o   Vec(y0);

%o };

%o seq(45)  \\ _Gheorghe Coserea_, Jan 05 2017

%Y Cf. A274110-A274115.

%K nonn,walk

%O 0,7

%A _N. J. A. Sloane_, Jun 17 2016

%E a(0)=1 prepended by _Gheorghe Coserea_, Jan 05 2017