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,4

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.

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..(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

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

Prog

(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
(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 */

Crossrefs

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

Sequence in context: A058520 A127680 A136750 * A097107 A098083 A182900

Adjacent sequences: A274112 A274113 A274114 * A274116 A274117 A274118

Keyword

nonn,walk

Author

N. J. A. Sloane, Jun 17 2016

Extensions

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

Status

approved