login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 15 22:19 EDT 2019. Contains 324145 sequences. (Running on oeis4.)