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

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.

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

Example

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

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}]]

Crossrefs

Row sums give A071721. Cf. A001263, A319252.

Sequence in context: A347676 A177947 A132789 * A100754 A332307 A296405

Adjacent sequences: A319248 A319249 A319250 * A319252 A319253 A319254

Keyword

easy,nonn,tabl

Author

Colin Defant, Sep 15 2018

Status

approved