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

Author

Emeric Deutsch, Mar 14 2005

Keywords

• nonn
• tabl

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).

Examples

			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.
		

Links

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

Crossrefs

Cf. A006318, A001906, A104553.

Formula

G.f.=G=G(t, z) satisfies zG^2-[1-z+z(1-t)/((1-z)(1-tz))]G+1=0.

Extensions

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