|
| |
|
|
A104553
|
|
Sum of trapezoid weights of all Schroeder paths of length 2n.
|
|
1
| |
|
|
1, 7, 38, 198, 1039, 5533, 29852, 162716, 893997, 4942723, 27466082, 153264066, 858230875, 4820155001, 27141345912, 153168964216, 866086326425, 4905744855359, 27830459812830, 158102366711550, 899290473825511
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
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). Partial sums of A047665 which, in turn, are the partial sums of A002002.
|
|
|
REFERENCES
| A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176).
|
|
|
FORMULA
| G.f.=[1-z-sqrt(1-6z+z^2)]/[2(1-z)^2*sqrt(1-6z+z^2)]
|
|
|
EXAMPLE
| a(2)=7 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 maximal trapezoids are shown between parentheses.
|
|
|
MAPLE
| G:=(1-z-sqrt(1-6*z+z^2))/2/(1-z)^2/sqrt(1-6*z+z^2):Gser:=series(G, z=0, 28): seq(coeff(Gser, z^n), n=1..25);
|
|
|
MATHEMATICA
| CoefficientList[Series[(1-x-Sqrt[1-6x+x^2])/(2(1-x)^2Sqrt[1-6x+x^2]), {x, 0, 30}], x] (* From Harvey P. Dale, May 26 2011 *)
|
|
|
CROSSREFS
| Cf. A006318, A047665, A002002, A104552.
Sequence in context: A141845 A048437 A099461 * A027241 A056197 A158576
Adjacent sequences: A104550 A104551 A104552 * A104554 A104555 A104556
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 14 2005
|
| |
|
|
