Two Recurrences for Counting Rooted Trees

A rooted tree is a tree with a special node called the root. The number of 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. I was surprised that they can produce the same sequence despite appearing so different. \[ 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) \]

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} \).

The image below shows how the second formula can be derived with an example for \(a_{25}\). Every node that is directly attached to the root is the root of a subtree, and the subtrees are arranged in a partition. Changing the partition changes the tree. You can switch out subtrees for another subtree with the same number of nodes, to get a new tree without changing the partition.

Using the program below I have verified that both recurrence relations are correct up to at least the \(30^\text{th}\) term.