A104552 - OEIS

%I #15 Dec 02 2014 16:58:09

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

%T 422,168,32,1,377,1515,2537,2350,1298,416,64,1,987,4984,10304,11897,

%U 8481,3796,1008,128,1,2584,16032,40057,56083,49448,28557,10680,2400,256,1

%N Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n having trapezoid weight k.

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

%C 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.

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

%H A. Denise and R. Simion, <a href="http://dx.doi.org/10.1016/0012-365X(93)E0147-V">Two combinatorial statistics on Dyck paths</a>, Discrete Math., 137, 1995, 155-176.

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

%e Triangle begins:

%e 1;

%e 1,1;

%e 1,3,2;

%e 1,8,9,4;

%e 1,21,35,25,8;

%e 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.

%Y Cf. A006318, A001906, A104553.

%K nonn,tabl

%O 0,5

%A _Emeric Deutsch_, Mar 14 2005

%E Keyword tabf changed to tabl by _Michel Marcus_, Apr 09 2013