13
$\begingroup$

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$?

$\endgroup$
14
  • $\begingroup$ I'd really want $\left(n-1\right) \cdot t_n$ to be something like the number of unlabeled rooted trees with one chosen non-root vertex $v$. In that case, we could split up such a tree into the child-tree of the root that contains $v$, along with all other child-trees of the roots that are isomorphic to it, and the tree that remains (including the root). That should give the right hand side (the $t_m$ counts the possibilities for the former child-tree; the $m$ the options for the location of $v$ in it; the $t_{n-i}$ counts the remaining trees). Unfortunately, it isn't, because automorphisms ... $\endgroup$ Nov 26, 2021 at 0:44
  • $\begingroup$ ... of the tree can move $v$ around. But there should be a way to deal with this, as I suspect it's a common issue with unlabeled objects and looks solvable. I suspect that, rather than counting unlabeled trees, we should really count labeled trees modulo some group actions. $\endgroup$ Nov 26, 2021 at 0:44
  • $\begingroup$ Wait, what exactly is an unlabeled tree? Are the children of a node a list or a multiset? $\endgroup$ Nov 26, 2021 at 0:48
  • $\begingroup$ Two rooted unlabeled trees are considered the same if there is an isomorphism between them which maps the root to the root. $\endgroup$ Nov 26, 2021 at 0:48
  • $\begingroup$ Ah, that's what I thought right away (was merely confused by the different use in algebraic combinatorics, where "labeled" is an extra layer of labels). If so, I'm thinking we could use another way to remove the "up to isomorphism" part: We pin each unlabeled tree to a given form by arranging all children of each node in increasing order (according to some arbitrary but fixed order on trees). Let me call a rooted tree in which the children of each node are arranged in increasing order from left to right a well-increasing tree (stupid name, but sufficiently novel to avoid confusion). Now, ... $\endgroup$ Nov 26, 2021 at 0:50

1 Answer 1

6
$\begingroup$

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$.
$\endgroup$
6
  • $\begingroup$ Sorry if there was a sufficient resolution in the comments already, it was a bit hard to follow. $\endgroup$ Nov 27, 2021 at 11:39
  • $\begingroup$ Indeed, I think this is exactly what Darij explained. $\endgroup$ Nov 27, 2021 at 13:28
  • $\begingroup$ Yep, that looks like my proof, explained sequentially rather than as a mess of comments :) I was trying to do it myself, but getting confused about the notion of a vertex. OTOH, I think your equality $(n - 1)t_n = \sum_{m = 1}^{n - 1}mt_m \sum_{0 < km < n} t_{n - km}$ is slightly buggy (some $m$s should be $n-m$s, right?). $\endgroup$ Nov 27, 2021 at 15:36
  • $\begingroup$ @darijgrinberg I don't think so? Here $km$ functions as $i$ in the OP formula. The actual inner summation is by $k$ via notation abuse. $\endgroup$ Nov 27, 2021 at 15:45
  • 1
    $\begingroup$ Had similar (although more general) question, didn't find this question, had to reinvent the same idea myself: math.stackexchange.com/questions/4494715/… $\endgroup$ Nov 6, 2022 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.