Better than Will Hunting

When programming, every tree has a special node we call the root node, and every node has a list of child nodes in some order. This makes trees easy to work with, as we can start at the root node and recursively walk down child nodes or whatever. For example, we can compare two trees by starting at their respective root nodes and explore them in unison until we find a discrepancy.

But we’re not counting these well-manicured trees. The trees in question are unordered and unlabeled: a bunch of dots connected by lines, and all we know is that there are no cycles. Without roots, it’s trickier to define when two trees are identical. A formal definition is vital, as how can we count trees if we can’t tell them apart?

The only way forward is to take the graph theory notion of equality. We consider two trees to be the same, or isomorphic, if there exists a bijection \(\phi\) from the nodes of one tree to the other such that \(v, w\) are connected if and only if \(\phi(v), \phi(w)\) are connected.

But now what? Are we to try every possible map to compare trees? Without data structures and memory and pointers, we’re out of our comfort zone and trees seem like slippery amorphous blobs.

Luckily, a clever trick allows us to get a grip on an unrooted tree. Suppose we delete every leaf node (along with the edge that connected it to the tree). We’re left with a smaller tree. If we iterate this process, then eventually, just before the tree vanishes, either a single node or a single edge remains.

Call this last node or edge standing the center node or center edge. Hence every tree has a sort of root after all, though depending on the tree, it might be an edge instead of a node.

The center is a promising start. It suggests we could start from a center node or edge, then count the number of ways to attach subtrees of certain sizes to the center. However, we must somehow avoid double-counting while doing so.

For this task, we use a marvellous correspondence due to the dissymmetry theorem of Pierre Leroux. Define:

Conditions for isomorphisms of such trees are tightened as we’d expect, that is, an isomorphism \(\phi\) must map any root edges to root edges, and any root nodes to root nodes.

Let \(T\) be a tree, and let:

Consider an element of \(T^\bullet\). If its root node is not the center, then there is a unique path from the root to the center and we can mark the first edge on this path to get an element of \(T^{\bullet-}\).

Similarly, given an element of \(T^-\), if its root edge is not the center, then there is a unique path from the root to the center and we can mark the first node on this path to get an element of \(T^{\bullet-}\). (This reminds me of a key step in my favourite proof of Cayley’s formula for counting labeled trees.)

We have exhibited a bijection:

\[(T^\bullet\cup T^-)\setminus\{c\} \longleftrightarrow T^{\bullet-}\]

Therefore:

\[ |T^\bullet| + |T^-| - | T^{\bullet-}| = 1 \]

This incredible equation suggests a method for counting a set of unrooted trees. Count the node-rooted, edge-rooted, and node-and-adjacent-edge-rooted versions of every tree in the set. Then the number of trees is the sum of the first two counts minus the third count.

This indirectness might seem silly, and indeed, it is silly to do all this if we’re just counting a single tree, but this method turns out to be sensible in general. The extra conditions of various styles of rooted trees make them easier to count.

Let’s start with node-rooted trees. From our money-changing demo, if we have coins with denominations \(c_1, …​, c_k\) then the number of ways to make \(c\) cents is the coefficient of \(x^c\) in the power series:

\[ \frac{1}{(1 - x^{c_1})…​(1 - x^{c_k})} \]

This formula is valid even if \(c_1,…​,c_k\) are not distinct, which happens when, say, we wish to distinguish between limited-edition commemorative 10c coins and regular 10c coins when counting the ways to make change. Thus if \(a_n\) is the number of different coins worth \(n\) cents we can rewrite this power series as:

\[ \frac{1}{(1 - x)^{a_1}(1 - x^2)^{a_2}...} \]

Building node-rooted trees is similar to making change. A node-rooted tree of size \(c + 1\) has one root node and some number of children which are also node-rooted trees, and whose sizes add up to \(c\); the number of ways this can happen is the coefficient of \(x^c\) in:

\[ \frac{1}{(1 - x)^{a_1}(1 - x^2)^{a_2}...} \]

where \(a_n\) is the number of node-rooted trees of size \(n\).

Let \(r(x)\) be the ordinary power series for the number of node-rooted trees with \(n\) nodes:

\[ \newcommand{\ops}{\overset{ops}\longleftrightarrow} r \ops \left\{a_n\right\}_0^\infty \]

Then:

\[ r = \sum_{n=0}^\infty a_n x^n = x \sum_{n=0}^\infty a_{n+1} x^n = x \prod_{n=1}^\infty \frac{1}{(1 - x^n)^{a_n}} \]

Wilf, Generatingfunctionology, derives this equation at the end of Chapter 3 via a more general framework, and notes that while it is sufficient for determining the coefficients \(a_0, a_1, …​\) of \(r\), the equation is "fairly formidable". Indeed, the infinite product makes calculation unwieldy, as do the exponentiations by \(a_n\).

Following Napier, we apply logarithms to change products to sums and exponentiations to multiplications. Then we interchange the order of summations to tightly bond each \(a_n\) and \(x^n\) so we can write expressions in terms of \(r\) rather than its individual coefficients.

Recall:

\[ \log 1/(1 - z) = z + z^2/2 + z^3/3 + …​ \]

For fun, we confirm several terms:

We have:

\[ \begin{align} \log \prod_{n=1}^\infty \frac{1}{(1 - x^n)^{a_n}} & = \sum_{n=1}^\infty a_n \log \frac{1}{1 - x^n} \\ & = \sum_{n=1}^\infty a_n \sum_{k=1}^\infty \frac{x^{nk}}{k} \\ & = \sum_{k=1}^\infty \frac{1}{k} \sum_{n=1}^\infty a_n (x^k)^n \\ & = \sum_{k=1}^\infty \frac{1}{k} r(x^k) \\ \end{align} \]

