A182222 Number T(n,k) of standard Young tableaux of n cells and height >= k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 2, 2, 1, 4, 4, 3, 1, 10, 10, 9, 4, 1, 26, 26, 25, 16, 5, 1, 76, 76, 75, 56, 25, 6, 1, 232, 232, 231, 197, 105, 36, 7, 1, 764, 764, 763, 694, 441, 176, 49, 8, 1, 2620, 2620, 2619, 2494, 1785, 856, 273, 64, 9, 1, 9496, 9496, 9495, 9244, 7308, 3952, 1506, 400, 81, 10, 1

Offset

0,4

Comments

Also number of self-inverse permutations in S_n with longest increasing subsequence of length >= k. T(4,3) = 4: 1234, 1243, 1324, 2134; T(3,0) = T(3,1) = 4: 123, 132, 213, 321; T(5,3) = 16: 12345, 12354, 12435, 12543, 13245, 13254, 14325, 14523, 15342, 21345, 21354, 21435, 32145, 34125, 42315, 52341.

Links

Alois P. Heinz, Rows n = 0..50, flattened

Wikipedia, Involution (mathematics)

Wikipedia, Young tableau

Formula

T(n,k) = A182172(n,n) - A182172(n,k-1) for k>0, T(n,0) = A182172(n,n).

Example

T(4,3) = 4, there are 4 standard Young tableaux of 4 cells and height >= 3:
  +---+   +------+   +------+   +------+
  | 1 |   | 1  2 |   | 1  3 |   | 1  4 |
  | 2 |   | 3 .--+   | 2 .--+   | 2 .--+
  | 3 |   | 4 |      | 4 |      | 3 |
  | 4 |   +---+      +---+      +---+
  +---+
Triangle T(n,k) begins:
    1;
    1,   1;
    2,   2,   1;
    4,   4,   3,   1;
   10,  10,   9,   4,   1;
   26,  26,  25,  16,   5,   1;
   76,  76,  75,  56,  25,   6,  1;
  232, 232, 231, 197, 105,  36,  7,  1;
  764, 764, 763, 694, 441, 176, 49,  8,  1;
  ...

Maple

h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j+
       add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
    end:
g:= proc(n, i, l) option remember;
      `if`(n=0, h(l), `if`(i<1, 0, `if`(i=1, h([l[], 1$n]),
        g(n, i-1, l) +`if`(i>n, 0, g(n-i, i, [l[], i])))))
    end:
T:= (n, k)-> g(n, n, []) -`if`(k=0, 0, g(n, k-1, [])):
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

h[l_] := Module[{n = Length[l]}, Sum[i, {i, l}]! / Product[ Product[1 + l[[i]] - j + Sum [If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
g[n_, i_, l_] := g[n, i, l] = If[n == 0, h[l], If[i < 1, 0, If[i == 1, h[Join[l, Array[1&, n]]], g [n, i-1, l] + If[i > n, 0, g[n-i, i, Append[l, i]]]]]];
t[n_, k_] := g[n, n, {}] - If[k == 0, 0, g[n, k-1, {}]];
Table[Table[t[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Dec 12 2013, translated from Maple *)

Crossrefs

Columns 0-10 give: A000085, A000085 (for n>0), A001189, A218263, A218264, A218265, A218266, A218267, A218268, A218269, A218262.

Diagonal and lower diagonals give: A000012, A000027(n+1), A000290(n+1) for n>0, A131423(n+1) for n>1.

T(2n,n) gives A318289.

Cf. A047884, A049400, A182172.

Sequence in context: A338131 A332601 A348840 * A225639 A110664 A193922

Adjacent sequences: A182219 A182220 A182221 * A182223 A182224 A182225

Keyword

nonn,tabl

Author

Alois P. Heinz, Apr 19 2012

Status

approved