A182172 Number A(n,k) of standard Young tableaux of n cells and height <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 4, 6, 1, 0, 1, 1, 2, 4, 9, 10, 1, 0, 1, 1, 2, 4, 10, 21, 20, 1, 0, 1, 1, 2, 4, 10, 25, 51, 35, 1, 0, 1, 1, 2, 4, 10, 26, 70, 127, 70, 1, 0, 1, 1, 2, 4, 10, 26, 75, 196, 323, 126, 1, 0, 1, 1, 2, 4, 10, 26, 76, 225, 588, 835, 252, 1, 0

Offset: 0

Author

Alois P. Heinz, Apr 16 2012

Keywords

• nonn
• tabl

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.

Examples

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

Links

• Alois P. Heinz, Antidiagonals n = 0..80, flattened
• Wikipedia, Young tableau

Crossrefs

Columns k=0-12 give: A000007, A000012, A001405, A001006, A005817, A049401, A007579, A007578, A007580, A212915, A212916, A229053, A229068.

Main diagonal gives A000085.

A(2n,n) gives A293128.

Cf. A047884, A049400, A226873, A240608.

Programs

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 *)

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