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.
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
Offset: 0
Examples
For n=2, the four walks are EEDDSS, EEDSDS, EDEDSS and EDESDS.
Links
- David Bevan, Table of n, a(n) for n = 0..300
- Nicolas Borie and Justine Falque, Product-Coproduct Prographs and Triangulations of the Sphere, 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.
- Adeline Pierrot and Dominique Rossin, 2-stack pushall sortable permutations, arXiv:1303.4376 [cs.DM], 2013.
Crossrefs
Programs
-
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]
-
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
Formula
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.
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
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
Extensions
Data double-checked by M. F. Hasler, Jul 13 2016
Comments