|
|
A126179
|
|
Triangle read by rows: T(n,k) is number of hex trees with n edges and k branches (1 <= k <= n).
|
|
1
|
|
|
3, 9, 1, 27, 6, 3, 81, 27, 27, 2, 243, 108, 162, 24, 6, 729, 405, 810, 180, 90, 5, 2187, 1458, 3645, 1080, 810, 90, 15, 6561, 5103, 15309, 5670, 5670, 945, 315, 14, 19683, 17496, 61236, 27216, 34020, 7560, 3780, 336, 42, 59049, 59049, 236196, 122472
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
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 median child, or a right child (name due to an obvious bijection with certain tree-like polyhexes; see the Harary-Read reference).
|
|
LINKS
|
|
|
FORMULA
|
Sum of terms in row n = A002212(n+1).
T(2n,2n) = c(n); T(2n+1,2n+1) = 3*c(n), where c(n) = binomial(2n,n)/(n+1) is a Catalan number (A000108).
Sum_[k=1..n} k*T(n,k) = A126180(n).
T(n,k) = 3^(n-k+1)*binomial(n-1,k-1)*c((k-1)/2) if k is odd; T(n,k) = 3^(n-k)*binomial(n-1,k-1)*c(k/2) if k is even; c(m) = binomial(2m,m)/(m+1) is a Catalan number.
G.f.: ((1-3z+3tz)/(1-3z))*C(t^2*z^2/(1-3z)^2)-1, where C(z) = (1-sqrt(1-4z))/(2z) is the Catalan function.
G.f.: (1-3z+3tz)*(1-3z-sqrt((1-3z)^2-4t^2*z^2))/(2t^2*z^2)-1;
|
|
EXAMPLE
|
Triangle starts:
3;
9, 1;
27, 6, 3;
81, 27, 27, 2;
243, 108, 162, 24, 6;
|
|
MAPLE
|
c:=n->binomial(2*n, n)/(n+1): T:=proc(n, k) if k mod 2 = 0 then 3^(n-k)*binomial(n-1, k-1)*c(k/2) else 3^(n-k+1)*binomial(n-1, k-1)*c((k-1)/2) fi end: for n from 1 to 11 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form
|
|
MATHEMATICA
|
n = 20; g[t_, z_] = (1 - 3z + 3t*z)* ((1 - 3z - Sqrt[(1 - 3z)^2 - 4t^2*z^2])/(2t^2*z^2)) - 1; Flatten[ Rest[ CoefficientList[#, t]] & /@ Rest[ CoefficientList[ Series[g[t, z], {z, 0, n}], z]]] (* Jean-François Alcover, Jul 22 2011, after g.f. *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|