A319251 Triangle read by rows: T(n,k) is the number of permutations pi of [n] with k descents such that s(pi) avoids the patterns 132, 231, 312, and 321, where s denotes West's stack-sorting map.

1, 1, 1, 1, 4, 1, 1, 8, 8, 1, 1, 13, 28, 13, 1, 1, 19, 70, 70, 19, 1, 1, 26, 145, 250, 145, 26, 1, 1, 34, 266, 700, 700, 266, 34, 1, 1, 43, 448, 1666, 2548, 1666, 448, 43, 1, 1, 53, 708, 3528, 7644, 7644, 3528, 708, 53, 1

Offset: 1

Author

Colin Defant, Sep 15 2018

Keywords

• easy
• nonn
• tabl

Comments

Rows are symmetric, so T(n,k) = T(n,n-1-k).

T(n,k) is the number of permutations of [n] that avoid the patterns 1342, 2341, 3142, 3241, 3412, and 3421 and have k descents.

Examples

			Triangle begins:
  1,
  1, 1,
  1, 4, 1,
  1, 8, 8, 1,
  1, 13, 28, 13, 1,
  1, 19, 70, 70, 19, 1
  ...
		

Links

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

Crossrefs

Row sums give A071721. Cf. A001263, A319252.

Programs

Mathematica

Flatten[Table[Table[(1/n) Binomial[n, m + 1] Binomial[n, m] + Sum[Sum[(1/(n - i - 1)) Binomial[n - i - 1, j] Binomial[n - i - 1, j - 1] (1/i) Binomial[i, m - j + 1] Binomial[i, m - j], {j, 1, m}], {i, 1, n - 2}], {m, 0, n - 1}], {n, 1, 10}]]

Formula

T(n,k) = N(n,k+1) + Sum_{i=1..n-2} Sum_{j=1..m} N(n-i-1,j) * N(i,k-j+1), where N(i,j) = (1/i) * binomial(i,j) * binomial(i,j-1) are the Narayana numbers given in A001263.

From Vladimir Kruchinin, Nov 16 2020: (Start)

G.f.: A001263(x,y) + x*A001263(x,y)^2.

T(n,k) = N(n,k) +2*C(n-1,k-2)*C(n-1,k)/(n-1). (End)