cp's OEIS Frontend

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.

%I A274969 #44 Mar 22 2022 02:25:18
%S A274969 1,1,4,21,121,728,4488,28101,177859,1134705,7283640,46981740,
%T A274969 304253964,1976886616,12880883408,84130964709,550649378199,
%U A274969 3610705776755,23714554702020,155979407872365,1027269675638745,6773476758296220,44709685668953760,295402076512228140,1953492865541875476
%N 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.
%C A274969 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.
%C A274969 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.
%C A274969 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
%H A274969 David Bevan, <a href="/A274969/b274969.txt">Table of n, a(n) for n = 0..300</a>
%H A274969 Nicolas Borie and Justine Falque, <a href="https://arxiv.org/abs/2202.05757">Product-Coproduct Prographs and Triangulations of the Sphere</a>, arXiv:2202.05757 [math.CO], 2022. Proceedings of the 34th Conference on Formal Power Series and Algebraic Combinatorics (Bangalore), Séminaire Lotharingien de Combinatoire XX (2022). See Proposition 1, p. 10.
%H A274969 Adeline Pierrot and Dominique Rossin, <a href="http://arxiv.org/abs/1303.4376">2-stack pushall sortable permutations</a>, arXiv:1303.4376 [cs.DM], 2013.
%F A274969 The o.g.f. 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.
%F A274969 a(n) = A259475(n,n). - _Alois P. Heinz_, Nov 19 2018
%F A274969 a(n) = binomial(3*n,n) - 2*binomial(3*n,n-1) + binomial(3*n,n-2). - _Janis Stipins_, May 27 2019
%F A274969 G.f.: (2*(1 - 6*x)*cos(arccos(1 - (27*x)/2)/6)/sqrt(4 - 27*x) + 4*sqrt(3)*sqrt(x)*sin(arcsin(3*sqrt(3)*sqrt(x)/2)/3) - 1)/(3*x). - _Stefano Spezia_, Feb 19 2022
%e A274969 For n=2, the four walks are EEDDSS, EEDSDS, EDEDSS and EDESDS.
%t A274969 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]
%o A274969 (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
%o A274969 (PARI) a(n) = binomial(3*n,n) - 2*binomial(3*n,n-1) + binomial(3*n,n-2); \\ _Janis Stipins_, May 27 2019
%Y A274969 Walks in the first quadrant from (0,0) to (0,0) with steps from {E, D, S} A005789.
%Y A274969 2-stack pushall sortable permutations A274970.
%Y A274969 Cf. A259475.
%K A274969 nonn,easy
%O A274969 0,3
%A A274969 _David Bevan_, Jul 13 2016
%E A274969 Data double-checked by _M. F. Hasler_, Jul 13 2016