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

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

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.

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

Example

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

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

Prog

(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

Crossrefs

Cf. A191384, A274110-A274115.

Sequence in context: A218021 A137713 A326490 * A345669 A335093 A143642

Adjacent sequences: A191382 A191383 A191384 * A191386 A191387 A191388

Keyword

nonn,walk

Author

Emeric Deutsch, Jun 01 2011

Status

approved