cp's OEIS Frontend

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

%I A317555 #14 Sep 15 2018 05:26:00
%S A317555 1,4,12,2,32,16,80,80,5,192,320,60,448,1120,420,14,1024,3584,2240,224,
%T A317555 2304,10752,10080,2016,42,5120,30720,40320,13440,840,11264,84480,
%U A317555 147840,73920,9240,132,24576,225280,506880,354816,73920,3168
%N A317555 Triangle read by rows: T(n,k) is the number of preimages of the permutation 21345...n under West's stack-sorting map that have k+1 valleys (1 <= k <= floor((n-1)/2)).
%C A317555 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).
%H A317555 C. Defant, <a href="https://arxiv.org/abs/1511.05681">Preimages under the stack-sorting algorithm</a>, arXiv:1511.05681 [math.CO], 2015-2018.
%H A317555 C. Defant, <a href="https://doi.org/10.1007/s00373-016-1752-5">Preimages under the stack-sorting algorithm</a>, Graphs Combin., 33 (2017), 103-122.
%H A317555 C. Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-sorting preimages of permutation classes</a>, arXiv:1809.03123 [math.CO], 2018.
%F A317555 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.
%e A317555 Triangle begins:
%e A317555     1;
%e A317555     4;
%e A317555    12,    2;
%e A317555    32,   16;
%e A317555    80,   80,   5;
%e A317555   192,  320,  60;
%e A317555   448, 1120, 420, 14;
%e A317555   ...
%e A317555 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.
%t A317555 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}]]
%Y A317555 Row sums give A002057.
%K A317555 easy,nonn,tabf
%O A317555 3,2
%A A317555 _Colin Defant_, Sep 14 2018