

A101919


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.


1



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, 205, 26, 1, 1, 609, 2622, 3275, 1650, 366, 34, 1, 1, 1596, 9134, 15473, 11020, 3716, 602, 43, 1, 1, 4180, 30691, 67684, 64553, 30520, 7483, 932, 53, 1, 1, 10945, 100284, 279106
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

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 xaxis (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 oddindexed Fibonacci numbers minus 1 (A027941). T(n,n1)=A034856(n)=binomial(n + 1, 2) + n  1.
Product A085478*A090181 (MorganVoyce times Narayana). [From Paul Barry, Jan 29 2009]


LINKS

Table of n, a(n) for n=0..58.


FORMULA

G.f.=G=G(t, z) satisfies z(1z)G^2(1ztz+z^2)G+1z=0.
G.f.: 1/(1xxy/(1xx/(1xxy/(1xxy/(1xx/(1xxy/(1.... (continued fraction). [From Paul Barry, Jan 29 2009]


EXAMPLE

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.
Triangle begins:
1;
1,1;
1,4,1;
1,12,8,1;
1,33,42,13,1;


MAPLE

G:=1/2/(z+z^2)*(1+z+t*zz^2+sqrt(16*z2*t*z+11*z^2+2*t*z^26*z^3+t^2*z^22*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


CROSSREFS

Cf. A006318, A027941, A034856, A101920.
Sequence in context: A156049 A192015 A205946 * A055106 A154372 A080416
Adjacent sequences: A101916 A101917 A101918 * A101920 A101921 A101922


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Dec 20 2004


STATUS

approved



