

A317555


Triangle read by rows: T(n,k) is the number of preimages of the permutation 21345...n under West's stacksorting map that have k+1 valleys (1 <= k <= floor((n1)/2)).


0



1, 4, 12, 2, 32, 16, 80, 80, 5, 192, 320, 60, 448, 1120, 420, 14, 1024, 3584, 2240, 224, 2304, 10752, 10080, 2016, 42, 5120, 30720, 40320, 13440, 840, 11264, 84480, 147840, 73920, 9240, 132, 24576, 225280, 506880, 354816, 73920, 3168
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 stacksorting map that have k+1 valleys is at most T(n,k).


LINKS

Table of n, a(n) for n=3..44.
C. Defant, Preimages under the stacksorting algorithm, arXiv:1511.05681 [math.CO], 20152018.
C. Defant, Preimages under the stacksorting algorithm, Graphs Combin., 33 (2017), 103122.
C. Defant, Stacksorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.


FORMULA

T(n,k) = Sum_{i=1..n2} Sum_{j=1..k} V(i,j) * V(n1i,m+1j), where V(i,j) = 2^{i2j+1} * (1/j) * binomial(i1, 2j2) * binomial(2j2, j1) 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 stacksorting 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

Row sums give A002057.
Sequence in context: A104063 A260430 A243347 * A213343 A308518 A307874
Adjacent sequences: A317552 A317553 A317554 * A317556 A317557 A317558


KEYWORD

easy,nonn,tabf


AUTHOR

Colin Defant, Sep 14 2018


STATUS

approved



