A238125
Triangle read by rows: T(n,k) gives the number of ballot sequences of length n having exactly k flat steps, n>=0, 0<=k<=n.
Original entry on oeis.org
1, 1, 0, 1, 1, 0, 2, 1, 1, 0, 4, 3, 2, 1, 0, 9, 8, 6, 2, 1, 0, 22, 24, 17, 9, 3, 1, 0, 59, 70, 57, 29, 13, 3, 1, 0, 170, 224, 191, 108, 49, 17, 4, 1, 0, 516, 744, 663, 399, 201, 69, 23, 4, 1, 0, 1658, 2588, 2415, 1573, 802, 322, 104, 28, 5, 1, 0, 5583, 9317, 9108, 6249, 3343, 1408, 510, 137, 35, 5, 1, 0
Offset: 0
Triangle starts:
00: 1;
01: 1, 0;
02: 1, 1, 0;
03: 2, 1, 1, 0;
04: 4, 3, 2, 1, 0;
05: 9, 8, 6, 2, 1, 0;
06: 22, 24, 17, 9, 3, 1, 0;
07: 59, 70, 57, 29, 13, 3, 1, 0;
08: 170, 224, 191, 108, 49, 17, 4, 1, 0;
09: 516, 744, 663, 399, 201, 69, 23, 4, 1, 0;
10: 1658, 2588, 2415, 1573, 802, 322, 104, 28, 5, 1, 0;
11: 5583, 9317, 9108, 6249, 3343, 1408, 510, 137, 35, 5, 1, 0;
12: 19683, 34924, 35695, 25642, 14368, 6440, 2411, 751, 189, 42, 6, 1, 0;
...
-
b:= proc(n, v, l) option remember; `if`(n<1, 1, expand(
add(`if`(i=1 or l[i-1]>l[i], `if`(i=v, x, 1)*
b(n-1, i, subsop(i=l[i]+1, l)), 0), i=1..nops(l))+
b(n-1, nops(l)+1, [l[], 1])))
end:
T:= n-> seq(coeff(b(n-1, 1, [1]), x, i), i=0..n):
seq(T(n), n=0..12);
-
b[n_, v_, l_List] := b[n, v, l] = If[n<1, 1, Sum[If[i == 1 || l[[i-1]] > l[[i]], If[i == v, x, 1]*b[n-1, i, ReplacePart[l, i -> l[[i]]+1]], 0], {i, 1, Length[l]}] + b[n-1, Length[l]+1, Append[l, 1]]]; T[n_] := Table[Coefficient[b[n-1, 1, {1}], x, i], {i, 0, n}]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 07 2015, translated from Maple *)
A237770
Number of standard Young tableaux with n cells without a succession v, v+1 in a row.
Original entry on oeis.org
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
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.
A238126 (tableaux with one succession),
A238127 (two successions).
-
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 *)
A238127
Number of standard Young tableaux with n cells and exactly two successions.
Original entry on oeis.org
0, 0, 0, 1, 2, 6, 17, 57, 191, 663, 2415, 9108, 35695, 143989, 599802, 2566917, 11298164, 50967216, 235745644, 1115324000, 5397332497, 26669487517, 134528555379, 691856601631, 3626390958551, 19353306241764, 105122093620388, 580689432523534, 3260906342453966
Offset: 0
Showing 1-3 of 3 results.
Comments