cp's OEIS Frontend

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

%I A232439 #52 Feb 07 2017 10:16:48
%S A232439 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 A232439 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 A232439 1,1,1,2,4,7,10,16,22,30,37,46,52,60,62,64,62
%N A232439 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 A232439 Rows are symmetric.
%C A232439 The row beginnings converge to A003293.
%C A232439 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 A232439 Joerg Arndt and Alois P. Heinz, <a href="/A232439/b232439.txt">Rows n = 0..40, flattened</a>
%H A232439 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 A232439 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 A232439 Wikipedia, <a href="https://en.wikipedia.org/wiki/Young_tableau">Young tableau</a>
%e A232439 For n=4 the 10 tableaux sorted by major index (sum of descent set) are:
%e A232439 :[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 A232439 :         :[2]    :[3 4] [3]    :[2]   [4]    :[2]   [2 4]:[3]  :[2]:
%e A232439 :         :       :             :[3]          :[4]        :[4]  :[3]:
%e A232439 :         :       :             :             :           :     :[4]:
%e A232439 : ---0--- : --1-- : -----2----- : -----3----- : ----4---- : -5- : 6 :
%e A232439 Triangle T(n,k) begins:
%e A232439 1;
%e A232439 1;
%e A232439 1, 1;
%e A232439 1, 1, 1, 1;
%e A232439 1, 1, 2, 2, 2, 1,  1;
%e A232439 1, 1, 2, 3, 4, 4,  4,  3,  2,  1,  1;
%e A232439 1, 1, 2, 4, 5, 7,  9,  9,  9,  9,  7,  5,  4,  2,  1,  1;
%e A232439 1, 1, 2, 4, 6, 9, 13, 16, 19, 22, 23, 23, 22, 19, 16, 13, 9, 6, 4, 2, 1, 1;
%e A232439 The 10 ballot sequences of length 4 are:
%e A232439 ##   [ ballot seq] ascent positions  sum
%e A232439 01:  [ 1 1 1 1 ]   (none)            0
%e A232439 02:  [ 1 1 1 2 ]   3                 3
%e A232439 03:  [ 1 1 2 1 ]   2                 2
%e A232439 04:  [ 1 1 2 2 ]   2                 2
%e A232439 05:  [ 1 1 2 3 ]   2 + 3             5
%e A232439 06:  [ 1 2 1 1 ]   1                 1
%e A232439 07:  [ 1 2 1 2 ]   1 + 3             4
%e A232439 08:  [ 1 2 1 3 ]   1 + 3             4
%e A232439 09:  [ 1 2 3 1 ]   1 + 2             3
%e A232439 10:  [ 1 2 3 4 ]   1 + 2 + 3         6
%e A232439 The numbers 2, 3, and 4 appear twice, all others once, so the row four is  1, 1, 2, 2, 2, 1, 1.
%p A232439 b:= proc(l, i) option remember; `if`(l=[], 1, expand(add(
%p A232439       `if`(l[j]>`if`(j=1, 0, l[j-1]), `if`(j=1 and l[j]=1,
%p A232439        b(subsop(1=NULL, l), j-1), b(subsop(j=l[j]-1, l), j))*
%p A232439        x^`if`(j>i, add(t, t=l), 0), 0), j=1..nops(l))))
%p A232439     end:
%p A232439 g:= (n, i, l)-> `if`(n=0 or i=1, b([1$n, l[]], nops(l)+n),
%p A232439                  add(g(n-i*j, i-1, [i$j, l[]]), j=0..n/i)):
%p A232439 T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(g(n$2, [])):
%p A232439 seq(T(n), n=0..10);
%p A232439 # second Maple program (counting ballot sequences):
%p A232439 b:= proc(n, v, l) option remember; local w; w:=add(t, t=l);
%p A232439       `if`(n<1, 1, expand(add(`if`(i=1 or l[i-1]>l[i],
%p A232439       `if`(v<i, x^w, 1)*b(n-1, i, subsop(i=l[i]+1, l)), 0),
%p A232439        i=1..nops(l))+ x^w*b(n-1, nops(l)+1, [l[], 1])))
%p A232439     end:
%p A232439 T:= n->(p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n-1, 1, [1])):
%p A232439 seq(T(n), n=0..10);
%t A232439 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 A232439 Row sums give A000085.
%Y A232439 Cf. A000217, A003293, A225616, A247386.
%K A232439 nonn,tabf
%O A232439 0,11
%A A232439 _Joerg Arndt_ and _Alois P. Heinz_, Feb 23 2014