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