|
%I #40 Feb 24 2024 11:04:03
%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
|
