login
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.
2
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
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
KEYWORD
easy,nonn
AUTHOR
Colin Defant, Sep 10 2018
STATUS
approved