A319029 Triangle read by rows: T(n,k) is the number of permutations pi of [n] such that pi has k descents and s(pi) avoids the patterns 132 and 321, where s is West's stack-sorting map (0 <= k <= n-1).

1, 1, 1, 1, 4, 1, 1, 10, 10, 1, 1, 20, 46, 20, 1, 1, 35, 146, 146, 35, 1, 1, 56, 371, 666, 371, 56, 1, 1, 84, 812, 2290, 2290, 812, 84, 1, 1, 120, 1596, 6504, 10198, 6504, 1596, 120, 1, 1, 165, 2892, 16080, 36352, 36352, 16080, 2892, 165, 1

Offset

1,5

Comments

Row sums give A319028.

Links

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

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

Formula

T(n,k) = T(n, n-1-k).

G.f.: F(x,y) + x^3*y*((d/dx)F(x,y))^2, where F(x,y) = (1-x(y+1) - (1 - 2x(y+1) + x^2(y-1)^2)^(1/2))/(2xy) is the generating function of A001263.

Example

Triangle begins:
  1,
  1,   1,
  1,   4,   1,
  1,  10,  10,   1,
  1,  20,  46,  20,   1,
  1,  35, 146, 146,  35,   1,
  1,  56, 371, 666, 371,  56,   1,
  ...

Mathematica

DeleteCases[Flatten[CoefficientList[Series[(1 - x (y + 1) - Sqrt[1 - 2 x (y + 1) + x^2 (y - 1)^2])/(2 x*y) + x^3*y (D[(1 - x (y + 1) - Sqrt[1 - 2 x (y + 1) + x^2 (y - 1)^2])/(2 x*y), x])^2, {x, 0, 10}], {x, y}]], 0]

Crossrefs

Cf. A319028, A001263.

Sequence in context: A214398 A220860 A174043 * A175124 A089447 A082680

Adjacent sequences: A319026 A319027 A319028 * A319030 A319031 A319032

Keyword

easy,nonn,tabl

Author

Colin Defant, Sep 10 2018

Status

approved