|
%I #9 Apr 09 2013 10:58:37
%S 1,1,1,1,4,1,1,12,8,1,1,33,42,13,1,1,88,183,102,19,1,1,232,717,624,
%T 205,26,1,1,609,2622,3275,1650,366,34,1,1,1596,9134,15473,11020,3716,
%U 602,43,1,1,4180,30691,67684,64553,30520,7483,932,53,1,1,10945,100284,279106
%N Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n and having k up steps starting at even heights.
%C A Schroeder path of length 2n is a lattice path starting from (0,0), ending at (2n,0), consisting only of steps U=(1,1) (up steps), D=(1,-1) (down steps) and H=(2,0) (level steps) and never going below the x-axis (Schroeder paths are counted by the large Schroeder numbers, A006318). Also number of Schroeder paths of length 2n and having k humps. A hump is an up step U followed by 0 or more level steps H followed by a down step D. The T(3,2)=8 Schroeder paths of length 6 and having 2 humps are: H(UD)(UD), (UD)H(UD), (UD)(UD)H, (UD)(UHD), (UD)(UUDD), (UHD)(UD), (UUDD)(UD) and U(UD)(UD)D, the humps being shown between parentheses. Row sums are the large Schroeder numbers (A006318). Column 1 yields the odd-indexed Fibonacci numbers minus 1 (A027941). T(n,n-1)=A034856(n)=binomial(n + 1, 2) + n - 1.
%C Product A085478*A090181 (Morgan-Voyce times Narayana). [From _Paul Barry_, Jan 29 2009]
%F G.f.=G=G(t, z) satisfies z(1-z)G^2-(1-z-tz+z^2)G+1-z=0.
%F G.f.: 1/(1-x-xy/(1-x-x/(1-x-xy/(1-x-xy/(1-x-x/(1-x-xy/(1-.... (continued fraction). [From _Paul Barry_, Jan 29 2009]
%e T(3,2)=8 because we have HU'DU'D, U'DHU'D, U'DU'DH, U'DU'HD, U'DU'UDD, U'HDU'D, U'UDDU'D and U'UU'DDD, the up steps starting at an even height being shown with a prime sign.
%e Triangle begins:
%e 1;
%e 1,1;
%e 1,4,1;
%e 1,12,8,1;
%e 1,33,42,13,1;
%p G:=1/2/(-z+z^2)*(-1+z+t*z-z^2+sqrt(1-6*z-2*t*z+11*z^2+2*t*z^2-6*z^3+t^2*z^2-2*t*z^3+z^4)): Gser:=simplify(series(G,z=0,13)): P[0]:=1: for n from 1 to 11 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 11 do seq(coeff(t*P[n],t^k),k=1..n+1) od; # yields the sequence in triangular form
%Y Cf. A006318, A027941, A034856, A101920.
%K nonn,tabl
%O 0,5
%A _Emeric Deutsch_, Dec 20 2004
|
