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

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

Offset: 1

Author

Colin Defant, Sep 17 2018

Keywords

• easy
• tabf
• nonn

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

Examples

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

Links

• Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.

Crossrefs

Cf. A000108. Row sums give A049124.

Programs

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}]]

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