|
Search: id:A120983
|
|
|
| A120983 |
|
Triangle read by rows: T(n,k) is the number of ternary trees with n edges and having k vertices of outdegree 3 (n>=0, k>=0). A ternary tree is a rooted tree in which each vertex has at most three children and each child of a vertex is designated as its left or middle or right child. |
|
+0
4
|
|
| 1, 3, 12, 54, 1, 261, 12, 1323, 105, 6939, 810, 3, 37341, 5859, 63, 205011, 40824, 840, 1143801, 277830, 9072, 12, 6466230, 1861380, 86670, 360, 36960300, 12335895, 764478, 6435, 213243435, 81120204, 6377778, 89100, 55, 1240219269, 530408736
(list; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
Row n has 1+floor(n/3) terms. Row sums yield A001764. T(n,0)=A107264(n). Sum(k*T(n,k),k>=1)=binom(3n,n-3)=A004321(n).
|
|
FORMULA
|
T(n,k)=(1/(n+1))*binomial(n+1,k)*sum(3^j*binomial(n+1-k,j)*binomial(j,n-3k-j), j=0..n+1-k). G.f.=G=G(t,z) satisfies G=1+3zG+3z^2*G^2+tz^3*G^3.
|
|
EXAMPLE
|
T(3,1)=1 because we have (Q,L,M,R), where Q denotes the root and L (M,R) denotes a left (middle, right) child of Q.
Triangle starts:
1;
3;
12;
54,1;
261,12;
1323,105;
6939,810,3;
|
|
MAPLE
|
T:=(n, k)->(1/(n+1))*binomial(n+1, k)*sum(3^j*binomial(n+1-k, j)*binomial(j, n-3*k-j), j=0..n+1-k): for n from 0 to 14 do seq(T(n, k), k=0..floor(n/3)) od; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A001764, A107264, A120429, A120981, A120982, A004321.
Sequence in context: A026781 A110122 A060460 this_sequence A124810 A123348 A083881
Adjacent sequences: A120980 A120981 A120982 this_sequence A120984 A120985 A120986
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 21 2006
|
|
|
Search completed in 0.002 seconds
|
