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