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!)
A274969 Number of walks in the first quadrant starting and ending at (0,0) consisting of 3n steps taken from {E=(1, 0), D=(-1, 1), S=(0, -1)}, no S step occurring before the final E step. 4
1, 1, 4, 21, 121, 728, 4488, 28101, 177859, 1134705, 7283640, 46981740, 304253964, 1976886616, 12880883408, 84130964709, 550649378199, 3610705776755, 23714554702020, 155979407872365, 1027269675638745, 6773476758296220, 44709685668953760, 295402076512228140, 1953492865541875476 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Number of pushall stack words of length 3n. These consist of n 'ρ' letters, n 'λ' letters and n 'μ' letters, such that the count of 'λ' letters never exceeds the count of 'ρ' letters, the count of 'μ' letters never exceeds the count of 'λ' letters, and all the 'ρ' letters occur before any of the 'μ' letters.

A permutation of length n is 2-stack pushall sortable if and only if it can be sorted by a sequence of 3n operations represented by a pushall stack word of length 3n, where ρ corresponds to pushing to the 1st (Right) stack, λ corresponds to popping from the 1st stack and pushing to the 2nd (Left) stack, and μ corresponds to popping from the 2nd stack.

There is an obvious bijection between pushall stack words of length 3n using the letters 'ρ', 'λ', and 'μ', and pushall stack words of length 3n in which 'ρ' and 'μ' are the same symbol. In this way, a(n) is the number of words consisting of n 'λ' letters and 2n 'μ' letters, such that the count of 'λ' letters never exceeds the count of 'μ' letters in any prefix or suffix of the word. This allows a closed form (added below) based on two usages of "Andre's reflection method", in analogy with the Catalan numbers. - Janis Stipins, May 27 2019

LINKS

David Bevan, Table of n, a(n) for n = 0..300

Adeline Pierrot and Dominique Rossin, 2-stack pushall sortable permutations, arXiv:1303.4376 [cs.DM], 2013.

FORMULA

The ogf f=f(z) is algebraic, satisfying the cubic equation (1-16*z+64*z^2) + (-1+21*z-96*z^2)*f + (-4*z+27*z^2)*f^2 + (-4*z^2+27*z^3)*f^3 = 0.

a(n) = A259475(n,n). - Alois P. Heinz, Nov 19 2018

a(n) = binomial(3*n,n) - 2*binomial(3*n,n-1) + binomial(3*n,n-2). - Janis Stipins, May 27 2019

EXAMPLE

For n=2, the four walks are EEDDSS, EEDSDS, EDEDSS and EDESDS.

MATHEMATICA

CoefficientList[Module[{r=0}, Do[r+=Coefficient[1-16z+64z^2+(21z-96z^2)f+(-4z+27z^2)f^2+(-4z^2+27z^3)f^3/.f->r, z, i]z^i, {i, 0, 30}]; r], z]

PROG

(PARI) N=O(z^35); f=1+N; while(f+N<>f=1+(5*z-32*z^2+(-4+27*z)*z*(1+z*f)*f^2)/(1-21*z+96*z^2), ); Vec(f+N) \\ Using that the g.f. is fixed point of T(f)=1+(5*z-32*z^2+(-4+27*z)*z*(1+z*f)*f^2)/(1-21*z+96*z^2). - M. F. Hasler, Jul 13 2016

(PARI) a(n) = binomial(3*n, n) - 2*binomial(3*n, n-1) + binomial(3*n, n-2); \\ Janis Stipins, May 27 2019

CROSSREFS

Walks in the first quadrant from (0,0) to (0,0) with steps from {E, D, S} A005789.

2-stack pushall sortable permutations A274970.

Cf. A259475.

Sequence in context: A182435 A045721 A101810 * A236525 A277292 A001888

Adjacent sequences:  A274966 A274967 A274968 * A274970 A274971 A274972

KEYWORD

nonn,easy

AUTHOR

David Bevan, Jul 13 2016

EXTENSIONS

Data double-checked by M. F. Hasler, Jul 13 2016

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 August 8 02:45 EDT 2020. Contains 336290 sequences. (Running on oeis4.)