login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Number of dispersed Dyck paths of length n having no ascents of length 1.
3

%I #43 Oct 20 2024 04:08:24

%S 1,1,1,1,2,3,5,7,12,18,31,47,81,125,216,337,583,918,1590,2522,4372,

%T 6977,12104,19415,33703,54297,94306,152507,265005,429974,747450,

%U 1216297,2115118,3450817,6002813,9816460,17080924,27991422,48718380,79989880,139252802,229034820,398806718

%N Number of dispersed Dyck paths of length n having no ascents of length 1.

%C Dispersed Dyck paths are Motzkin paths with no (1,0) steps at positive heights. An ascent is a maximal sequence of consecutive (1,1)-steps.

%C The number of UU-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are UU-equivalent iff the positions of pattern UU are identical in these paths. - _Sergey Kirgizov_, Apr 08 2018

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

%H J.-L. Baril, R. Genestier, A. Giorgetti, and A. Petrossian, <a href="http://jl.baril.u-bourgogne.fr/cartes.pdf">Rooted planar maps modulo some patternss</a>, Preprint 2016.

%H Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, <a href="https://arxiv.org/abs/1804.01293">Enumeration of Łukasiewicz paths modulo some patterns</a>, arXiv:1804.01293 [math.CO], 2018.

%H J.-L. Baril and A. Petrossian, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Baril/baril3.html">Equivalence Classes of Motzkin Paths Modulo a Pattern of Length at Most Two</a>, J. Int. Seq. 18 (2015) 15.7.1

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

%H Helmut Prodinger, <a href="https://arxiv.org/abs/2402.13026">Dispersed Dyck paths revisited</a>, arXiv:2402.13026 [math.CO], 2024. See p. 3.

%F a(n) = A191384(n,0).

%F G.f.: g(z) = ((1-z)^2 - sqrt((1+z^2)*(1-3*z^2)))/(2*z*(z^3-(1-z)^2)).

%F a(n-1) = Sum_{m=floor((n+1)/2)..n} ((2*m-n)*sum(j=2*m-n..m, binomial(n-2*m+2*j-1,j-1)*(-1)^(j-m)*binomial(m,j)))/m. - _Vladimir Kruchinin_, Mar 09 2013

%F Recurrence: (n+1)*a(n) = 2*(n+1)*a(n-1) + (n-5)*a(n-2) - 3*(n-3)*a(n-3) + (5*n-19)*a(n-4) - 2*(4*n-17)*a(n-5) + 3*(n-5)*a(n-6) - 3*(n-5)*a(n-7). - _Vaclav Kotesovec_, Mar 21 2014

%F a(n) ~ 3^(n/2+1) * (7*sqrt(3)+12 +(-1)^n*(7*sqrt(3)-12)) / (n^(3/2)*sqrt(2*Pi)). - _Vaclav Kotesovec_, Mar 21 2014

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

%e a(5)=3 because we have HHHHH, HUUDD, and UUDDH, where U=(1,1), D=(1,-1), and H=(1,0).

%p g := (((1-z)^2-sqrt((1+z^2)*(1-3*z^2)))*1/2)/(z*(z^3-(1-z)^2)): gser := series(g, z = 0, 45): seq(coeff(gser, z, n), n = 0 .. 42);

%t CoefficientList[Series[(((1-x)^2-Sqrt[(1+x^2)*(1-3*x^2)])*1/2)/(x*(x^3-(1-x)^2)), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Mar 21 2014 *)

%o (PARI)

%o seq(N) = {

%o my(x='x+O('x^N), A001006 = (1 - x - sqrt(1-2*x-3*x^2))/(2*x^2),

%o y=subst(A001006, 'x, 'x^2));

%o Vec((1+x^2*y) / (1-x+x^2-x^3*y));

%o };

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

%Y Cf. A191384, A274110-A274115.

%K nonn,walk

%O 0,5

%A _Emeric Deutsch_, Jun 01 2011