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

1, 1, 1, 1, 2, 3, 5, 7, 12, 18, 31, 47, 81, 125, 216, 337, 583, 918, 1590, 2522, 4372, 6977, 12104, 19415, 33703, 54297, 94306, 152507, 265005, 429974, 747450, 1216297, 2115118, 3450817, 6002813, 9816460, 17080924, 27991422, 48718380, 79989880, 139252802, 229034820, 398806718

Offset: 0

Author

Emeric Deutsch, Jun 01 2011

Keywords

• nonn
• walk

Comments

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.

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

Examples

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

Links

• Gheorghe Coserea, Table of n, a(n) for n = 0..300
• J.-L. Baril, R. Genestier, A. Giorgetti, and A. Petrossian, Rooted planar maps modulo some patternss, Preprint 2016.
• Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
• J.-L. Baril and A. Petrossian, Equivalence Classes of Motzkin Paths Modulo a Pattern of Length at Most Two, J. Int. Seq. 18 (2015) 15.7.1
• 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.
• Helmut Prodinger, Dispersed Dyck paths revisited, arXiv:2402.13026 [math.CO], 2024. See p. 3.

Crossrefs

Cf. A191384, A274110-A274115.

Programs

Maple

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

Mathematica

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

PARI

seq(N) = {
  my(x='x+O('x^N), A001006 = (1 - x - sqrt(1-2*x-3*x^2))/(2*x^2),
     y=subst(A001006, 'x, 'x^2));
  Vec((1+x^2*y) / (1-x+x^2-x^3*y));
};
seq(43)  \\ Gheorghe Coserea, Jan 06 2017

Formula

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

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

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

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

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

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