A114706 Triangle read by rows: T(n,k) is the number of hill-free Schroeder paths of length 2n and having k ascents (n>=1; 0<=k<=n-1). A Schroeder path of length 2n is a lattice path from (0,0) to (2n,0) consisting of U=(1,1), D=(1,-1) and H=(2,0) steps and never going below the x-axis. A hill is a peak at height 1. An ascent in a Schroeder path is a maximal sequence of consecutive U steps.

1, 1, 2, 1, 8, 2, 1, 22, 20, 2, 1, 52, 106, 36, 2, 1, 114, 420, 310, 56, 2, 1, 240, 1410, 1840, 706, 80, 2, 1, 494, 4260, 8714, 5832, 1382, 108, 2, 1, 1004, 11978, 35484, 36898, 15100, 2442, 140, 2, 1, 2026, 31988, 129758, 194216, 122674, 34012, 4006, 176, 2, 1

Offset

1,3

Comments

Row sums are the little Schroeder numbers (A001003). Sum(k*T(n,k),k=0..n-1)=2*A049608(n-1).

Links

Table of n, a(n) for n=1..56.

Formula

G.f.=G-1, where G=G(t, z) satisfies z(1+t-z+tz)G^2-(1+tz)G+1=0.

Example

T(3,2)=2 because we have (U)H(U)DD and (UU)D(U)DD, where U=(1,1), D=(1,-1),
H=(2,0) (the ascents are shown between parentheses).
Triangle starts:
1;
1,2;
1,8,2;
1,22,20,2;

Maple

G:=(1+t*z-sqrt(1-2*t*z+t^2*z^2-4*z-4*z^2*t+4*z^2))/2/(z+t*z+z^2*t-z^2)-1: Gser:=simplify(series(G, z=0, 15)): for n from 1 to 11 do P[n]:=coeff(Gser, z^n) od: for n from 1 to 11 do seq(coeff(t*P[n], t^j), j=1..n) od; # yields sequence in triangular form

Crossrefs

Cf. A001003, A049608.

Sequence in context: A208921 A208660 A367024 * A046740 A317932 A253583

Adjacent sequences: A114703 A114704 A114705 * A114707 A114708 A114709

Keyword

nonn,tabl

Author

Emeric Deutsch, Dec 26 2005

Status

approved