login
Number T(n,k) of standard Young tableaux with n cells and k as last value in the first row; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
10

%I #24 Feb 06 2017 18:13:08

%S 1,0,1,0,1,1,0,1,1,2,0,1,2,3,4,0,1,3,5,7,10,0,1,6,10,14,19,26,0,1,10,

%T 19,29,41,56,76,0,1,20,41,66,96,132,176,232,0,1,35,86,152,232,327,441,

%U 582,764,0,1,70,197,374,596,863,1181,1563,2031,2620

%N Number T(n,k) of standard Young tableaux with n cells and k as last value in the first row; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

%C T(0,0) = 1 by convention.

%C Also the number of ballot sequences of length n where k is the position of the last occurrence of the minimal value.

%C Diagonal: T(n,n) = A000085(n-1) for n>=1.

%C Columns k=0-10 give: A000007, A000012 for n>0, A001405(n-2) for n>1, A245001, A245002, A245003, A245004, A245005, A245006, A245007, A245008.

%C T(2n,n) gives A245000.

%C Row sums give A000085.

%H Joerg Arndt and Alois P. Heinz, <a href="/A238794/b238794.txt">Rows n = 0..50, flattened</a>

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

%e The 10 tableaux with n=4 cells sorted by last value in the first row:

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

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

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

%e :[4]: : : :

%e : 1 : ----2---- : --------3-------- : --------------4-------------- :

%e Their corresponding ballot sequences are: [1,2,3,4], [1,1,2,3], [1,1,2,2], [1,2,1,3], [1,2,1,2], [1,1,1,2], [1,2,3,1], [1,1,2,1], [1,2,1,1], [1,1,1,1]. Thus row 4 = [0, 1, 2, 3, 4].

%e Triangle T(n,k) begins:

%e 00: 1;

%e 01: 0, 1;

%e 02: 0, 1, 1;

%e 03: 0, 1, 1, 2;

%e 04: 0, 1, 2, 3, 4;

%e 05: 0, 1, 3, 5, 7, 10;

%e 06: 0, 1, 6, 10, 14, 19, 26;

%e 07: 0, 1, 10, 19, 29, 41, 56, 76;

%e 08: 0, 1, 20, 41, 66, 96, 132, 176, 232;

%e 09: 0, 1, 35, 86, 152, 232, 327, 441, 582, 764;

%e 10: 0, 1, 70, 197, 374, 596, 863, 1181, 1563, 2031, 2620;

%p b:= proc(n, l) option remember; `if`(n=0, 1, add(`if`(

%p i=1 or l[i-1]>l[i], b(n-1, subsop(i=l[i]+1, l)), 0),

%p i=1..nops(l)) +(p-> p+(x^(1+add(j, j=l))-1)*

%p coeff(p, x, 0))(b(n-1, [l[], 1])))

%p end:

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

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

%t b[n_, l_List] := b[n, l] = If[n == 0, 1, Sum[If[i == 1 || l[[i-1]] > l[[i]], b[n-1, ReplacePart[l, i -> l[[i]]+1]], 0], {i, 1, Length[l]}] + Function[{p}, p + (x^(1+Total[l])-1)*Coefficient[p, x, 0]][b[n-1, Append[l, 1]]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, {}]]; Table[T[n], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Jan 13 2015, translated from Maple *)

%K nonn,tabl

%O 0,10

%A _Joerg Arndt_ and _Alois P. Heinz_, Mar 05 2014