login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A191385 Number of dispersed Dyck paths of length n having no ascents of length 1. 3
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 (list; graph; refs; listen; history; text; internal format)
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, 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, 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, P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015.

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: A169986 A218021 A137713 * A143642 A192685 A293543

Adjacent sequences:  A191382 A191383 A191384 * A191386 A191387 A191388

KEYWORD

nonn,walk

AUTHOR

Emeric Deutsch, Jun 01 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 21 15:32 EDT 2019. Contains 323444 sequences. (Running on oeis4.)