A274114 Number of equivalence classes of Dyck paths of semilength n for the string uuu.

1, 1, 1, 2, 4, 8, 17, 37, 81, 180, 405, 917, 2090, 4795, 11054, 25589, 59475, 138712, 324483, 761163, 1790028, 4219139, 9965328, 23582735, 55906518, 132751359, 315700152, 751837207, 1792853416, 4280568845, 10232005939, 24484563844, 58650123942, 140625967460, 337488663293, 810641635789

Offset: 0

Author

N. J. A. Sloane, Jun 17 2016

Keywords

• nonn
• walk

Links

• Gheorghe Coserea, Table of n, a(n) for n = 0..301
• 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.

Crossrefs

Cf. A274110-A274115.

Programs

Mathematica

F[x_, y_] = x y^3 - (1 + 2x) y^2 + (1 + 3x) y - x;
Y[n_] := Module[{y0 = 1, y1 = 0}, For[k = 1, k <= n, k++, y1 = y0 - F[x, y0] / (D[F[x, y], y] /. y -> y0) + O[x]^n // Normal; If[y1 == y0, Break[]]; y0 = y1]; y0];
seq[n_] := Module[{y = Y[n]}, ((1 + x y)/(1 - x (y-1)^2)) + O[x]^n // CoefficientList[#, x]&];
seq[36] (* Jean-François Alcover, Jul 27 2018, after Gheorghe Coserea *)

PARI

x='x; y='y;
Fxy = x*y^3 - (1+2*x)*y^2 + (1+3*x)*y - x;
Y(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);
  y0;
};
seq(N) = my(y = Y(N)); Vec((1 + x*y)/(1 - x*(y-1)^2));
seq(35) \\ Gheorghe Coserea, Jan 05 2017

Formula

A(x) = (1 + x*y)/(1 - x*(y-1)^2), where 0 = x*y^3 - (1+2*x)*y^2 + (1+3*x)*y - x with y(0)=1. - Gheorghe Coserea, Jan 05 2017

a(n) ~ sqrt(51/4 + 577*sqrt(2)/64 + 19*sqrt(180250 + 127456*sqrt(2))/448) * (sqrt(13 + 16*sqrt(2))/2 - 1/2)^n / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Apr 25 2020

Extensions

a(0)=1 prepended and more terms added by Gheorghe Coserea, Jan 05 2017