A101281 Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n and having k low humps.

1, 1, 1, 2, 3, 1, 8, 8, 5, 1, 36, 28, 18, 7, 1, 164, 120, 68, 32, 9, 1, 764, 552, 292, 136, 50, 11, 1, 3652, 2616, 1356, 608, 240, 72, 13, 1, 17852, 12680, 6532, 2880, 1140, 388, 98, 15, 1, 88868, 62664, 32156, 14128, 5572, 1976, 588, 128, 17, 1, 449004, 314744

Offset: 0

Author

Emeric Deutsch and Ira M. Gessel, Dec 20 2004

Keywords

• nonn
• tabl

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 x-axis. A hump is an up step U followed by 0 or more level steps H followed by a down step D. A low hump is a hump that starts at height zero. Schroeder paths are counted by the large Schroeder numbers (A006318). Row sums are the large Schroeder numbers (A006318). Column 0 yields A089387.

Examples

			T(3,2) = 5 because we have (UD)(UHD), (UHD)(UD), H(UD)(UD), (UD)H(UD) and (UD)(UD)H, the low humps being shown between parentheses.
Triangle begins:
1;
1,1;
2,3,1;
8,8,5,1;
36,28,18,7,1;
		

Crossrefs

Cf. A006318, A089387.

Programs

Maple

G:=(-1+z)*(-1+z+sqrt(1-6*z+z^2))/z/(3-3*z-sqrt(1-6*z+z^2) -t+t*z +t*sqrt(1-6*z+z^2)): Gser:=simplify(series(G,z=0,12)): P[0]:=1: for n from 1 to 10 do P[n]:=coeff(Gser,z^n) od: seq(seq(coeff(t*P[n],t^k), k=1..n+1), n=0..10);

Formula

G.f.: G(t, z)=(1-z)R/[1-z+(1-t)zR], where R=[1-z-sqrt(1-6z+z^2)]/(2z) is the g.f. of the large Schroeder numbers (A006318).