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

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, 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, 4748, 3088, 1168, 350, 99, 29, 9, 3, 1, 1, 0, 17848, 11644, 4404, 1302, 356, 99, 29, 9, 3, 1, 1

Offset: 0

Author

Joerg Arndt and Alois P. Heinz, Mar 05 2014

Keywords

• nonn
• tabl

Comments

T(0,0) = 1 by convention.

Also the number of ballot sequences of length n with exactly k fixed points. The fixed points are in the positions 1,2,...,k.

Row sums give A000085.

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

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

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

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

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

Examples

			The 10 tableaux with n=4 cells sorted by the length of the maximal consecutive sequence 1,2,...,k in the first column are:
:[1 2] [1 2] [1 2 3] [1 2 4] [1 2 3 4]:[1 3] [1 3] [1 3 4]:[1 4]:[1]:
:[3]   [3 4] [4]     [3]              :[2]   [2 4] [2]    :[2]  :[2]:
:[4]                                  :[4]                :[3]  :[3]:
:                                     :                   :     :[4]:
: -----------------1----------------- : --------2-------- : -3- : 4 :
Their corresponding ballot sequences are:
[1, 1, 2, 3]  ->  1 \
[1, 1, 2, 2]  ->  1  \
[1, 1, 1, 2]  ->  1   } -- 5
[1, 1, 2, 1]  ->  1  /
[1, 1, 1, 1]  ->  1 /
[1, 2, 1, 3]  ->  2 \
[1, 2, 1, 2]  ->  2  } --- 3
[1, 2, 1, 1]  ->  2 /
[1, 2, 3, 1]  ->  3 } ---- 1
[1, 2, 3, 4]  ->  4 } ---- 1
Thus row 4 = [0, 5, 3, 1, 1].
Triangle T(n,k) begins:
00:   1;
01:   0,    1;
02:   0,    1,    1;
03:   0,    2,    1,    1;
04:   0,    5,    3,    1,   1;
05:   0,   13,    8,    3,   1,  1;
06:   0,   38,   24,    9,   3,  1,  1;
07:   0,  116,   74,   28,   9,  3,  1,  1;
08:   0,  382,  246,   93,  29,  9,  3,  1,  1;
09:   0, 1310,  848,  321,  98, 29,  9,  3,  1,  1;
10:   0, 4748, 3088, 1168, 350, 99, 29,  9,  3,  1,  1;
		

Links

• Joerg Arndt and Alois P. Heinz, Rows n = 0..50, flattened
• Wikipedia, Young tableau

Programs

Maple

b:= proc(n, l) option remember; `if`(n=0, 1,
       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, k)-> `if`(n=k, 1, `if`(k=0, 0, b(n-k-1, [2, 1$(k-1)]))):
seq(seq(T(n, k), k=0..n), n=0..14);

Mathematica

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 *)