Two Recurrences for Counting Rooted Trees

Question

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$.}

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

Answer 2

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.