login
A237770
Number of standard Young tableaux with n cells without a succession v, v+1 in a row.
9
1, 1, 1, 2, 4, 9, 22, 59, 170, 516, 1658, 5583, 19683, 72162, 274796, 1082439, 4406706, 18484332, 79818616, 353995743, 1611041726, 7510754022, 35842380314, 174850257639, 871343536591, 4430997592209, 22978251206350, 121410382810005, 653225968918521
OFFSET
0,4
COMMENTS
A standard Young tableau (SYT) without a succession v, v+1 in a row is called a nonconsecutive tableau.
Also the number of ballot sequences without two consecutive elements equal. A ballot sequence B is a string such that, for all prefixes P of B, h(i)>=h(j) for i<j, where h(x) is the number of times x appears in P (see A000085).
First column (k=0) of A238125.
LINKS
Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..68 (terms 0..48 from Alois P. Heinz)
Timothy Y. Chow, Henrik Eriksson and C. Kenneth Fan, Chess Tableaux, The Electronic Journal of Combinatorics, vol.11, no.2, (2005).
S. Dulucq and O. Guibert, Stack words, standard tableaux and Baxter permutations, Disc. Math. 157 (1996), 91-106.
Wikipedia, Young tableau
FORMULA
a(n) = Sum_{k=1..A264078(n)} k * A264051(n,k). - Alois P. Heinz, Nov 02 2015
EXAMPLE
The a(5) = 9 such tableaux of 5 are:
[1] [2] [3] [4] [5] [6] [7] [8] [9]
135 13 135 13 13 14 14 15 1
24 24 2 25 2 25 2 2 2
5 4 4 4 3 3 3 3
5 5 4 4
5
The corresponding ballot sequences are:
1: [ 0 1 0 1 0 ]
2: [ 0 1 0 1 2 ]
3: [ 0 1 0 2 0 ]
4: [ 0 1 0 2 1 ]
5: [ 0 1 0 2 3 ]
6: [ 0 1 2 0 1 ]
7: [ 0 1 2 0 3 ]
8: [ 0 1 2 3 0 ]
9: [ 0 1 2 3 4 ]
MAPLE
h:= proc(l, j) option remember; `if`(l=[], 1,
`if`(l[1]=0, h(subsop(1=[][], l), j-1), add(
`if`(i<>j and l[i]>0 and (i=1 or l[i]>l[i-1]),
h(subsop(i=l[i]-1, l), i), 0), i=1..nops(l))))
end:
g:= proc(n, i, l) `if`(n=0 or i=1, h([1$n, l[]], 0),
`if`(i<1, 0, g(n, i-1, l)+
`if`(i>n, 0, g(n-i, i, [i, l[]]))))
end:
a:= n-> g(n, n, []):
seq(a(n), n=0..30);
# second Maple program (counting ballot sequences):
b:= proc(n, v, l) option remember;
`if`(n<1, 1, add(`if`(i<>v and (i=1 or l[i-1]>l[i]),
b(n-1, i, subsop(i=l[i]+1, l)), 0), i=1..nops(l))+
b(n-1, nops(l)+1, [l[], 1]))
end:
a:= proc(n) option remember; forget(b); b(n-1, 1, [1]) end:
seq(a(n), n=0..30);
MATHEMATICA
b[n_, v_, l_List] := b[n, v, l] = If[n<1, 1, Sum[If[i != v && (i == 1 || l[[i-1]] > l[[i]]), b[n-1, i, ReplacePart[l, i -> l[[i]]+1]], 0], {i, 1, Length[l]}] + b[n-1, Length[l]+1, Append[l, 1]]]; a[n_] := a[n] = b[n-1, 1, {1}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 06 2015, translated from 2nd Maple program *)
CROSSREFS
Cf. A000085 (all Young tableaux), A000957, A001181, A214021, A214087, A214159, A214875.
Cf. A238126 (tableaux with one succession), A238127 (two successions).
Sequence in context: A077003 A210726 A046917 * A187044 A193361 A294281
KEYWORD
nonn
AUTHOR
Joerg Arndt and Alois P. Heinz, Feb 13 2014
STATUS
approved