16
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ I wanted to implement the formula for A000672 to get this done, but I don't know what the function C [referenced in the formula] is... \$\endgroup\$ – Zaelin Goodman Feb 10 at 15:57
  • 2
    \$\begingroup\$ @ZaelinGoodman I guess it's a combination: \$C(n,r)=n!/(r!(n-r)!)\$ \$\endgroup\$ – Arnauld Feb 10 at 16:50
  • \$\begingroup\$ @Arnauld It is definitely a combination, thanks! Unfortunately, still can't get that formula to work for me, but at least now I know it's my own fault. \$\endgroup\$ – Zaelin Goodman Feb 10 at 19:13
  • 1
    \$\begingroup\$ @ZaelinGoodman FWIW, I've posted another JS answer that implements the formula. Should you decide to port it in C, I would recommend to 1) use for loops instead of my helper function S and 2) use modulo tests before invoking b whenever the argument is the result of a division (instead of passing a float and testing whether it's actually an integer in the function). \$\endgroup\$ – Arnauld Feb 11 at 10:58
13
\$\begingroup\$

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

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.