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,2

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

Table of n, a(n) for n=1..26.

Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 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

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

Crossrefs

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

Sequence in context: A150263 A165534 A165535 * A165536 A032351 A165537

Adjacent sequences: A319025 A319026 A319027 * A319029 A319030 A319031

Keyword

easy,nonn

Author

Colin Defant, Sep 10 2018

Status

approved