Therefore:

\[ r(x) = x \exp \sum_{k=1}^\infty \frac{1}{k} r(x^k) \\ \]

Define \(M\) to be the operator that takes a power series with a zero constant term and returns the power series that arises in the money-changing problem:

\[ M f(x) = \exp \sum_{k=1}^\infty \frac{1}{k} f(x^k) \]

Then we can write:

\[ r(x) = x M r(x) \]

We define a money function to compute \(M\). Some care is needed because our mutually recursive lazy lists require bootstrapping to avoid infinite loops; typically, we use x in our code to to hive off deeper recursive calls behind a (:+:).

We can produce \(f(x^k)\) by inserting \(k\) zero coefficients before each coefficient of \(f(x)\). Since \(a_0 = 0\), we have \(f(x^k) = a_1 x^{k} + …​ \), so we only start doing this on the \(k\)th step, giving the recursion enough runway to take off.

Now we can count node-rooted trees:

Our sequence agrees with the On-line Encyclopedia of Integer Sequences (OEIS).

Most of the hard work is done. The other two cases are closely related.

A node-and-adjacent-edge-rooted tree of size \(n\) corresponds to an ordered pair of node-rooted trees whose sizes sum to \(n\), because on either side of the root edge lies a rooted subtree, and the root of one of them is also the root node of the original tree. By convolution, the ordinary power series for counting node-and-adjacent-edge-rooted trees of size \(n\) is simply:

\[ r(x)^2 \]

An edge-rooted tree of size \(n\) corresponds to an unordered pair of node-rooted trees whose sizes sum to \(n\), because on either side of the root edge lies a rooted subtree, but there is no reason to order them one way or the other. Thus \( r(x)^2 \) doesn’t quite work because it counts each pair of distinct trees twice, and counts each tree paired with itself once. We correct for this by computing:

\[ \frac{r(x)^2 + r(x^2)}{2} \]

because \(r(x^2)\) counts pairs of the same tree (if there are \(a_k\) trees of size \(k\), then there are \(a_k\) pairs of identical trees whose total size is \(2k\)).

Then the ordinary power series for the number of unrooted trees of size \(n\) is:

\[ r(x) + \frac{r(x)^2 + r(x^2)}{2} - r(x)^2 = r(x) - \frac{r(x)^2 - r(x^2)}{2} \]

Our numbers agree with the OEIS. (The numbers on Gessel’s slides differ, and are likely erroneous.)

It remains to count homeomorphically irreducible trees, that is, trees where no node has degree 2.

We start by counting node-rooted trees where no node has exactly one child:

\[ s(x) = x (M s(x) - s(x)) \]

This is nearly what we want. Each non-root node has exactly one parent, so if it does not have exactly one child node, its degree is not 2. However, the root node has no parents, so we’re incorrectly including trees where the root node has degree 2, and incorrectly omitting trees where the root node has degree 1.

We fix this by counting trees where the root node does not have exactly two children, and the other nodes do not have exactly one child:

\[ \begin{align} t^\bullet & = x\left(M s(x) - \frac{s(x)^2 + s(x^2)}{2}\right) \\ & = x\left(M s(x) - s(x) + s(x) - \frac{s(x)^2 + s(x^2)}{2}\right) \\ & = s(x) + x\left(s(x) - \frac{s(x)^2 + s(x^2)}{2}\right) \\ & = (1 + x)s(x) - x\left(\frac{s(x)^2 + s(x^2)}{2}\right) \end{align} \]

We proceed as before to unroot. We count node-and-adjacent-edge-rooted irreducible trees:

\[ t^{\bullet-} = s(x)^2 \]

then edge-rooted irreducible trees:

\[ t^- = \frac{s(x)^2 + s(x^2)}{2} \]

Thus the ordinary power series for the number of irreducible trees is:

\[ t = t^\bullet + t^- - t^{\bullet-} = (1 + x)s(x) + (1 - x)\left(\frac{s(x)^2 + s(x^2)}{2}\right) - s(x)^2 \]

We found 10 irreducible trees of 10 nodes when we drew them, and thankfully this matches the coefficient of \(x^{10}\). Our numbers also agree with the OEIS.

Michael Drmota walks through another way to count unrooted trees (Theorem 6): we start by counting rooted trees with Pólya’s Enumeration Theorem. Just as we must consider rotations and reflections when counting ways of stringing coloured beads on a necklace, we must consider arbitrary permutations of a parent node’s children when counting trees.

The cycle index polynomial for the symmetric group of order \(n\) is:

\[ \sum \frac{x_1^{\lambda_1} ... x_n^{\lambda_n}}{1^{\lambda_1} \lambda_1 ! 2^{\lambda_2}\lambda_2 ! ... n^{\lambda_n} \lambda_n !} \left[ \lambda_1 + 2\lambda_2 + ... + n\lambda_n = n \right] \]

Summing for \(n \ge 0\) yields:

\[ \left(1 + x_1 + \frac{x_1^2}{2!} + ...\right) \left(1 + \frac{x_2}{2} + \frac{x_2^2}{2^2 2!}\right)... \]

which is:

\[ \exp\left(x_1 + \frac{1}{2} x_2 + \frac{1}{3} x_3 + …​\right) \]

This leads to the equation for \(M\). Then we apply a result due to Otter to count unrooted trees. We omit the details; it’s also an ingenious bijection that involves the center node or center edge, but more complicated.