A214875 -id:A214875 - cp's OEIS frontend

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

Joerg Arndt and Alois P. Heinz, Feb 13 2014

nonn

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 iA000085).
First column (k=0) of A238125.

			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 ]

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

Cf. A000085 (all Young tableaux), A000957, A001181, A214021, A214087, A214159, A214875.
Cf. A238126 (tableaux with one succession), A238127 (two successions).
Cf. A264051, A264078.

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

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

a(n) = Sum_{k=1..A264078(n)} k * A264051(n,k). - Alois P. Heinz, Nov 02 2015

A214021 Number A(n,k) of n X k nonconsecutive tableaux; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 2, 1, 1, 1, 0, 1, 6, 6, 1, 1, 1, 0, 1, 22, 72, 18, 1, 1, 1, 0, 1, 92, 1289, 960, 57, 1, 1, 1, 0, 1, 422, 29889, 93964, 14257, 186, 1, 1, 1, 0, 1, 2074, 831174, 13652068, 8203915, 228738, 622, 1, 1

Offset: 0

Alois P. Heinz, Jul 01 2012

A standard Young tableau (SYT) where entries i and i+1 never appear in the same row is called a nonconsecutive tableau.

			A(2,4) = 1:
  [1 3 5 7]
  [2 4 6 8].
A(4,2) = 6:
  [1, 5]   [1, 4]   [1, 3]   [1, 4]   [1, 3]   [1, 3]
  [2, 6]   [2, 6]   [2, 6]   [2, 5]   [2, 5]   [2, 4]
  [3, 7]   [3, 7]   [4, 7]   [3, 7]   [4, 7]   [5, 7]
  [4, 8]   [5, 8]   [5, 8]   [6, 8]   [6, 8]   [6, 8].
Square array A(n,k) begins:
  1, 1,  1,     1,       1,          1,              1, ...
  1, 1,  0,     0,       0,          0,              0, ...
  1, 1,  1,     1,       1,          1,              1, ...
  1, 1,  2,     6,      22,         92,            422, ...
  1, 1,  6,    72,    1289,      29889,         831174, ...
  1, 1, 18,   960,   93964,   13652068,     2621897048, ...
  1, 1, 57, 14257, 8203915, 8134044455, 11865331748843, ...

Alois P. Heinz, Antidiagonals n = 0..23, flattened
T. Y. Chow, H. Eriksson and C. K. Fan, Chess tableaux, Elect. J. Combin., 11 (2) (2005), #A3.
S. Dulucq and O. Guibert, Stack words, standard tableaux and Baxter permutations, Disc. Math. 157 (1996), 91-106.
Wikipedia, Young tableau

Rows n=0+2, 3-4 give: A000012, A001181(k) for k>0, A214875.
Columns k=0+1, 2, 3 give: A000012, A000957(n+1), A214159.
Main diagonal gives A264103.
Cf. A214020, A214088.

b:= proc(l, t) option remember; local n, s; n, s:= nops(l),
       add(i, i=l); `if`(s=0, 1, add(`if`(t<>i and l[i]>
      `if`(i=n, 0, l[i+1]), b(subsop(i=l[i]-1, l), i), 0), i=1..n))
    end:
A:= (n, k)-> `if`(n<1 or k<1, 1, b([k$n], 0)):
seq(seq(A(n, d-n), n=0..d), d=0..12);

b[l_, t_] := b[l, t] = Module[{n, s}, {n, s} = {Length[l], Sum[i, {i, l}]}; If[s == 0, 1, Sum[If[t != i && l[[i]] > If[i == n, 0, l[[i+1]]], b[ReplacePart[l, i -> l[[i]]-1], i], 0], {i, 1, n}]] ] ; a[n_, k_] := If[n < 1 || k < 1, 1, b[Array[k&, n], 0]]; Table[Table[a[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Dec 09 2013, translated from Maple *)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula