OFFSET
0,13
COMMENTS
Also the number A(n,k) of standard Young tableaux of n cells and <= k columns.
A(n,k) is also the number of n-length words w over a k-ary alphabet {a1,a2,...,ak} such that for every prefix z of w we have #(z,a1) >= #(z,a2) >= ... >= #(z,ak), where #(z,x) counts the letters x in word z. The A(4,4) = 10 words of length 4 over alphabet {a,b,c,d} are: aaaa, aaab, aaba, abaa, aabb, abab, aabc, abac, abca, abcd.
LINKS
Alois P. Heinz, Antidiagonals n = 0..80, flattened
Wikipedia, Young tableau
FORMULA
Conjecture: A(n,k) ~ k^n/Pi^(k/2) * (k/n)^(k*(k-1)/4) * Product_{j=1..k} Gamma(j/2). - Vaclav Kotesovec, Sep 12 2013
EXAMPLE
A(4,2) = 6, there are 6 standard Young tableaux of 4 cells and height <= 2:
+------+ +------+ +---------+ +---------+ +---------+ +------------+
| 1 3 | | 1 2 | | 1 3 4 | | 1 2 4 | | 1 2 3 | | 1 2 3 4 |
| 2 4 | | 3 4 | | 2 .-----+ | 3 .-----+ | 4 .-----+ +------------+
+------+ +------+ +---+ +---+ +---+
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, ...
0, 1, 1, 1, 1, 1, 1, 1, 1, ...
0, 1, 2, 2, 2, 2, 2, 2, 2, ...
0, 1, 3, 4, 4, 4, 4, 4, 4, ...
0, 1, 6, 9, 10, 10, 10, 10, 10, ...
0, 1, 10, 21, 25, 26, 26, 26, 26, ...
0, 1, 20, 51, 70, 75, 76, 76, 76, ...
0, 1, 35, 127, 196, 225, 231, 232, 232, ...
0, 1, 70, 323, 588, 715, 756, 763, 764, ...
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:
A:= (n, k)-> g(n, k, []):
seq(seq(A(n, d-n), n=0..d), d=0..15);
MATHEMATICA
h[l_List] := 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_List] := 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]]]]]];
a[n_, k_] := g[n, k, {}];
Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 06 2013, translated from Maple *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Apr 16 2012
STATUS
approved