Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n and having k horizontal segments (a horizontal segment is a maximal string of horizontal steps).
A Schroeder path is a lattice path starting from (0,0), ending at a point on the x-axis, consisting only of steps U=(1,1), D=(1,-1) and H=(2,0) and never going below the x-axis. Schroeder paths are counted by the large Schroeder numbers (A006318).
T(n, k) = Sum_{j=ceiling((k-1)/2)..n-k} binomial(2j, j)*binomial(2j+1, k)*binomial(n-j-1, k-1)/(j+1) for 1 <= k <= round(2n/3).
G.f.: G = G(t, z) satisfies z*(1 - z + t*z)*G^2 - (1-z)*G + 1 - z + t*z = 0.
EXAMPLE
T(2,1)=4 because we have (HH), (H)UD, UD(H) and U(H)D; the horizontal segments are shown between parentheses.
Triangle starts:
1;
1, 1;
2, 4;
5, 14, 3;
14, 49, 26, 1;
42, 175, 154, 23;
132, 637, 786, 241, 10;
429, 2353, 3728, 1831, 215, 2;
1430, 8788, 16966, 11723, 2564, 115;
4862, 33098, 75249, 67669, 22866, 2319, 35;
MAPLE
T:=proc(n, k) if k=0 then binomial(2*n, n)/(n+1) else sum(binomial(2*j, j)*binomial(2*j+1, k)*binomial(n-j-1, k-1)/(j+1), j=ceil((k-1)/2)..n-k) fi end: for n from 0 to 11 do seq(T(n, k), k=0..round(2*n/3)) od; # yields sequence in triangular form
