login
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)).
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
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
KEYWORD
easy,nonn,tabf
AUTHOR
Colin Defant, Sep 15 2018
STATUS
approved