|
Search: id:A138158
|
|
|
| A138158 |
|
Triangle read by rows: T(n,k) is the number of ordered trees with n edges and path length k; 0<=k<=n(n+1)/2. |
|
+0
2
|
|
| 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 2, 1, 1, 0, 0, 0, 0, 1, 3, 3, 3, 2, 1, 1, 0, 0, 0, 0, 0, 1, 4, 6, 7, 7, 5, 5, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 1, 5, 10, 14, 17, 16, 16, 14, 11, 9, 7, 5, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 6, 15, 25, 35, 40, 43, 44, 40, 37, 32, 28, 22, 18, 13, 11, 7, 5, 3, 2, 1, 1
(list; graph; listen)
|
|
|
OFFSET
|
0,12
|
|
|
COMMENT
|
a(n)=number of Dyck paths of semilength n for which the sum of the heights of the vertices that terminate an upstep (i.e. peaks and doublerises) is k. Example: T(4,7)=3 beacuse we have UUDUDUDD, UDUUUDDD, and UUUDDDUD.
Row n contains 1+n(n+1)/2 terms.
Row sums are the Catalan numbers (A000108).
Sum of entries in column n = A005169(n).
Sum(k*T(n,k),k=0..n(n+1)/2)=A000346(n-1).
T(n,k)=A047998(k,n).
|
|
FORMULA
|
G.f.=G(t,z) satisfies G(t,z)=1+tzG(t,z)G(t,tz). Row generating polynomials P[n]=P[n](t) are given by P[0]=1, P[n]=t*Sum(P[j]P[n-j-1]t^(n-1-j),j=0..n-1) (n>=1).
|
|
EXAMPLE
|
T(2,2)=1 because /\ is the only ordered tree with 2 edges and path length 2.
|
|
MAPLE
|
P[0]:=1: for n to 7 do P[n]:=sort(expand(t*(sum(P[j]*P[n-j-1]*t^(n-j-1), j= 0.. n-1)))) end do: for n from 0 to 7 do seq(coeff(P[n], t, j), j=0..(1/2)*n*(n+1)) end do; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A000108, A005169, A000346, A047998.
Sequence in context: A127326 A064663 A025923 this_sequence A057276 A035185 A086013
Adjacent sequences: A138155 A138156 A138157 this_sequence A138159 A138160 A138161
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 21 2008
|
|
|
Search completed in 0.002 seconds
|
