login
A104553
Sum of trapezoid weights of all Schroeder paths of length 2n.
2
1, 7, 38, 198, 1039, 5533, 29852, 162716, 893997, 4942723, 27466082, 153264066, 858230875, 4820155001, 27141345912, 153168964216, 866086326425, 4905744855359, 27830459812830, 158102366711550, 899290473825511, 5120997554408597, 29191620055374228, 166560724629655188
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.
LINKS
A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.
FORMULA
G.f.: (1-x-sqrt(1-6*x+x^2))/(2*(1-x)^2*sqrt(1-6*x+x^2)).
Recurrence: n*(2*n-3)*a(n) = 2*(8*n^2 - 15*n + 5)*a(n-1) - 2*(14*n^2 - 28*n + 11)*a(n-2) + 2*(8*n^2 - 17*n + 7)*a(n-3) - (n-2)*(2*n-1)*a(n-4). - Vaclav Kotesovec, Oct 24 2012
a(n) ~ sqrt(48+34*sqrt(2))*(3+2*sqrt(2))^n/(16*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 24 2012
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 - 6 x + x^2]) / x /(2 (1 - x)^2 Sqrt[1 - 6 x + x^2]), {x, 0, 30}], x] (* Harvey P. Dale, May 26 2011 *)
PROG
(PARI) x='x+O('x^66); Vec((1-x-sqrt(1-6*x+x^2))/(2*(1-x)^2*sqrt(1-6*x+x^2))) \\ Joerg Arndt, May 13 2013
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Mar 14 2005
EXTENSIONS
Typo in Mma program fixed by Vincenzo Librandi, May 13 2013
STATUS
approved