|
Search: id:A104549
|
|
|
| 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). 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). |
|
+0
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, 58786
(list; graph; listen)
|
|
|
OFFSET
|
0,4
|
|
|
FORMULA
|
T(n, 0)=binomial(2n, n)/(n+1) (i.e. the Catalan numbers, A001008); T(n, k)=sum(binomial(2j, j)*binomial(2j+1, k)*binomial(n-j-1, k-1)/(j+1), j=ceil((k-1)/2)..n-k) for 1<=k<=round(2n/3). G.f.=G=G(t, z) satisfies z(1-z+tz)G^2-(1-z)G+1-z+tz=0
|
|
EXAMPLE
|
Triangle starts:
1;
1,1;
2,4;
5,14,3;
14,49,26,1;
T(2,1)=4 because we have (HH),(H)UD,UD(H) and U(H)D; the horizontal segments are shown between parentheses.
|
|
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
|
|
CROSSREFS
|
Row sums are the large Schroeder numbers (A006318). Column 0 yields the Catalan numbers (A001008).
Cf. A006318, A001008, A104550.
Sequence in context: A102992 A136563 A127077 this_sequence A000063 A039574 A121410
Adjacent sequences: A104546 A104547 A104548 this_sequence A104550 A104551 A104552
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 14 2005
|
|
|
Search completed in 0.002 seconds
|
