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$.
 A: 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.
A: 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.
