OFFSET
3,2
COMMENTS
If pi is any permutation of [n] with exactly 1 descent, then the number of preimages of pi under West's stack-sorting map that have k+1 valleys is at most T(n,k).
LINKS
C. Defant, Preimages under the stack-sorting algorithm, arXiv:1511.05681 [math.CO], 2015-2018.
C. Defant, Preimages under the stack-sorting algorithm, Graphs Combin., 33 (2017), 103-122.
C. Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
FORMULA
T(n,k) = Sum_{i=1..n-2} Sum_{j=1..k} V(i,j) * V(n-1-i,m+1-j), where V(i,j) = 2^{i-2j+1} * (1/j) * binomial(i-1, 2j-2) * binomial(2j-2, j-1) are the numbers found in the triangle A091894.
EXAMPLE
Triangle begins:
1;
4;
12, 2;
32, 16;
80, 80, 5;
192, 320, 60;
448, 1120, 420, 14;
...
T(1,1) = 1 because the permutation 213 has one preimage under West's stack-sorting map (namely, 231), and this permutation has 2 valleys.
MATHEMATICA
Flatten[Table[Table[Sum[Sum[(2^(i - 2 j + 1)) Binomial[i - 1, 2 j - 2]CatalanNumber[j - 1] (2^((n - 1 - i) - 2 (m + 1 - j) + 1)) Binomial[(n - 1 - i) - 1, 2 (m + 1 - j) - 2] CatalanNumber[(m + 1 - j) - 1], {j, 1, m}], {i, 1, n - 2}], {m, 1, Floor[(n - 1)/2]}], {n, 1, 10}]]
CROSSREFS
KEYWORD
easy,nonn,tabf
AUTHOR
Colin Defant, Sep 14 2018
STATUS
approved