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

%I #53 Nov 18 2024 22:31:27

%S 1,1,1,2,4,8,17,35,75,157,337,712,1529,3248,6976,14869,31937,68222,

%T 146536,313487,673351,1441999,3097326,6637879,14257734,30572032,

%U 65666593,140860379,302557585,649202036,1394434685,2992721902,6428118868,13798302512,29637567305,63626933527,136665012979

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

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

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

%H Cyril Banderier and Michael Wallner, <a href="https://arxiv.org/abs/1707.01931">Lattice paths with catastrophes</a>, arXiv:1707.01931 [math.CO], 2017.

%H Jean-Luc Baril and Sergey Kirgizov, <a href="https://arxiv.org/abs/2104.01186">Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths</a>, arXiv:2104.01186 [math.CO], 2021.

%H K. Manes, A. Sapounakis, I. Tasoulas, and 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.

%F A(x) = 1 + x/(1 - x*(1+x)*A000108(x^2)). - _Gheorghe Coserea_, Jan 06 2017

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

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

%t A[x_] = 1 + x/(1 + ((1 + x)(Sqrt[1 - 4x^2] - 1))/(2x)) + O[x]^40;

%t CoefficientList[A[x], x] (* _Jean-François Alcover_, Jul 27 2018, after _Gheorghe Coserea_ *)

%o (PARI)

%o seq(N) = {

%o my(x='x+O('x^N),

%o A000108 = 1+x*Ser(vector(N\2, n, binomial(2*n,n)/(n+1)),'x));

%o Vec(1+x/(1 - x*(1+x)*subst(A000108,'x,'x^2)));

%o };

%o seq(37) \\ _Gheorghe Coserea_, Jan 06 2017

%o (Maxima)

%o 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 */

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

%K nonn,walk,changed

%O 0,4

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

%E a(0)=1 prepended and more terms from _Gheorghe Coserea_, Jan 06 2017