Counting free trees from rooted trees.

Question

The number of free trees on n vertices is given in Sloane's OEIS A000055. the number of rooted trees is A000081. If t(x) is the ordinary generating function (o.g.f.) for free trees and T(x) is the o.g.f. for rooted trees then:

t(x) = 1 + T(x) - (T(x)^2 - T(x^2))/2.

I am trying to understand the equation in terms of the symbolic method of derivation of generating functions as described in Flajolet and Sedgewick, Analytic Combinatorics. I recognize (T(x)^2 - T(x^2))/2 as the o.g.f. for the number of unordered distinct pairs of rooted trees. I do not understand how subtracting this from T(x) gives us the o.g.f. for free trees. I know that every tree is centered or bi-centered and I think this might have something to do with the explanation.

Answer 1

Here we show OPs formula using the dissimilarity theorem for trees. In the following we also give some basic information around this theorem to ease reading.

We denote with

• $\mathcal{U}$ the class of unrooted unlabelled non-plane trees. With the corresponding generating function $U(z)$ (see A000055).

\begin{align*} U(z)&=z+z^2+z^3+2z^4+3z^5+6z^6+11z^7+23z^8+47z^9\\ &\qquad+106z^{10}+235z^{11}+551z^{12}+1301z^{13}+3159z^{14} \end{align*}

• $\mathcal{R}$ the class of rooted unlabelled non-plane trees. With the generating function $R(z)$ (see A000081). \begin{align*} R(z)&=z+z^2+2z^3+4z^4+9z^5+20z^6+48z^7+115z^8+286z^9\\ &\qquad+719z^{10}+1842z^{11}+4766z^{12}+12486z^{13}+32973z^{14} \end{align*}

Unrooted trees are also called sometimes free trees (see e.g. Analytic Combinatorics VII.25, p.480 by P. Flajolet and R. Sedgewick).

Note that contrary to OEIS $U(z)$ does not contain the empty unrooted tree. This is in accordance with the formula we show below and which is stated this way quite often in the literature.

Otter's formula

The following is valid \begin{align*} U(z)=R(z)-\frac{1}{2}\left(R(z)^2-R(z^2)\right)\tag{1} \end{align*}

This formula named after R. Otter was presented in The number of trees (1948).

The following proof is according to Analytic Combinatorics VII.26 by P. Flajolet and R. Sedgewick. The authors refer in their proof to Combinatorial Species and Tree-like Structures by F. Bergeron, G. Labelle and P. Leroux. Otter's formula is stated there as Theorem 1 in section 4.1. The Dissymmetry Theorem for trees.

Preliminaries

Let $\mathcal{U}^\bullet$ (and $\mathcal{U}^{\bullet-\bullet}$) be the class of unrooted trees with one vertex (respectively, one edge) distinguished. We have \begin{align*} \mathcal{U}^\bullet\cong\mathcal{R}\qquad\text{ and }\qquad\mathcal{U}^{\bullet-\bullet}\cong \operatorname{SET}_2(\mathcal{R})\tag{2} \end{align*}

The equivalence relation $\mathcal{U}^\bullet\cong\mathcal{R}$ is obvious. We can associate to each unrooted tree with a distinguished edge in $\mathcal{U}^{\bullet-\bullet}$ an unordered not necessarily distinct pair of elements of $\mathcal{R}$ by breaking the tree at the edge, giving the right hand side of (2).

A class of unordered pairs of elements $\operatorname{SET}_2(\mathcal{B})$ fulfills the combinatorial isomorphism \begin{align*} \operatorname{SET}_2(\mathcal{B})+\operatorname{SET}_2(\mathcal{B})-\Delta(\mathcal{B}\times\mathcal{B})\cong \mathcal{B}\times\mathcal{B}\tag{3} \end{align*} (we may think of lower triangle + upper triangle - diagonal is equal the square). If $B(z)$ is the generating function of the class $\mathcal{B}$, then since \begin{align*} \Delta(\mathcal{B}\times\mathcal{B}):=\{(\beta,\beta)|\beta\in\mathcal{B}\} \end{align*} we obtain \begin{align*} \Delta_B(z)=\sum_{(\beta,\beta)\in\mathcal{B}}z^{2|\beta|}=B(z^2) \end{align*} If we set $\mathcal{A}\equiv \operatorname{SET}_2(\mathcal{B})$ we obtain according to (3) \begin{align*} A(z)&=\frac{1}{2}\left(B(z)^2+B(z^2)\right) \end{align*}

Otter's formula can be shown via the following combinatorial isomorphism

Dissimilarity theorem for trees

The dissimilarity theorem for trees states the validity of \begin{align*} \mathcal{U}^\bullet+\mathcal{U}^{\bullet-\bullet}\cong\mathcal{U}+\left(\mathcal{U}^\bullet\times\mathcal{U}^\bullet\right)\tag{4} \end{align*}

In order to prove this theorem, we recall a diameter of an unrooted tree is a simple path of maximal length. If the length of any diameter is even, call centre its mid-point, otherwise, call bi-centre its mid-edge. Note for each tree there is either one centre or one bi-centre.

The left-hand side of (4) corresponds to trees that are pointed either at a vertex ($\mathcal{U}^\bullet$) or an edge ($\mathcal{U}^{\bullet-\bullet}$).

The term $\mathcal{U}$ on the right-hand side corresponds to cases where the pointing happens to coincide with the canonical centre or bicentre.

If there is no coincidence, then, an ordered pair of trees results from a suitable surgery of the pointed tree.

• If the tree is pointed at a vertex $s$ different from the center, let $p$ be the vertex adjacent to $s$, in the direction of the center (if the center is an edge to which $s$ belongs, $p$ is the other vertex of this edge). By cutting the edge joining $s$ and $p$, one obtains an ordered pair of rooted trees, the left one with root $s$ and the right one with root $p$.

• If the tree is pointed at an edge, different from the center, let $p$ be the vertex of the distinguished edge nearest to the center. Then cut the edge and place on the left the rooted tree with root $p$, and on the right the other part.

Note:

• There is a typo in P. Flajolet's book regarding the dissimilarity theorem for trees (4). The right-hand side of the formula there is incorrectly stated as $\mathcal{U}+\left(\mathcal{U}\times\mathcal{U}\right)$ instead of $\mathcal{U}+\left(\mathcal{U}^\bullet\times\mathcal{U}^\bullet\right)$ (see formula (59) at page 481).

• The surgery argument is from Theorem 1 in F. Bergeron's book.

Putting all together: Using the preliminaries together with the dissimilarity theorem we obtain \begin{align*} \mathcal{U}^\bullet+\mathcal{U}^{\bullet-\bullet}\cong\mathcal{U}+\left(\mathcal{U}^\bullet\times\mathcal{U}^\bullet\right)&\qquad\qquad \text{this is }(4)\\ \mathcal{R}+ \operatorname{SET}_2(\mathcal{R})\cong\mathcal{U}+\left(\mathcal{R}\times\mathcal{R}\right)&\qquad\qquad \text{due to }(2) \end{align*} and since the generating function of the class $\operatorname{SET}_2(\mathcal{R})$ is according to (3) \begin{align*} \frac{1}{2}\left(R(z)^2+R(z^2)\right) \end{align*} we finally get Otter's formula \begin{align*} R(z)+\frac{1}{2}\left(R(z)^2+R(z^2)\right)&=U(z)+R(z)^2\\ U(z)&=R(z)-\frac{1}{2}\left(R(z)^2-R(z^2)\right) \end{align*} and the claim follows.