OFFSET
1,1
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 (Schroeder paths are counted by the large Schroeder numbers (A006318)). Also number of Schroeder paths of length 2n and having k UU's. Also number of Schroeder paths of length 2n and having k peaks at height >1,
FORMULA
G.f.=G=G(t, z) satisfies z(t+z-tz)G^2-(1-2z+tz)G+1=0.
T(n,m) = Sum_{k=0..n-m} (k+1)*C(n-k,m-1)*C(2*n-m-k+1,n+1)/(n-k), m>1, T(n,1) = 1/(n+1)*binomial(2*n+2,n). - Vladimir Kruchinin, Oct 14 2020
EXAMPLE
T(3,1)=7 because we have HU(DU)D, U(DU)DH, U(DU)HD, UH(DU)D, U(DU)UDD,
UUD(DU)D and UU(DU)DD, the valleys being shown between parentheses.
Triangle begins:
2;
5,1;
14,7,1;
42,36,11,1;
132,165,80,16,1;
MAPLE
G := 1/2/(-t*z-z^2+z^2*t)*(-1+2*z-t*z+sqrt(1-4*z-2*t*z+t^2*z^2)):Gser:=simplify(series(G, z=0, 13)):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^k), k=1..n) od; # yields the sequence in triangular form
PROG
(Maxima)
T(n, m):=if n=0 or m=0 then 0 else if m=1 then 1/(n+1)*binomial(2*n+2, n) else sum(((k+1)*binomial(n-k, m-1)*binomial(2*n-m-k+1, n+1))/(n-k), k, 0, n-m); /* Vladimir Kruchinin, Oct 14 2020 */
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Dec 20 2004
STATUS
approved