A104549 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).

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, 16796, 125476, 328012, 364864, 171310, 29869, 1386, 5

Offset: 0

Author

Emeric Deutsch, Mar 14 2005

Keywords

• nonn
• tabf

Comments

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

Examples

			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;
		

Links

• G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Crossrefs

Row sums are the large Schroeder numbers (A006318). Column 0 yields the Catalan numbers (A000108).

Cf. A006318, A000108, A104550.

Programs

Magma

function T(n,k)
  if k eq 0 then return Catalan(n);
  else return (&+[Catalan(j)*Binomial(2*j+1,k)*Binomial(n-j-1,k-1): j in [Ceiling((k-1)/2)..n-k]]);
  end if; return T;
end function;
[T(n,k): k in [0..Round(2*n/3)], n in [0..12]]; // G. C. Greubel, Jan 01 2023

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

Mathematica

T[n_, k_]:= T[n, k]= Sum[CatalanNumber[j]*Binomial[2*j+1,k]*Binomial[n -j-1, k-1], {j, Ceiling[(k-1)/2], n-k}];
Table[T[n, k], {n,0,15}, {k, 0, Round[2*n/3]}]//Flatten (* G. C. Greubel, Jan 01 2023 *)

SageMath

@CachedFunction
def T(n,k): # T = A104549
    if (k==0): return catalan_number(n)
    else: return sum(catalan_number(j)*binomial(2*j+1,k)*binomial(n-j-1,k-1) for j in range(ceil((k-1)/2),n-k+1))
flattan([[T(n,k) for k in range(round(2*n/3)+1)] for n in range(12)]) # G. C. Greubel, Jan 01 2023

Formula

T(n, 0) = A000108(n).

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.