A114692 Triangle read by rows: T(n,k) is the number of hill-free Schroeder paths of length 2n that have k returns to the x-axis (0<=k<=floor(n/2)). 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.

1, 1, 1, 2, 1, 10, 1, 40, 4, 1, 160, 36, 1, 674, 220, 8, 1, 2994, 1180, 104, 1, 13872, 6056, 848, 16, 1, 66336, 30760, 5680, 272, 1, 324898, 156632, 34528, 2768, 32, 1, 1621178, 803096, 199552, 22224, 672, 1, 8210904, 4150444, 1122736, 156528, 8192, 64, 1

Offset

0,4

Comments

Row n contains 1+floor(n/2) terms. Row sums are the little Schroeder numbers (A001003). Sum(k*T(n,k),k=0..floor(n/2))=A114693(n-2).

Links

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

Formula

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

Example

T(4,2)=4 because we have UUD(D)UUD(D),UUD(D)UH(D),UH(D)UUD(D) and UH(D)UH(D), where U=(1,1), D=(1,-1) and H=(2,0) (the returns to the x-axis are shown between parentheses).
Triangle starts:
1;
1;
1,2;
1,10;
1,40,4;
1,160,36;

Maple

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

Crossrefs

Cf. A001003, A114693.

Sequence in context: A055633 A105606 A132995 * A112691 A110169 A144274

Adjacent sequences: A114689 A114690 A114691 * A114693 A114694 A114695

Keyword

nonn,tabf

Author

Emeric Deutsch, Dec 26 2005

Status

approved