cp's OEIS Frontend

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

%I A104552 #15 Dec 02 2014 16:58:09
%S A104552 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 A104552 422,168,32,1,377,1515,2537,2350,1298,416,64,1,987,4984,10304,11897,
%U A104552 8481,3796,1008,128,1,2584,16032,40057,56083,49448,28557,10680,2400,256,1
%N A104552 Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n having trapezoid weight k.
%C A104552 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 A104552 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 A104552 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 A104552 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 A104552 G.f.=G=G(t, z) satisfies zG^2-[1-z+z(1-t)/((1-z)(1-tz))]G+1=0.
%e A104552 Triangle begins:
%e A104552 1;
%e A104552 1,1;
%e A104552 1,3,2;
%e A104552 1,8,9,4;
%e A104552 1,21,35,25,8;
%e A104552 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 A104552 Cf. A006318, A001906, A104553.
%K A104552 nonn,tabl
%O A104552 0,5
%A A104552 _Emeric Deutsch_, Mar 14 2005
%E A104552 Keyword tabf changed to tabl by _Michel Marcus_, Apr 09 2013