OFFSET
1,6
COMMENTS
Halin graphs are planar and 3-connected and can be embedding in the sphere in essentially one way up to mirror symmetry. This sequence counts each graph as either 1 or 2 depending on if it is mirror symmetric.
From Vjeran Crnjak, Jun 21 2026: (Start)
Also counts orientation-preserving unrooted plane trees with n vertices and no vertex of degree 2. Equivalently, this is the number of contour-rerooting orbits of rooted ordered plane trees with n vertices and no vertex of degree 2.
Let B = B(x) be the g.f. for a branch, i.e., a rooted plane subtree attached to a parent edge. The root of such a branch has degree 1 plus its number of children. Since degree 2 is forbidden, it may have 0, 2, 3, ... children, but not 1. Thus B = x*(1 + B^2 + B^3 + ...) = x*(1 - B + B^2)/(1 - B). This is the same branch series used for A187306. The tree dissymmetry theorem gives U = V + E - D, where U, V, E, and D count the unrooted, vertex-rooted, edge-rooted, and directed-edge-rooted cases, respectively. A vertex-rooted plane tree has a cyclic list of incident branches. Let CYC(B) = Sum_{r>=1} phi(r)/r * log(1/(1 - B(x^r))). This counts nonempty cyclic lists of branches. The empty cyclic list gives the one-vertex tree. Degree 2 at the root corresponds to a cyclic list of exactly two branches, whose g.f. is CYC_2(B) = (B(x)^2 + B(x^2))/2. Hence V = x*(1 + CYC(B) - CYC_2(B)). An edge-rooted tree is an unordered pair of branches, so E = (B(x)^2 + B(x^2))/2. A directed-edge-rooted tree is an ordered pair of branches, so D = B(x)^2. Therefore the g.f. U(x) for the unrooted orientation-preserving plane trees with no vertex of degree 2 is U(x) = x*(1 + Sum_{r>=1} phi(r)/r * log(1/(1 - B(x^r))) - (B(x)^2 + B(x^2))/2) + (B(x^2) - B(x)^2)/2, where B = x*(1 - B + B^2)/(1 - B). Expanding the series and omitting the one- and two-vertex trees, the coefficients from x^4 onward are the sequence.
Example: the 4-vertex star (ooo).
o
|
o---o---o
As an unrooted plane tree, there is only one object. As a rooted ordered tree, root can be center or leaf node. A187306 sees two rooted versions, while this sequence sees one unrooted orbit. (End)
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Halin Graph.
Wikipedia, Halin graph.
FORMULA
G.f.: x*(Sum_{r>=1} phi(r)/r*log(1/(1-B(x^r)))-(B(x)^2+B(x^2))/2)+(B(x^2)-B(x)^2)/2-x^2, where B=x*(1-B+B^2)/(1-B) and phi is Euler's totient function. - Vjeran Crnjak, Jun 21 2026
EXAMPLE
From Vjeran Crnjak, Jun 22 2026: (Start)
Let o denote a leaf. In a nested expression, parentheses denote a non-leaf vertex joined to the enclosed branches and, if nested, also to its parent.
a(4) = 1: (ooo).
a(5) = 1: (oooo).
a(6) = 2: (ooooo), (oo(oo)).
a(7) = 2: (oooooo), (ooo(oo)).
a(8) = 4: (ooooooo), (oooo(oo)), (ooo(ooo)), (o(oo)(oo)).
(End)
PROG
(PARI) A380360seq(36) \\ See PARI Link in A380362 for program code.
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
Andrew Howroyd, Jan 25 2025
STATUS
approved