A319252 Triangle read by rows: T(n,k) is the number of permutations pi of [n] with k+1 valleys such that s(pi) avoids the patterns 132, 231, 312, and 321, where s denotes West's stack-sorting map (0 <= k <= floor((n-1)/2)).

1, 2, 4, 2, 8, 10, 16, 36, 4, 32, 112, 36, 64, 320, 200, 10, 128, 864, 880, 130, 256, 2240, 3360, 980, 28, 512, 5632, 11648, 5600, 476, 1024, 13824, 37632, 26880, 4536, 84, 2048, 33280, 115200, 114240, 31920, 1764

Offset

1,2

Comments

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

Links

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

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

Formula

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

Example

Triangle begins:
   1;
   2;
   4,   2;
   8,  10;
  16,  36,  4;
  32, 112, 36;
  ...

Mathematica

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

Crossrefs

Row sums give A071721. Cf. A091894, A319251.

Sequence in context: A068217 A303603 A308044 * A114593 A114655 A228890

Adjacent sequences: A319249 A319250 A319251 * A319253 A319254 A319255

Keyword

easy,nonn,tabf

Author

Colin Defant, Sep 15 2018

Status

approved