login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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

LINKS

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.

FORMULA

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

EXAMPLE

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.

MAPLE

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

MATHEMATICA

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

PROG

(PARI) 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

(MAGMA) m:=40; R<x>:=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

(Sage) (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

CROSSREFS

Cf. A191384.

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

Sequence in context: A068054 A174542 A007182 * A323988 A026677 A109165

Adjacent sequences:  A191383 A191384 A191385 * A191387 A191388 A191389

KEYWORD

nonn

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 June 17 19:09 EDT 2021. Contains 345085 sequences. (Running on oeis4.)