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,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

Table of n, a(n) for n=1..42.

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

Cf. A000108. Row sums give A049124.

Sequence in context: A073187 A138159 A118919 * A274404 A101282 A263776

Adjacent sequences: A319117 A319118 A319119 * A319121 A319122 A319123

Keyword

easy,tabf,nonn

Author

Colin Defant, Sep 17 2018

Status

approved