|
|
A125177
|
|
Triangle read by rows: T(n,0)=C(2n,n)/(n+1) for n>=0; T(n,n+1)=0; T(n,k)=T(n-1,k)+T(n-1,k-1) for 1<=k<=n.
|
|
4
|
|
|
1, 1, 1, 2, 2, 1, 5, 4, 3, 1, 14, 9, 7, 4, 1, 42, 23, 16, 11, 5, 1, 132, 65, 39, 27, 16, 6, 1, 429, 197, 104, 66, 43, 22, 7, 1, 1430, 626, 301, 170, 109, 65, 29, 8, 1, 4862, 2056, 927, 471, 279, 174, 94, 37, 9, 1, 16796, 6918, 2983, 1398, 750, 453, 268, 131, 46, 10, 1, 58786
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Column k (k>=1) starts with 0, followed by the partial sums of column k-1. Row sums yield A126221.
Indexing n and k from 1 instead of from 0, T(n,k) is the number of Dyck n-paths whose first peak is at height k and whose first component avoids DUU. A primitive Dyck path is one whose only return (to ground level) is at the end. The interior returns of a general Dyck path split the path into a list of primitive Dyck paths, called its components. For example, UUDDUD has components UUDD, UD and T(4,2) = 4 counts UUDUDUDD, UUDDUUDD, UUDDUDUD, UUDUDDUD (but not UUDUUDDD because its first component contains a DUU). - David Callan, Jan 17 2007
|
|
LINKS
|
|
|
FORMULA
|
G.f.: G(t,x)=(1-x)[1-sqrt(1-4x)]/[2x(1-x-tx)].
|
|
EXAMPLE
|
First few rows of the triangle are:
1;
1, 1;
2, 2, 1;
5, 4, 3, 1;
14, 9, 7, 4, 1;
42, 23, 16, 11, 5, 1;
...
(5,3) = 16 = 7 + 9 = (4,3) + (4,2).
Production matrix is
1, 1,
1, 1, 1,
1, 0, 1, 1,
2, 0, 0, 1, 1,
4, 0, 0, 0, 1, 1,
9, 0, 0, 0, 0, 1, 1,
21, 0, 0, 0, 0, 0, 1, 1,
51, 0, 0, 0, 0, 0, 0, 1, 1,
127, 0, 0, 0, 0, 0, 0, 0, 1, 1 (End)
|
|
MAPLE
|
T:=proc(n, k) if k=0 then binomial(2*n, n)/(n+1) elif n=0 then 0 else T(n-1, k)+T(n-1, k-1) fi end: for n from 0 to 11 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form
G:=(1-x)*(1-sqrt(1-4*x))/2/x/(1-x-t*x): Gser:=simplify(series(G, x=0, 15)): for n from 0 to 11 do P[n]:=sort(coeff(Gser, x, n)) od: for n from 0 to 11 do seq(coeff(P[n], t, j), j=0..n) od; # yields sequence in triangular form
|
|
PROG
|
(Maxima) T(n, k)=sum((binomial(2*i, i)*binomial(n-i-1, n-k-i))/(i+1), i, 0, n-k); /* Vladimir Kruchinin, Nov 03 2016 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|