A126186 Triangle read by rows: T(n,k) is number of hex trees with n edges and level of first leaf (in the preorder traversal) equal to k (1 <= k <= n).

3, 1, 9, 3, 6, 27, 10, 19, 27, 81, 36, 66, 90, 108, 243, 137, 245, 325, 378, 405, 729, 543, 954, 1242, 1416, 1485, 1458, 2187, 2219, 3848, 4944, 5563, 5760, 5589, 5103, 6561, 9285, 15942, 20286, 22620, 23235, 22410, 20412, 17496, 19683, 39587, 67442, 85194

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 middle child, or a right child (name due to an obvious bijection with certain tree-like polyhexes; see the Harary-Read reference).

Links

Table of n, a(n) for n=1..48.

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) = [k/(n-k)] sum(3^(2k+2j-n)*binomial(n-k,j)*binomial(k-1+j,n-k-1-j), j=ceiling((n-2k)/2)..n-k) if 1<=k<n; T(n,n)=3^n.

G.f.: 2/[2-t-3tz+t*sqrt(1-6z+5z^2)]-1.

Sum of terms in row n = A002212(n+1).

T(n,1) = A025238(n); T(n,1) = A002212(n-1) for n>=2.

T(n,n) = 3^n = A000244(n); T(n,n-1) = (n-1)*3^(n-2) = A027471(n) (n>=2).

Sum_{k=1..n} k*T(n,k) = A126187(n).

Example

Triangle starts:
   3;
   1,   9;
   3,   6,  27;
  10,  19,  27,  81;
  36,  66,  90, 108, 243;

Maple

G:=2/(2-t-3*t*z+t*sqrt(1-6*z+5*z^2))-1: Gser:=simplify(series(G, z=0, 14)): for n from 1 to 10 do P[n]:=sort(coeff(Gser, z, n)) od: for n from 1 to 10 do seq(coeff(P[n], t, k), k=1..n) od; # yields sequence in triangular form

Mathematica

n = 10; g[t_, z_] = 2/(2 - t - 3t*z + t*Sqrt[1 - 6z + 5z^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

Cf. A000244, A002212, A025238, A027471, A126187.

Sequence in context: A309057 A246269 A328475 * A368568 A370150 A162852

Adjacent sequences: A126183 A126184 A126185 * A126187 A126188 A126189

Keyword

nonn,tabl

Author

Emeric Deutsch, Dec 22 2006

Status

approved