login
Number T(n,k) of standard Young tableaux with n cells and major index k; triangle T(n,k), n>=0, 0<=k<=n*(n-1)/2, read by rows.
3

%I #52 Feb 07 2017 10:16:48

%S 1,1,1,1,1,1,1,1,1,1,2,2,2,1,1,1,1,2,3,4,4,4,3,2,1,1,1,1,2,4,5,7,9,9,

%T 9,9,7,5,4,2,1,1,1,1,2,4,6,9,13,16,19,22,23,23,22,19,16,13,9,6,4,2,1,

%U 1,1,1,2,4,7,10,16,22,30,37,46,52,60,62,64,62

%N Number T(n,k) of standard Young tableaux with n cells and major index k; triangle T(n,k), n>=0, 0<=k<=n*(n-1)/2, read by rows.

%C Rows are symmetric.

%C The row beginnings converge to A003293.

%C T(n,k) is also the number of ballot sequences of length n with k the sum of positions of all ascents, see example.

%H Joerg Arndt and Alois P. Heinz, <a href="/A232439/b232439.txt">Rows n = 0..40, flattened</a>

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000009">The charge of the tableau</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000059">The inversion number of a standard Young tableau as defined by Haglund and Stevens</a>, <a href="http://www.findstat.org/St000169">The cocharge of a standard tableau</a>

%H James Haglund, <a href="https://www.math.upenn.edu/~jhaglund/books/qtcat.pdf">The q,t-Catalan Numbers and the Space of Diagonal Harmonics</a>, AMS University Lecture Series, vol. 41, 2008.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Young_tableau">Young tableau</a>

%e For n=4 the 10 tableaux sorted by major index (sum of descent set) are:

%e :[1 2 3 4]:[1 3 4]:[1 2] [1 2 4]:[1 4] [1 2 3]:[1 3] [1 3]:[1 2]:[1]:

%e : :[2] :[3 4] [3] :[2] [4] :[2] [2 4]:[3] :[2]:

%e : : : :[3] :[4] :[4] :[3]:

%e : : : : : : :[4]:

%e : ---0--- : --1-- : -----2----- : -----3----- : ----4---- : -5- : 6 :

%e Triangle T(n,k) begins:

%e 1;

%e 1;

%e 1, 1;

%e 1, 1, 1, 1;

%e 1, 1, 2, 2, 2, 1, 1;

%e 1, 1, 2, 3, 4, 4, 4, 3, 2, 1, 1;

%e 1, 1, 2, 4, 5, 7, 9, 9, 9, 9, 7, 5, 4, 2, 1, 1;

%e 1, 1, 2, 4, 6, 9, 13, 16, 19, 22, 23, 23, 22, 19, 16, 13, 9, 6, 4, 2, 1, 1;

%e The 10 ballot sequences of length 4 are:

%e ## [ ballot seq] ascent positions sum

%e 01: [ 1 1 1 1 ] (none) 0

%e 02: [ 1 1 1 2 ] 3 3

%e 03: [ 1 1 2 1 ] 2 2

%e 04: [ 1 1 2 2 ] 2 2

%e 05: [ 1 1 2 3 ] 2 + 3 5

%e 06: [ 1 2 1 1 ] 1 1

%e 07: [ 1 2 1 2 ] 1 + 3 4

%e 08: [ 1 2 1 3 ] 1 + 3 4

%e 09: [ 1 2 3 1 ] 1 + 2 3

%e 10: [ 1 2 3 4 ] 1 + 2 + 3 6

%e The numbers 2, 3, and 4 appear twice, all others once, so the row four is 1, 1, 2, 2, 2, 1, 1.

%p b:= proc(l, i) option remember; `if`(l=[], 1, expand(add(

%p `if`(l[j]>`if`(j=1, 0, l[j-1]), `if`(j=1 and l[j]=1,

%p b(subsop(1=NULL, l), j-1), b(subsop(j=l[j]-1, l), j))*

%p x^`if`(j>i, add(t, t=l), 0), 0), j=1..nops(l))))

%p end:

%p g:= (n, i, l)-> `if`(n=0 or i=1, b([1$n, l[]], nops(l)+n),

%p add(g(n-i*j, i-1, [i$j, l[]]), j=0..n/i)):

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(g(n$2, [])):

%p seq(T(n), n=0..10);

%p # second Maple program (counting ballot sequences):

%p b:= proc(n, v, l) option remember; local w; w:=add(t, t=l);

%p `if`(n<1, 1, expand(add(`if`(i=1 or l[i-1]>l[i],

%p `if`(v<i, x^w, 1)*b(n-1, i, subsop(i=l[i]+1, l)), 0),

%p i=1..nops(l))+ x^w*b(n-1, nops(l)+1, [l[], 1])))

%p end:

%p T:= n->(p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n-1, 1, [1])):

%p seq(T(n), n=0..10);

%t b[l_List, i_] := b[l, i] = If[l == {}, 1, Expand[Sum[ If[l[[j]] > If[j == 1, 0, l[[j-1]]], If[j == 1 && l[[j]] == 1, b[ReplacePart[l, 1 -> Sequence[]], j-1], b[ReplacePart[l, j -> l[[j]]-1], j]]*x^If[j>i, Total[l], 0], 0], {j, 1, Length[l]}]]] ; g[n_, i_, l_List] := g[n, i, l] = If[n == 0 || i == 1, b[Join[Array[1&, n], l], Length[l]+n], Sum[g[n-i*j, i-1, Join[Array[i&, j], l]], {j, 0, n/i}]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][g[n, n, {}]]; Table[T[n], {n, 0, 10}] // Flatten (* _Jean-François Alcover_, Jan 14 2015, translated from Maple *)

%Y Row sums give A000085.

%Y Cf. A000217, A003293, A225616, A247386.

%K nonn,tabf

%O 0,11

%A _Joerg Arndt_ and _Alois P. Heinz_, Feb 23 2014