A114692 - OEIS

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.

%I #5 Mar 30 2012 17:36:07

%S 1,1,1,2,1,10,1,40,4,1,160,36,1,674,220,8,1,2994,1180,104,1,13872,

%T 6056,848,16,1,66336,30760,5680,272,1,324898,156632,34528,2768,32,1,

%U 1621178,803096,199552,22224,672,1,8210904,4150444,1122736,156528,8192,64,1

%N 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.

%C 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).

%F 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).

%e 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).

%e Triangle starts:

%e 1;

%e 1,2;

%e 1,10;

%e 1,40,4;

%e 1,160,36;

%p 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

%Y Cf. A001003, A114693.

%K nonn,tabf

%O 0,4

%A _Emeric Deutsch_, Dec 26 2005