A274112 Number of equivalence classes of ballot paths of length n for the string ddu.

1, 1, 1, 1, 2, 3, 4, 5, 8, 12, 17, 23, 35, 52, 75, 105, 157, 232, 337, 480, 712, 1049, 1529, 2199, 3248, 4777, 6976, 10092, 14869, 21845, 31937, 46377, 68222, 100159, 146536, 213328, 313487, 460023, 673351, 981976, 1441999, 2115350, 3097326, 4522529, 6637879, 9735205, 14257734, 20836827, 30572032, 44829766, 65666593

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, Section 3.4.

Crossrefs

Cf. A274110-A274115, A263719.

Programs

Maple

A274112 := proc(n)
    add( (n-4*i+1)/(n-3*i+1)*binomial(n-2*i,i),i=0..n/4) ;
end proc:
seq(A274112(n),n=0..50) ; # R. J. Mathar, Jun 20 2016

Mathematica

a[n_] := Sum[(n - 4*i + 1)/(n - 3*i + 1)*Binomial[n - 2*i, i], {i, 0, n/4} ];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Nov 27 2017, after R. J. Mathar *)

PARI

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

Formula

G.f. y satisfies: 0 = x*(x^3+x-1)*y^2 + (2*x-1)*y + 1. - Gheorghe Coserea, Jan 05 2017

G.f.: 1/(1 - x - x^4/(1 - x^4/(1 - x^4/(1 - x^4/(1 - ...))))), a continued fraction. - Ilya Gutkovskiy, Jul 26 2017

a(n) ~ 3 * (1+r^2)^(n+1) / (7 + 4*r + 8*r^2), where r = A263719 = ((9+sqrt(93))/2)^(1/3)/3^(2/3) - (2/(3*(9+sqrt(93))))^(1/3) = 0.682327803828019327369483739711048256891188581898... is the real root of the equation r^3 + r = 1. - Vaclav Kotesovec, Nov 27 2017

Extensions

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