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, 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

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

Table of n, a(n) for n=0..55.

A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.

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

Cf. A006318, A001906, A104553.

Sequence in context: A198498 A016648 A366133 * A210803 A204144 A203992

Adjacent sequences: A104549 A104550 A104551 * A104553 A104554 A104555

Keyword

nonn,tabl

Author

Emeric Deutsch, Mar 14 2005

Extensions

Keyword tabf changed to tabl by Michel Marcus, Apr 09 2013

Status

approved