Count unrooted, unlabeled binary trees of n nodes

Question

An unrooted binary tree is an unrooted tree (a graph that has single connected component and contains no cycles) where each vertex has exactly one or three neighbors. It is used in bioinformatics to show evolutionary relationships between species.

If such a tree has \$n\$ internal nodes, it necessarily has \$n+2\$ leaves. Therefore it always has an even number of vertices.

Challenge

Given a positive integer \$n\$, compute the number of distinct unrooted, unlabeled binary trees having \$2n\$ vertices. This is OEIS A000672. You may take \$2n\$ as input instead, and in that case, you may assume the input is always even.

The shortest code in bytes wins.

Illustration

n=1 (2 nodes, 1 possible)

O-O

n=2 (4 nodes, 1 possible)

O
 \
  O-O
 /
O

n=3 (6 nodes, 1 possible)

O     O
 \   /
  O-O
 /   \
O     O

n=4 (8 nodes, 1 possible)

O     O
 \   /
  O-O
 /   \
O     O-O
     /
    O

n=5 (10 nodes, 2 possible)

                  C
                   \
A     B       C     O-C
 \   /         \   /
  O-O     A     O-O
 /   \   /     /   \
A     O-O     C     O-C
     /   \         /
    B     A       C

n=6 (12 nodes, 2 possible)
(branching from A)  (branching from B or C)
    O                    O
   /                      \
O-O     O            O     O-O
   \   /              \   /
    O-O     O          O-O     O
   /   \   /          /   \   /
  O     O-O          O     O-O
       /   \              /   \
      O     O            O     O

Test cases

The values for first 20 terms (for \$n=1\dots 20\$) are as follows:

1, 1, 1, 1, 2, 2, 4, 6, 11, 18,
37, 66, 135, 265, 552, 1132, 2410, 5098, 11020, 23846

Answer 1

JavaScript (ES6), 265 bytes

This code actually builds all possible trees and filters out isomorphic results. This is quite slow for \$n>9\$ but \$a(10)=18\$ was checked locally.

n=>(K=A=>A.map(a=>[...a].sort()).sort(),g=(A,k)=>k>n-3?g[K(A)]||(N--,P=(p,a)=>a.map((v,i)=>P([...p,v],a.filter(_=>i--)))+a?1:g[K(A.map(a=>a.map(v=>~p[v])))]=1)(i=[],A.map(_=>--i)):A.map((a,i)=>a.some((v,j)=>~v?0:a[g([...A,[i,v,v]],a[j]=-~k),j]=v)))([[N=-1,N,N]])|~N

Try it online!

How?

Tree representation

Only internal nodes are stored explicitly as triplets \$[n_0,n_1,n_2]\$ where each value is either the 0-indexed ID of another internal node, or \$-1\$ for a leaf.

The final list of triplets can be normalized with the helper function \$K\$ which first sorts each triplet and then the entire list:

K = A => A.map(a => [...a].sort()).sort()

Main algorithm

The main recursive function \$g\$ builds all possible trees with \$n-1\$ internal nodes¹. We start with an arbitrary root node \$[-1,-1,-1]\$ and attach each new internal node to the first available slot in one of the previous nodes.

For the first iteration, there's only one possible option:

$$\big[[-1,-1,-1]\big] \rightarrow \big[[1,-1,-1],[0,-1,-1]\big]$$

The underlying object of \$g\$ is also used to store all normalized trees that were already found.

Whenever a new tree is generated, we use the helper function \$P\$ to generate all permutations of the vertex identifiers. This allows us to store in \$g\$ all normalized trees that are isomorphic to the one we've found.

---

^{1: For obscure golfing reasons, the code actually generates at least 2 internal nodes. This is inconsistent for \$n<3\$ but leads to only one possible tree anyway, which is the expected result.}

Answer 2

JavaScript (ES6), 267 bytes

A slightly longer but much faster version that implements the formula described in A000672, which itself is based on A001190.

n=>n<5||-(b=n=>(B=(n,g=i=>i<n/2&&B(i)*B(n-i)+g(i+1))=>v=n%1?0:n<2?n:g(1)+B(n/2)*-~v/2)(n+1))(n)+b(--n/2)+2*b(n)-2*(C=(n,r)=>!r||C(n,--r)*(r-n)/~r)(1+b(--n/3),3)-(S=(c,b,i=1)=>i>b?0:c(i)+S(c,b,i+1))(i=>C(b(i),2)*b(n-2*i),~-n/2)+S(i=>b(i)*S(j=>b(j)*b(n-j),--n/2,i),n/3)

Try it online!

Please follow this link for a formatted version of the code.