A274115 Number of equivalence classes of Dyck paths of semilength n for the string duu.

1, 1, 1, 2, 4, 8, 17, 35, 75, 157, 337, 712, 1529, 3248, 6976, 14869, 31937, 68222, 146536, 313487, 673351, 1441999, 3097326, 6637879, 14257734, 30572032, 65666593, 140860379, 302557585, 649202036, 1394434685, 2992721902, 6428118868, 13798302512, 29637567305, 63626933527, 136665012979

Offset: 0

Author

N. J. A. Sloane, Jun 17 2016

Keywords

• nonn
• walk

Comments

a(n+1) is also the number of Dyck meanders of length n, where catastrophes are allowed. A catastrophe is a direct jump from any altitude > 0 to 0, see the Banderier-Wallner article. - Cyril Banderier, May 30 2019

Links

• Gheorghe Coserea, Table of n, a(n) for n = 0..300
• Cyril Banderier and Michael Wallner, Lattice paths with catastrophes, arXiv:1707.01931 [math.CO], 2017.
• Jean-Luc Baril and Sergey Kirgizov, Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths, arXiv:2104.01186 [math.CO], 2021.
• K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015.

Crossrefs

Cf. A000108, A274110, A274111, A274112, A274113, A274114.

Programs

Mathematica

A[x_] = 1 + x/(1 + ((1 + x)(Sqrt[1 - 4x^2] - 1))/(2x)) + O[x]^40;
CoefficientList[A[x], x] (* Jean-François Alcover, Jul 27 2018, after Gheorghe Coserea *)

Maxima

a(n):=if n<2 then 1 else sum((k+1)*sum((binomial(k+1,2*k+2*i-n+3)*binomial(k+2*i,i))/(k+i+1),i,0,(n-k)/2),k,0,n); /* Vladimir Kruchinin, Feb 14 2019 */

PARI

seq(N) = {
  my(x='x+O('x^N),
     A000108 = 1+x*Ser(vector(N\2, n, binomial(2*n,n)/(n+1)),'x));
  Vec(1+x/(1 - x*(1+x)*subst(A000108,'x,'x^2)));
};
seq(37)  \\ Gheorghe Coserea, Jan 06 2017

Formula

A(x) = 1 + x/(1 - x*(1+x)*A000108(x^2)). - Gheorghe Coserea, Jan 06 2017

a(n) = Sum_{k=0..n} (k+1)*Sum_{i=0..floor((n-k)/2)} C(k+1,2*k+2*i-n+3)*C(k+2*i,i)/(k+i+1), n>1, a(0)=1,a(1)=1. - Vladimir Kruchinin, Feb 14 2019

D-finite with recurrence (-n+1)*a(n) +2*a(n-1) +7*(n-3)*a(n-2) +3*(n-5)*a(n-3) +(-11*n+53)*a(n-4) +4*(-3*n+16)*a(n-5) +4*(-n+6)*a(n-6)=0. - R. J. Mathar, Sep 27 2020

Extensions

a(0)=1 prepended and more terms from Gheorghe Coserea, Jan 06 2017