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
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
KEYWORD
nonn
AUTHOR
Joerg Arndt and Alois P. Heinz, Feb 13 2014
STATUS
approved