login
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)
2
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,4
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).
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.
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
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 *)
PROG
(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
(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
CROSSREFS
Row sums are the large Schroeder numbers (A006318). Column 0 yields the Catalan numbers (A000108).
Sequence in context: A136563 A127077 A367027 * A174513 A000063 A368378
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Mar 14 2005
STATUS
approved