OFFSET
1,2
COMMENTS
T(n,0) = A000108(n).
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).
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.
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
LINKS
Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
EXAMPLE
Triangle begins:
1;
2;
5, 1;
14, 6;
42, 28, 1;
132, 120, 12;
429, 495, 90, 1;
1430, 2002, 550, 20;
4862, 8008, 3003, 220, 1;
16796, 31824, 15288, 1820, 30;
58786, 125970, 74256, 12740, 455, 1;
208012, 497420, 348840, 79968, 4900, 42;
...
MATHEMATICA
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}]]
PROG
(PARI) T(n, k) = binomial(n-k-1, k) * binomial(2*n-2*k, n)/(n+1);
tabf(nn) = for (n=1, nn, for (k=0, (n-1)\2, print1(T(n, k), ", ")); print); \\ Michel Marcus, Sep 20 2018
CROSSREFS
KEYWORD
easy,tabf,nonn
AUTHOR
Colin Defant, Sep 17 2018
STATUS
approved