login
A110220
Triangle read by rows: T(n,k) (0 <= k <= floor(n/2)) is the number of lattice paths from (0,0) to (2n,0) consisting of steps U=(1,1), D=(1,-1), H=(2,0), never going below the x-axis (i.e., Schroeder paths) and having k UH's.
1
1, 2, 5, 1, 15, 7, 51, 37, 2, 188, 181, 25, 731, 866, 204, 5, 2950, 4124, 1393, 91, 12235, 19657, 8672, 1008, 14, 51822, 93937, 51147, 8856, 336, 223191, 450220, 291470, 68085, 4710, 42, 974427, 2163910, 1622665, 480535, 50655, 1254, 4302645
OFFSET
0,2
COMMENTS
Row n has 1 + floor(n/2) terms.
Row sums yield the large Schroeder numbers (A006318).
FORMULA
T(n,0) = A007317(n+1).
Sum_{k=0..floor(n/2)} k*T(n,k) = A026002(n-1) for n >= 2.
T(2n,n) = Cat(n) (the n-th Catalan number, A000108).
G.f.: (1 - z - sqrt(1 - 6z + 5z^2 - 4tz^2))/(2z(1 - z + tz)).
T(n,k) = binomial(n+1,k)*Sum_{j=0..n-2k} (binomial(n+1-k, k+j+1)*binomial(2j+2k, j))/(n+1). - Emeric Deutsch, Feb 28 2007
EXAMPLE
T(3,1)=7 because we have HUHD, UHDH, UHDUD, UHHD, UHUDD, UUHDD and UDUHD.
Triangle starts:
1;
2;
5, 1;
15, 7;
51, 37, 2;
188, 181, 25;
MAPLE
G:=(1-z-sqrt(1-6*z+5*z^2-4*z^2*t))/2/z/(1-z+t*z): Gser:=simplify(series(G, z=0, 15)): P[0]:=1: for n from 1 to 12 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 12 do seq(coeff(t*P[n], t^k), k=1..1+floor(n/2)) od; # yields sequence in triangular form
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jul 16 2005
STATUS
approved