Search: a214159 -id:a214159
|
| |
|
|
A237770
|
|
Number of standard Young tableaux with n cells without a succession v, v+1 in a row.
|
|
+10
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).
|
|
|
LINKS
|
Timothy Y. Chow, Henrik Eriksson and C. Kenneth Fan, Chess Tableaux, The Electronic Journal of Combinatorics, vol.11, no.2, (2005).
|
|
|
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
|
Cf. A238126 (tableaux with one succession), A238127 (two successions).
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A214021
|
|
Number A(n,k) of n X k nonconsecutive tableaux; square array A(n,k), n>=0, k>=0, read by antidiagonals.
|
|
+10
7
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,19
|
|
|
COMMENTS
|
A standard Young tableau (SYT) where entries i and i+1 never appear in the same row is called a nonconsecutive tableau.
|
|
|
LINKS
|
T. Y. Chow, H. Eriksson and C. K. Fan, Chess tableaux, Elect. J. Combin., 11 (2) (2005), #A3.
|
|
|
EXAMPLE
|
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, ...
|
|
|
MAPLE
|
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);
|
|
|
MATHEMATICA
|
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.007 seconds
|
