login
Number T(n,k) of standard Young tableaux with n cells where k is the length of the maximal consecutive sequence 1,2,...,k in the first column; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
9

%I #37 Feb 06 2017 17:57:06

%S 1,0,1,0,1,1,0,2,1,1,0,5,3,1,1,0,13,8,3,1,1,0,38,24,9,3,1,1,0,116,74,

%T 28,9,3,1,1,0,382,246,93,29,9,3,1,1,0,1310,848,321,98,29,9,3,1,1,0,

%U 4748,3088,1168,350,99,29,9,3,1,1,0,17848,11644,4404,1302,356,99,29,9,3,1,1

%N Number T(n,k) of standard Young tableaux with n cells where k is the length of the maximal consecutive sequence 1,2,...,k in the first column; 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 with exactly k fixed points. The fixed points are in the positions 1,2,...,k.

%C Row sums give A000085.

%C Diagonal T(2n,n) gives A238803(n).

%C Diagonal T(2n+1,n) gives A238803(n+1)-1.

%C T(n,1) = Sum_{k=2..n} T(n,k) = A000085(n)/2 = A001475(n-1) for n>1.

%C Columns k=2-8 give: A238977, A238978, A238979, A239116, A239117, A239118, A239119.

%C Conjecture: Generally, column k is asymptotic to sqrt(2)/(2*(k+1)*(k-1)!) * exp(sqrt(n)-n/2-1/4) * n^(n/2) * (1 + 7/(24*sqrt(n))), holds for all k<=10. - _Vaclav Kotesovec_, Mar 08 2014

%H Joerg Arndt and Alois P. Heinz, <a href="/A238802/b238802.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 the length of the maximal consecutive sequence 1,2,...,k in the first column are:

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

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

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

%e : : : :[4]:

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

%e Their corresponding ballot sequences are:

%e [1, 1, 2, 3] -> 1 \

%e [1, 1, 2, 2] -> 1 \

%e [1, 1, 1, 2] -> 1 } -- 5

%e [1, 1, 2, 1] -> 1 /

%e [1, 1, 1, 1] -> 1 /

%e [1, 2, 1, 3] -> 2 \

%e [1, 2, 1, 2] -> 2 } --- 3

%e [1, 2, 1, 1] -> 2 /

%e [1, 2, 3, 1] -> 3 } ---- 1

%e [1, 2, 3, 4] -> 4 } ---- 1

%e Thus row 4 = [0, 5, 3, 1, 1].

%e Triangle T(n,k) begins:

%e 00: 1;

%e 01: 0, 1;

%e 02: 0, 1, 1;

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

%e 04: 0, 5, 3, 1, 1;

%e 05: 0, 13, 8, 3, 1, 1;

%e 06: 0, 38, 24, 9, 3, 1, 1;

%e 07: 0, 116, 74, 28, 9, 3, 1, 1;

%e 08: 0, 382, 246, 93, 29, 9, 3, 1, 1;

%e 09: 0, 1310, 848, 321, 98, 29, 9, 3, 1, 1;

%e 10: 0, 4748, 3088, 1168, 350, 99, 29, 9, 3, 1, 1;

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

%p b(n-1, [l[], 1]) +add(`if`(i=1 or l[i-1]>l[i],

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

%p end:

%p T:= (n, k)-> `if`(n=k, 1, `if`(k=0, 0, b(n-k-1, [2, 1$(k-1)]))):

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

%t b[n_, l_] := b[n, l] = If[n == 0, 1, 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_, k_] := If[n == k, 1, If[k == 0, 0, b[n-k-1, Join[{2}, Table[1, {k-1}]]]]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 14}] // Flatten (* _Jean-François Alcover_, Jan 06 2015, translated from Maple *)

%K nonn,tabl

%O 0,8

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