Would've been a better question for Christmas than Thanksgiving, but alas...


Let $t\_n$ denote the number of rooted, unlabeled trees on $n$ vertices ([OEIS A000081](http://oeis.org/A000081)). These are the isomorphism classes of rooted trees under root-preserving isomorphisms. Let $T(z) = \sum\_{n\geq 1} t\_n z^n$ be the corresponding generating function. In 1937, using his [enumeration under symmetry theorem](https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem), Pólya showed that
$$ T(z) = z \prod\_{i=1}^{\infty}e^{\frac{T(z^i)}{i}}.$$
By differentiating this identity one obtains the recurrence
$$ (n-1)\cdot t\_n = \sum\_{i=1}^{n-1}t\_{n-i}\sum\_{m \mid i}mt\_{m}$$
for $n> 1$. This is such a nice recurrence that I wonder:


**Question**: Is there a bijective proof of this recurrence for $t\_n$?



Bijective proof of recurrence for rooted unlabeled trees
**Late edit**: having now read through the OP comments, I can see that my proof is essentially a carbon copy of @darij.grinberg's approach (although my derivation was independent). I'm okay to delete this answer once/if darij chooses to post theirs.


Pick a canonical ordering of unlabelled rooted trees, say, with lexicographical comparison of tuples $(n, T\_1, \ldots, T\_k)$, where $n$ is the number of vertices, $T\_1, \ldots, T\_k$ is the non-descending sequence of children subtrees. Throughout $T, T\_1, T\_2$ are unlabelled rooted trees in canonical form (that is, subtrees of any vertex are ordered as above).


Let $A\_n$ be the set of pairs $(T, v)$ with $|T| = n$, $v$ is a non-root vertex of $T$. Also, let $B\_n$ be the set of tuples $(T\_1, T\_2, k, u)$ such that $|T\_1| + k|T\_2| = n$, $u$ is a vertex of $T\_2$. Observe that $|A\_n|$ and $|B\_n|$ are LHS and RHS of the recurrence in OP, more readily seen by rewriting $(n - 1)t\_n = \sum\_{m = 1}^{n - 1}mt\_m \sum\_{0 < km < n} t\_{n - km}$.


The bijection between $A\_n$ and $B\_n$ is as follows:


* we associate $(T\_1, T\_2, k, u)$ to $(T, v)$ by:
	+ $T\_2$ = the subtree of $T$ containing $v$,
	+ $u$ = the respective vertex of $T\_2$,
	+ $k$ = the number of children subtrees of $T$ isomorphic to $T\_2$ not later than the copy containing $v$ in the ordered sequence of children subtrees,
	+ $T\_1$ = the result of removing the $k$ children subtrees from $T$.
* we associate $(T, v)$ to $(T\_1, T\_2, k, u)$ by inserting $k$ copies of $T\_2$ as children subtrees of the root of $T\_1$ (and naming the result $T$), and picking the respective vertex $u$ in the $k$-th copy as $v$.


