A319028 Number of permutations pi of [n] such that s(pi) avoids the patterns 132 and 321, where s is West's stack-sorting map.

1, 2, 6, 22, 88, 364, 1522, 6374, 26640, 110980, 460716, 1906172, 7862416, 32341144, 132707626, 543376774, 2220650656, 9060011284, 36908739316, 150159618964, 610186287376, 2476912674664, 10044874544116, 40700948789212, 164788263075808, 666716080038824

Offset: 1

Author

Colin Defant, Sep 10 2018

Keywords

• easy
• nonn

Comments

a(n) is the number of permutations of [n] that avoid the patterns 1342, 34251, 35241, and 45231 and also avoid any 3142 pattern that is not part of a 34152 pattern or a 35142 pattern.

Links

• Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.

Crossrefs

Cf. A000108. Row sums of triangles A319029 and A319030.

Programs

Mathematica

Rest[CoefficientList[Series[(1 - Sqrt[1 - 4 x] - 5 x + 3 x*Sqrt[1 - 4 x] + 5 x^2)/(x - 4 x^2), {x, 0, 10}], x]]
RecurrenceTable[{n (n + 1) a[n] - 4 n (3 n - 2) a[n - 1] + 4 (2 n - 3) (6 n - 5) a[n - 2] - 16 (2 n - 5) (2 n - 3) a[n - 3] == 0, a[1] == 1, a[2] == 2, a[3] == 6}, a, {n, 1, 30}] (* Bruno Berselli, Sep 14 2018 *)

Formula

G.f.: c(x) - 1 + x^3*(c'(x))^2, where c(x) is the generating function of the Catalan numbers.

n*(n + 1)*a(n) - 4*n*(3*n - 2)*a(n-1) + 4*(2*n - 3)*(6*n - 5)*a(n-2) - 16*(2*n - 5)*(2*n - 3)*a(n-3) = 0 with n > 3. - Bruno Berselli, Sep 14 2018