|
Search: id:A126177
|
|
|
| A126177 |
|
Triangle read by rows: T(n,k) is number of hex trees with n edges and k leaves (n>=1, 1<=k<=1+floor(n/2)). A hex tree is a rooted tree where each vertex has 0, 1, or 2 children and, when only one child is present, it is either a left child, or a middle child, or a right child (name due to an obvious bijection with certain tree-like polyhexes; see the Harary-Read paper). |
|
+0
1
|
|
| 3, 9, 1, 27, 9, 81, 54, 2, 243, 270, 30, 729, 1215, 270, 5, 2187, 5103, 1890, 105, 6561, 20412, 11340, 1260, 14, 19683, 78732, 61236, 11340, 378, 59049, 295245, 306180, 85050, 5670, 42, 177147, 1082565, 1443420, 561330, 62370, 1386, 531441, 3897234
(list; graph; listen)
|
|
|
OFFSET
|
1,1
|
|
|
COMMENT
|
Also number of hex trees with n edges and k-1 nodes of outdegree 2. Row n has 1+floor(n/2) terms. Sum of terms in row n = A002212(n+1). T(n,1)=3^n (A000244). T(n,2)=A027472(n+1). sum(kT(n,k), k=1..1+floor(n/2))=A026375(n)
|
|
REFERENCES
|
F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.
|
|
FORMULA
|
T(n,k)=3^(n-2k+2)binomial(2k-2,k-1)*binomial(n,2k-2)/k. Proof: There are Catalan(k-1) full binary trees with k leaves. Each of them has 2k-2 edges. Additional n-2k+2 edges can be inserted as paths at the existing 2k-1 vertices in 3^(n-2k+2)*binom(n,2k-2) ways. G.f.=G=G(t,z) satisfies z^2*G^2-(1-3z-2tz^2)G+tz(3+tz)=0.
|
|
EXAMPLE
|
Triangle starts:
3;
9,1;
27,9;
81,54,2;
243,270,30;
|
|
MAPLE
|
T:=(n, k)->3^(n-2*k+2)*binomial(2*k-2, k-1)*binomial(n, 2*k-2)/k: for n from 1 to 13 do seq(T(n, k), k=1..1+floor(n/2)) od; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A002212, A000244, A027472, A026375.
Sequence in context: A080322 A126179 A128727 this_sequence A128733 A128724 A128753
Adjacent sequences: A126174 A126175 A126176 this_sequence A126178 A126179 A126180
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 19 2006
|
|
|
Search completed in 0.002 seconds
|
