OFFSET
0,4
COMMENTS
Also the number of standard Young tableaux (SYT) with n cells having difference k between the lengths of the first and the last row.
LINKS
Joerg Arndt and Alois P. Heinz, Rows n = 0..67, flattened
Wikipedia, Young tableau
EXAMPLE
For n=4 the 10 ballot sequences of length 4 and differences between the multiplicities of the smallest and the largest value are:
[1, 2, 3, 4] -> 1-1 = 0,
[1, 1, 2, 2] -> 2-2 = 0,
[1, 2, 1, 2] -> 2-2 = 0,
[1, 1, 1, 1] -> 4-4 = 0,
[1, 1, 2, 3] -> 2-1 = 1,
[1, 2, 1, 3] -> 2-1 = 1,
[1, 2, 3, 1] -> 2-1 = 1,
[1, 1, 1, 2] -> 3-1 = 2,
[1, 1, 2, 1] -> 3-1 = 2,
[1, 2, 1, 1] -> 3-1 = 2,
thus row 4 = [4, 3, 3, 0, 0].
The 10 tableaux with 4 cells sorted by the difference between the lengths of the first and the last row are:
:[1] [1 2] [1 3] [1 2 3 4]:[1 2] [1 3] [1 4]:[1 2 3] [1 2 4] [1 3 4]:
:[2] [3 4] [2 4] :[3] [2] [2] :[4] [3] [2] :
:[3] :[4] [4] [3] : :
:[4] : : :
: -----------0----------- : -------1------- : ----------2---------- :
Triangle T(n,k) begins:
00: 1;
01: 1, 0;
02: 2, 0, 0;
03: 2, 2, 0, 0;
04: 4, 3, 3, 0, 0;
05: 2, 14, 6, 4, 0, 0;
06: 12, 14, 35, 10, 5, 0, 0;
07: 2, 69, 71, 69, 15, 6, 0, 0;
08: 30, 97, 295, 195, 119, 21, 7, 0, 0;
09: 44, 251, 751, 929, 421, 188, 28, 8, 0, 0;
10: 86, 671, 2326, 3044, 2254, 791, 279, 36, 9, 0, 0;
MAPLE
b:= proc(n, l) option remember; `if`(n<1, x^(l[1]-l[-1]),
expand(b(n-1, [l[], 1])+add(`if`(i=1 or l[i-1]>l[i],
b(n-1, subsop(i=l[i]+1, l)), 0), i=1..nops(l))))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n-1, [1])):
seq(T(n), n=0..12);
# second Maple program (counting SYT):
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) `if`(n=0 or i=1, (p->h(p)*x^(`if`(p=[], 0, p[1]-
p[-1])))([l[], 1$n]), add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))
end:
T:= n->(p-> seq(coeff(p, x, i), i=0..n))(g(n, n, [])):
seq(T(n), n=0..12);
MATHEMATICA
b[n_, l_List] := b[n, l] = If[n<1, x^(l[[1]] - l[[-1]]), Expand[b[n-1, Append[l, 1]] + Sum[If[i == 1 || l[[i-1]] > l[[i]], b[n-1, ReplacePart[l, i -> l[[i]]+1]], 0], {i, 1, Length[l]}]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, n}]][b[n-1, {1}]]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 07 2015, translated from Maple *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Joerg Arndt and Alois P. Heinz, Mar 03 2014
STATUS
approved