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