# Two Recurrences for Counting Rooted Trees

The number of unlabeled rooted trees with $$n$$ nodes is given by the sequence A000081 in the OEIS. They provide the following recurrence relation:

$$a_{n+1} = \frac{1}{n} \sum_{k=1}^n \left( \sum_{d \mid k} d \cdot a_d \right) a_{n-k+1}$$

I came up with a different one:

$$a_{n+1} = \sum_{ \left( p_1^{r_1} \, \ldots \, p_\ell^{r_\ell} \right) \, \vdash \, n } \left( \prod_{i=1}^{\ell} \left(\!\!\binom{a_{p_i}}{r_i}\!\!\right) \right)$$

I have verified that this is correct up to at least $$a_{30}$$. The sum is over all partitions of $$n$$, and $$\left( p_1^{r_1} \ldots p_\ell^{r_\ell} \right)$$ is the frequency representation of a partition. $$\left(\!\binom{n}{k}\!\right)$$ is the multiset coefficient. It represents the number of ways to choose $$k$$ elements out of $$n$$ allowing repetition, and is equal to $$\binom{n+k-1}{k}$$.

Is there a way to show that the two equations are equivalent*? Where does the first equation come from? I found this question which seems relevant.

* The two equations can produce different sequences when $$a_1 \neq 1$$.

We have for unlabeled rooted trees $$\mathcal{T}$$ the combinatorial class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{T} = \mathcal{Z} \times \textsc{MSET}(\mathcal{T})$$

wich just says that a tree is a multiset of trees, possibly empty, attached to a root node. This immediately yields a functional equation via the exponential formula, and which is

$$T(z) = z \exp\left(\sum_{\ell\ge 1} \frac{T(z^\ell)}{\ell}\right).$$

Differentiate to obtain

$$T'(z) = \exp\left(\sum_{\ell\ge 1} \frac{T(z^\ell)}{\ell}\right) + z \exp\left(\sum_{\ell\ge 1} \frac{T(z^\ell)}{\ell}\right) \left(\sum_{\ell\ge 1} T'(z^\ell) z^{\ell-1} \right) \\ = \frac{1}{z} T(z) + T(z) \sum_{\ell\ge 1} T'(z^\ell) z^{\ell-1}.$$

With $$t_n = [z^n] T(z)$$ (for the notational choice observe that we are working with cycle indices here and $$a_n$$ might be taken for one of their variables) we now extract the coefficient on $$[z^n]$$ to get,

$$(n+1) t_{n+1} = t_{n+1} + \sum_{q=0}^{n-1} ([z^{n-q}] T(z)) \left([z^q] \sum_{\ell\ge 1} T'(z^\ell) z^{\ell-1} \right) \\ = t_{n+1} + \sum_{q=0}^{n-1} t_{n-q} \left(\sum_{\ell\ge 1} [z^{q+1-\ell}] T'(z^\ell) \right).$$

Here we must have that $$q+1-\ell$$ is a multiple of $$\ell$$ which means $$q+1$$ is a multiple of $$\ell.$$ This yields

$$n t_{n+1} = \sum_{q=0}^{n-1} t_{n-q} \left(\sum_{\ell|q+1} [z^{q+1-\ell}] T'(z^\ell) \right) \\ = \sum_{q=0}^{n-1} t_{n-q} \left(\sum_{\ell|q+1} [z^{(q+1)/\ell-1}] T'(z) \right) \\ = \sum_{q=0}^{n-1} t_{n-q} \left(\sum_{\ell|q+1} ((q+1)/\ell) t_{(q+1)/\ell}\right) \\ = \sum_{q=0}^{n-1} t_{n-q} \left(\sum_{\ell|q+1} \ell t_{\ell}\right).$$

With a shift of the sum variable we have obtained the recurrence

