login
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.
11
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
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
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.
Sequence in context: A338131 A332601 A348840 * A225639 A110664 A193922
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Apr 19 2012
STATUS
approved