A237770 Number of standard Young tableaux with n cells without a succession v, v+1 in a row.

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

Cf. A264051, A264078.

Sequence in context: A077003 A210726 A046917 * A187044 A193361 A294281

Adjacent sequences: A237767 A237768 A237769 * A237771 A237772 A237773

Keyword

nonn

Author

Joerg Arndt and Alois P. Heinz, Feb 13 2014

Status

approved