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

Author

Emeric Deutsch, Dec 19 2006

Keywords

• nonn
• tabf

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

Examples

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

Links

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

Crossrefs

Cf. A002212, A126184, A126185.

Programs

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

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

Extensions

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