|
%I #42 Mar 06 2019 08:11:15
%S 1,2,5,1,14,6,42,28,1,132,120,12,429,495,90,1,1430,2002,550,20,4862,
%T 8008,3003,220,1,16796,31824,15288,1820,30,58786,125970,74256,12740,
%U 455,1,208012,497420,348840,79968,4900,42
%N T(n, k) = binomial(n - k - 1, k)*binomial(2*n - 2*k, n)/(n + 1), for n >= 1 and 0 <= k <= floor((n - 1)/2), triangle read by rows.
%C T(n,0) = A000108(n).
%C Let L(u,v) be the set of integer partitions whose Young diagrams fit inside a u by v rectangle. Given lambda in L(u,v), let E(lambda) be the number of partitions whose Young diagrams fit inside the Young diagram of lambda. Also, for 1 <= i <= v, let x_i(lambda)-1 be the number of parts of lambda of length v+1-i. Let x_{v+1}(lambda) = u+v+1-Sum_{i=1..v} x_i(lambda) so that (x_1(lambda), ..., x_{v+1}(lambda)) is a composition of u+v+1 into v+1 parts. Let F(lambda) = Product_{i=1..v+1} Catalan(x_i(lambda)). Conjecturally, T(n,k) = Sum_{lambda in L(n-2k-1)} E(lambda) * F(lambda).
%C Conjecturally, T(n,k) is the number of permutations pi of [n] such that s(pi) has k descents and avoids the patterns 231, 312, and 321, where s is West's stack-sorting map.
%C Conjecturally, T(n,k) is the number of permutations pi of [n] that avoid the 4 patterns 4312, 4321, 4231, 3241 (more succinctly, that avoid 32x1 for all x) and contain k entries which are neither left-right maxima nor right-left minima (equivalently, contain k entries that serve as the "2" of a 321). - _David Callan_, Mar 05 2019
%H Colin Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-sorting preimages of permutation classes</a>, arXiv:1809.03123 [math.CO], 2018.
%e Triangle begins:
%e 1;
%e 2;
%e 5, 1;
%e 14, 6;
%e 42, 28, 1;
%e 132, 120, 12;
%e 429, 495, 90, 1;
%e 1430, 2002, 550, 20;
%e 4862, 8008, 3003, 220, 1;
%e 16796, 31824, 15288, 1820, 30;
%e 58786, 125970, 74256, 12740, 455, 1;
%e 208012, 497420, 348840, 79968, 4900, 42;
%e ...
%t Flatten[Table[Table[(1/(n + 1)) Binomial[n - k - 1, k] Binomial[2 n - 2 k, n], {k, 0, Floor[(n - 1)/2]}], {n, 1, 12}]]
%o (PARI) T(n,k) = binomial(n-k-1,k) * binomial(2*n-2*k,n)/(n+1);
%o tabf(nn) = for (n=1, nn, for (k=0, (n-1)\2, print1(T(n,k), ", ")); print); \\ _Michel Marcus_, Sep 20 2018
%Y Cf. A000108. Row sums give A049124.
%K easy,tabf,nonn
%O 1,2
%A _Colin Defant_, Sep 17 2018
|
