A191384 -id:A191384 - cp's OEIS frontend

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

Emeric Deutsch, Jun 01 2011

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

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

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.

Cf. A191384, A274110-A274115.

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

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

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

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

A191386 Number of ascents of length 1 in all dispersed Dyck paths of length n (i.e., in all Motzkin paths of length n with no (1,0) steps at positive heights). An ascent is a maximal sequence of consecutive (1,1)-steps.

Original entry on oeis.org

0, 0, 1, 2, 5, 10, 23, 46, 102, 204, 443, 886, 1898, 3796, 8054, 16108, 33932, 67864, 142163, 284326, 592962, 1185924, 2464226, 4928452, 10209620, 20419240, 42190558, 84381116, 173962532, 347925064, 715908428, 1431816856, 2941192472, 5882384944, 12065310083, 24130620166

Offset: 0

Emeric Deutsch, Jun 01 2011

nonn

a(n+2) is the length of a lock-breaking sequence for a lock having buttons 1,2,...,n and a reset button R, and a combination that is any subset of the buttons (the lock opens if the proper combination is pressed after an R). For example, R123R23R31 is a length-10 sequence that unlocks the case of 3 buttons, because each of the 8 subsets occurs somewhere in the sequence between resets. This problem is due to John Guilford. Proof that the shortest sequence has length a(n+2) is due to Dan Velleman and Stan Wagon. - Stan Wagon, Feb 17 2019

			a(4) = 5 because in HHHH, HHUD, HUDH, UDHH, UDUD, and UUDD we have a total of 0+1+1+1+2+0=5 ascents of length 1.

G. C. Greubel, Table of n, a(n) for n = 0..1000
F. Blanchet-Sadri, Kun Chen, Kenneth Hawes, Dyck Words, Lattice Paths, and Abelian Borders, arXiv:1708.06461 [cs.FL], 2017, Conjecture 1.
Kairi Kangro, Mozhgan Pourmoradnasseri, Dirk Oliver Theis, Short note on the number of 1-ascents in dispersed dyck paths, arXiv:1603.01422 [math.CO], 2016.

Cf. A191384.

If the two initial zeros are omitted, we get A323988.

m:=40; R:=PowerSeriesRing(Rationals(), m); [0,0] cat Coefficients(R!( x^2*(1+Sqrt(1-4*x^2))/(2*(1-2*x)*Sqrt(1-4*x^2)) )); // G. C. Greubel, Feb 17 2019

g := (1/2)*z^2*(1+sqrt(1-4*z^2))/((1-2*z)*sqrt(1-4*z^2)): gser := series(g, z = 0, 38): seq(coeff(gser, z, n), n = 0 .. 35);

CoefficientList[Series[(1/2)*x^2*(1+Sqrt[1-4*x^2])/((1-2*x)*Sqrt[1-4*x^2]), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 21 2014 *)

z='z+O('z^40); concat([0,0], Vec(z^2*(1+sqrt(1-4*z^2))/(2*(1-2*z)*sqrt(1-4*z^2)))) \\ G. C. Greubel, Mar 26 2017

(x^2*(1+sqrt(1-4*x^2))/(2*(1-2*x)*sqrt(1-4*x^2))).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Feb 17 2019

G.f.: g(z) = z^2*(1+sqrt(1-4*z^2))/(2*(1-2*z)*sqrt(1-4*z^2)). [The next three formulas follow from this. - N. J. A. Sloane, Feb 13 2019]
-(n-2)*a(n) + 2*(n-2)*a(n-1) + 4*(n-3)*a(n-2) - 8*(n-3)*a(n-3) = 0. - R. J. Mathar, Jun 14 2016
For n > 1, a(n) = 2^(n - 3) + binomial(n-2, floor(n/2-1))*(n - 1)/2. [See Kangro-Pourmoradnasseri-Theis, first page] - Dan Velleman, Feb 12 2019
a(n) = Sum_{k>=0} k*A191384(n,k).
a(n) ~ 2^(n-5/2)*sqrt(n)/sqrt(Pi) * (1 + sqrt(Pi)/sqrt(2*n)). - Vaclav Kotesovec, Mar 21 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula