|
| |
|
|
A104552
|
|
Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n having trapezoid weight k.
|
|
1
|
|
|
|
1, 1, 1, 1, 3, 2, 1, 8, 9, 4, 1, 21, 35, 25, 8, 1, 55, 128, 128, 66, 16, 1, 144, 448, 591, 422, 168, 32, 1, 377, 1515, 2537, 2350, 1298, 416, 64, 1, 987, 4984, 10304, 11897, 8481, 3796, 1008, 128, 1, 2584, 16032, 40057, 56083, 49448, 28557, 10680, 2400, 256, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
A Schroeder path is a lattice path starting from (0,0), ending at a point on the x-axis, consisting only of steps U=(1,1), D=(1,-1) and H=(2,0) and never going below the x-axis. Schroeder paths are counted by the large Schroeder numbers (A006318).
A trapezoid in a Schroeder path is a factor of the form U^i H^j D^i (i>=1, j>=0), i being the height of the trapezoid. A trapezoid in a Schroeder path w is maximal if, as a factor in w, it is not immediately preceded by a U and immediately followed by a D. The trapezoid weight of a Schroeder path is the sum of the heights of its maximal trapezoids. For example, in the Schroeder path w=UH(UHD)D(UUDD) we have two trapezoids (shown between parentheses) of heights 1 and 2, respectively. The trapezoid weight of w is 1+2=3.
This concept is an analogous to the concept of pyramid weight in a Dyck path (see the Denise-Simion paper). Row sums yield the large Schroeder numbers (A006318). Column 1 yields the even-subscripted Fibonacci numbers (A001906).
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.=G=G(t, z) satisfies zG^2-[1-z+z(1-t)/((1-z)(1-tz))]G+1=0.
|
|
|
EXAMPLE
|
Triangle begins:
1;
1,1;
1,3,2;
1,8,9,4;
1,21,35,25,8;
T(2,0)=1,T(2,1)=3, T(2,2)=2 because the six Schroeder paths of length 4, namely HH, (UD)H, H(UD), (UHD), (UD)(UD) and (UUDD) have trapezoid weights 0,1,1,1,2 and 2, respectively; the trapezoids are shown between parentheses.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
