cp's OEIS Frontend

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)).

%I A319252 #8 Sep 16 2018 16:42:29
%S A319252 1,2,4,2,8,10,16,36,4,32,112,36,64,320,200,10,128,864,880,130,256,
%T A319252 2240,3360,980,28,512,5632,11648,5600,476,1024,13824,37632,26880,4536,
%U A319252 84,2048,33280,115200,114240,31920,1764
%N 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)).
%C A319252 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.
%H A319252 C. Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-sorting preimages of permutation classes</a>, arXiv:1809.03123 [math.CO], 2018.
%F A319252 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.
%e A319252 Triangle begins:
%e A319252    1;
%e A319252    2;
%e A319252    4,   2;
%e A319252    8,  10;
%e A319252   16,  36,  4;
%e A319252   32, 112, 36;
%e A319252   ...
%t A319252 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}]]
%Y A319252 Row sums give A071721. Cf. A091894, A319251.
%K A319252 easy,nonn,tabf
%O A319252 1,2
%A A319252 _Colin Defant_, Sep 15 2018