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,8

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

Links

Joerg Arndt and Alois P. Heinz, Rows n = 0..50, flattened

Wikipedia, Young tableau

Example

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;

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

Crossrefs

Sequence in context: A077875 A198237 A122049 * A229892 A064879 A173591

Adjacent sequences: A238799 A238800 A238801 * A238803 A238804 A238805

Keyword

nonn,tabl

Author

Joerg Arndt and Alois P. Heinz, Mar 05 2014

Status

approved