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
Examples
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;
Programs
-
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
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).
Comments