Combinatorics – Bijective Proof of Recurrence for Rooted Unlabeled Trees

bijective-combinatoricsco.combinatoricsenumerative-combinatoricstrees

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). 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, 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$?

Best Answer

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$.
Related Question