A238707 Number T(n,k) of ballot sequences of length n having difference k between the multiplicities of the smallest and the largest value; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
1, 1, 0, 2, 0, 0, 2, 2, 0, 0, 4, 3, 3, 0, 0, 2, 14, 6, 4, 0, 0, 12, 14, 35, 10, 5, 0, 0, 2, 69, 71, 69, 15, 6, 0, 0, 30, 97, 295, 195, 119, 21, 7, 0, 0, 44, 251, 751, 929, 421, 188, 28, 8, 0, 0, 86, 671, 2326, 3044, 2254, 791, 279, 36, 9, 0, 0, 2, 1847, 6524, 11824, 8999, 4696, 1354, 395, 45, 10, 0, 0
Offset: 0
Examples
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;
Links
- Joerg Arndt and Alois P. Heinz, Rows n = 0..67, flattened
- Wikipedia, Young tableau
Crossrefs
Programs
-
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 *)
Comments