$$\bbox[5px,border:2px solid #00A000]{ t_{n+1} = \frac{1}{n} \sum_{q=1}^{n} t_{n+1-q} \left(\sum_{\ell|q} \ell t_{\ell}\right).}$$

For the second recurrence we observe that the multisets in the combinatorial class in fact only act on sets of trees with the same number of nodes. A different numbers of nodes automatically distinguishes two trees. Therefore we may write

$$\mathcal{T} = \mathcal{Z} \times \prod_{m\ge 1} \textsc{MSET}(\mathcal{T}_{=m})$$

where $$\mathcal{T}_{=m}$$ is the class of unlabeled rooted trees on $$m$$ nodes with OGF $$t_m z^m.$$ Doing another coefficient extraction we thus obtain

$$t_{n+1} = [z^n] \prod_{m\ge 1} \exp\left(\sum_{\ell\ge 1} \frac{t_m z^{\ell m}}{\ell}\right) \\ = [z^n] \prod_{m\ge 1} \exp\left(t_m \sum_{\ell\ge 1} \frac{z^{\ell m}}{\ell}\right) \\ = [z^n] \prod_{m\ge 1} \exp\left(t_m \log\frac{1}{1-z^m} \right) \\ = [z^n] \prod_{m\ge 1} \frac{1}{(1-z^m)^{t_m}}.$$

Now from the terms with $$m\gt n$$ clearly only the constant zerm contributes to $$[z^n]$$ for an answer of

$$\bbox[5px,border:2px solid #00A000]{ t_{n+1} = [z^n] \prod_{m=1}^n \frac{1}{(1-z^m)^{t_m}}.}$$

Let $$p\;\vdash n$$ with value $$p_j$$ having multiplicity $$r_j$$ as in OP's notation. Here we have $$p_j = m$$ so that the contribution from the corresponding term in the product is by the binomial theorem

$$[z^{mr_j}] \frac{1}{(1-z^m)^{t_m}} = [z^{r_j}] \frac{1}{(1-z)^{t_m}} = {r_j + t_m - 1 \choose t_m-1} = {r_j + t_m - 1 \choose r_j} \\ = {t_{p_j} + r_j - 1\choose r_j},$$

and we have proven the second formula, which, it must be said, almost follows by inspection.

Commentary, per request. We have immediately from first principles that $$1/(1-z^m)$$ is the OGF of a multiset drawn from one object of size $$m.$$ Thus if we have $$t_m$$ different objects of size $$m$$, the multisets drawn from them have OGF $$1/(1-z^m)^{t_m}.$$ Hence the second formula simply says that a rooted unlabeled tree on $$n+1$$ nodes consists of multisets of trees on $$m$$ nodes with $$1\le m\le n$$ attached to the root. Now when we extract the coefficient on $$[z^n]$$ we must partition $$n$$ into a contribution $$q$$ from the $$n$$ terms, possibly zero. Note however that $$1/(1-z^m)^{t_m}$$ contains all multiples of $$m$$ as exponents in its series expansion, and these terms are clearly unique, every multiple occuring one time. This means we see every partition $$p\; \vdash n$$ (which is a sum of unique multiples of the $$m$$) exactly once, with the term $$p_j^{r_j}$$ being contributed by $$m=p_j$$ where $$q=m r_j$$ (Here the values that do not appear in the partition have $$r_j=0$$.) This establishes a one-to-one correspondence between partitions and contributions to $$[z^n].$$ The formula by OP then follows by extracting the coefficient $$[z^{mr_j}] \frac{1}{(1-z^m)^{t_m}}$$ using the binomial theorem and multiplying the results.

• Thank you. For the first formula, what is the motivation for performing the differentiation? – ignorantFid Sep 21 '18 at 20:10
• Differentiation will keep the exponential term, which may be replaced using the functional equation, making for a simpler recurrence. This technique is used on many types of trees, labeled and not labeled. – Marko Riedel Sep 21 '18 at 20:28
• I'm sorry, I can't follow the step where you introduce the partition. Can you explain what's happening there? – ignorantFid Sep 21 '18 at 21:53
• Additional commentary, submitted. – Marko Riedel Sep 22 '18 at 18:25

The second formula in A000081 is simply equivalent to $$\frac{A(x)}x = \sum_{n=0}^\infty a_{n+1} x^n = \prod_{k=1}^\infty (1-x^k)^{-a_k} \tag{1}$$ which states that the Euler transform of the sequence is the sequence shifted by one. This is equivalent to the decomposition of a rooted tree with its root removed into a forest of rooted trees. The partition interpretation of the infinite product implies your second equation since $$(1-x)^{-a} = \sum_{n=0}^\infty \left(\!\! \binom{a}{n} \!\!\right) x^n. \tag{2}$$

The first formula in A000081 is simply equivalent to $$C(x) := \frac{A(x)}x = \sum_{n=0}^\infty a_{n+1} x^n = \exp(B(x)), \tag{3}$$ where $$B(x) := \sum_{k=1}^\infty \frac{A(x^k)}k , \quad x \frac{d}{dx} B(x) = \sum_{n=1}^\infty x^n \sum_{d|n} d\,a_d. \tag{4}$$ Now, using the operator $$\, f(x) \mapsto x \frac{d}{dx} f(x), \,$$ on equation $$(3)$$ we get $$x \frac{d}{dx} C(x) = \sum_{n=0}^\infty n\,a_{n+1} x^n = C(x)\, x \frac{d}{dx} B(x) . \tag{5}$$ which is equivalent to your first formula by equating power series coefficients.

Finally, given any sequence $$\, \{f_1,f_2,\dots\}, \,$$ and its generating function $$\, F(x),\,$$ the following is true $$x \frac{d}{dx} \sum_{k=1}^\infty \frac{F(x^k)}k = \sum_{n=1}^\infty x^n \sum_{d|n} d\,f_d. \tag{6}$$ Apply this result with $$\, F=A \,$$ in equation $$(4)$$ to get your first equation.