A126183 Triangle read by rows: T(n,k) is number of hex trees with n edges and k nonroot nodes of outdegree 2.

1, 3, 10, 33, 3, 108, 29, 351, 186, 6, 1134, 990, 95, 3645, 4725, 900, 15, 11664, 20979, 6615, 329, 37179, 88452, 41580, 4116, 42, 118098, 358668, 234738, 38556, 1176, 373977, 1410615, 1224720, 300510, 18270, 126, 1180980, 5412825, 6014250

Offset

0,2

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).

Row 0 has one term; rows 2n-1 and 2n have n terms.

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

T(n,0)=A126184(n).

Sum_{k=1..floor((n-1)/2)} k*T(n,k) = A126185(n).

Links

Table of n, a(n) for n=0..39.

F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.

Formula

G.f.: G(t,z)=1+3*z*H+z^2*H^2, where H=H(t,z) is defined by H=1+3*z*H+t*z^2*H^2 (see explicit expression of G(t,z) at the Maple program).

Example

Triangle begins:
    1;
    3;
   10;
   33,   3;
  108,  29;
  351, 186,   6;

Maple

G := 1/2/t^2/z^2*(-11*t*z^2+2*t^2*z^2+3*z*t+9*z^2-6*z+1-sqrt(1-58*t*z^2-12*z+54*z^2 +6*z*t+81*z^4-108*z^3 -36*t^3*z^4+153*t^2*z^4 -198*t*z^4-78*t^2*z^3+186*t*z^3+9*t^2*z^2)): Gser:=simplify(series(G, z=0, 16)): for n from 0 to 18 do P[n]:=sort(coeff(Gser, z, n)) od: 1; for n from 1 to 13 do seq(coeff(P[n], t, j), j=0..floor((n-1)/2)) od; # yields sequence in triangular form

Mathematica

len = 40; m = Ceiling[2 Sqrt[len]]; gf[t_, z_] = g /. Solve[g == 1 + 3z* h + z^2*h^2 && h == 1 + 3z*h + t*z^2*h^2, g, h][[1]]; gser = Series[gf[t, z], {z, 0, m}]; p[n_] := Coefficient[gser, z, n]; tr[n_, k_] := tr[n, k] = Coefficient[p[n], t, k]; Flatten[Table[ tr[n, k], {n, 0, m}, {k, 0, Max[0, Floor[(n-1)/2]]}]][[1 ;; len]] (* Jean-François Alcover, May 31 2011, after Maple prog. *)

Crossrefs

Cf. A002212, A126184, A126185.

Sequence in context: A184436 A149028 A174573 * A174798 A042039 A080697

Adjacent sequences: A126180 A126181 A126182 * A126184 A126185 A126186

Keyword

nonn,tabf

Author

Emeric Deutsch, Dec 19 2006

Extensions

Keyword tabl changed to tabf by Michel Marcus, Apr 09 2013

Status

approved