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

Author

Colin Defant, Sep 10 2018

Keywords

• easy
• nonn
• tabl

Comments

Row sums give A319028.

Examples

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

Links

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

Crossrefs

Cf. A319028, A001263.

Programs

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]

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.