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, 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

Author

Emeric Deutsch, Jul 16 2005

Keywords

• nonn
• tabf

Comments

Row n has 1 + floor(n/2) terms.

Row sums yield the large Schroeder numbers (A006318).

Examples

			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;
		

Crossrefs

Cf. A000108, A006318, A007317, A026002.

Programs

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

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