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.

  • $\begingroup$ Thank you. For the first formula, what is the motivation for performing the differentiation? $\endgroup$ – ignorantFid Sep 21 '18 at 20:10
  • $\begingroup$ 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. $\endgroup$ – Marko Riedel Sep 21 '18 at 20:28
  • $\begingroup$ I'm sorry, I can't follow the step where you introduce the partition. Can you explain what's happening there? $\endgroup$ – ignorantFid Sep 21 '18 at 21:53
  • $\begingroup$ Additional commentary, submitted. $\endgroup$ – 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.


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.