To what extent is it possible to generalise a natural bijection between trees and $7$-tuples of trees, suggested by divergent series?

Question

This is a cross-post from MSE.

In the paper "Seven Trees In One" by Andreas Blass, a "very explicit" bijection is found between trees and 7-tuples of such trees.

The idea to construct such a bijection stems from looking at some particular divergent series, as mentioned in Chapter 2 of the paper:

To see why seven is special, we first give an argument to establish Theorem 1 in the style of eighteenth-century analysis, where meaningless computations (e.g., manipulating divergent series as though they converged absolutely and uniformly) somehow gave correct results. This argument begins with the observation that a tree either is 0 or splits naturally into two subtrees (by removing the root). Thus the set T of trees satisfies $T = 1 + T^ 2$ . (Of course equality here actually means an obvious isomorphism. Note that the same equation holds also for the variant notions of tree mentioned at the end of Section 1.) Solving this quadratic equation for T, we find $T = 1/2 ± i \sqrt{3}/2 $ . (The reader who objects that this is nonsense has not truly entered into the eighteenth-century spirit.) These complex numbers are primitive sixth roots of unity, so we have $T^ 6 = 1$ and $T^ 7 = T$. And this is why seven-tuples of trees can be coded as single trees.

A more elaborate explanation can be found here.

Mr. Blass does not elaborate a lot on the divergent series he mentioned. This is explained in a bit more detail in a blog post on the "Everything Seminar". The divergent sum of the Catalan numbers (where the $n$'th Catalan number is defined as $C_n = \frac{1}{n+1} \binom{2n}{n} $) is computed by looking at the corresponding generating function of these numbers: $$ T(z) = 1 + z + 2z^2 + 5z^3 + 14z^4 + 42z^5 + \dots $$

It is mentioned in that blog post that the coefficient of $x^n$ is the number of binary rooted trees with $n+1$ leaves. Combining these pieces of information, it can be computed that $$T(z) = \frac{1- \sqrt{1-4z}}{2z} . $$

By plugging in $x=1$, we obtain that $$ 1 + 1 + 2 + 5 + 14 + 42 + \dots "=" \frac{1}{2} - i \frac{\sqrt{3}}{2} = e^{-\pi i/3} . $$

Therefore, we "know" that $$ 1 + 1 + 2 + 5 + 14 + 42 + \dots "=" (1 + 1 + 2 + 5 + 14 + 42 + \dots)^7 $$

This suggested the bijection in the paper by Blass. I am curious, though, whether there are more instances of divergent series that suggest bijections between certain combinatorial objects. For instance, we also have the Fibonacci generating function $$ F(z) = 1 + z + 2z^2 + 3z^3 + 5z^4 + 8z^5 + \dots = \frac{z}{1-z-z^2} . $$ (Here, the $n$'th coefficient is defined as $f_{n} = f_{n-1} + f_{n-2} $, where $f_0 = f_1 = 1$.)

If we let $z$ go to $1$, we find that $$ 1 + 1 + 2 + 3 + 5 + 8 + \dots "=" -1 .$$

Therefore, we find that $$ 1 + 1 + 2 + 3 + 5 + 8 + \dots "=" (1 + 1 + 2 + 3 + 5 + 8 + \dots)^{2k+1} \qquad (1), $$ is true as well, for integer $k > 0 $ .

Question 1: Does this "equality" (1) involving the Fibonacci divergent series admit a combinatorial interpretation as well? Can a bijection between combinatorial structures similar to the one mentioned in Blass' paper be constructed based on this interpretation as well?

Furthermore, we can compute that $$ 1 + 2 + 4 + 8 + 16 + \dots = -1 $$ by means of a generating function as well. (Here, the $n$'th term is of the form $2^n$.) So we have $$ 1 + 2 + 4 + 8 + 16 + \dots = (1 + 2 + 4 + 8 + 16 + \dots)^{2k+1} \qquad (2) $$ for integer $k>0$ as well.

Question 2: Does equality (2) admit a combinatorial interpretation and a corresponding "very explicit" bijection as well?

Question 3: If there are combinatorial interpretations of equalities (1) and (2), could there exist "very explicit" bijections between these different combinatorial structures too?

Answer 1

Let's dissect the case of binary trees first, and see why Fibonacci numbers/powers of two don't work in the same way.

A binary tree is either empty or made of two binary trees joined by a root, hence there is a "natural" bijection $\mathcal{T}\to 1+\mathcal{T}^2$ from the set $\mathcal{T}$ of all binary trees to the union $1+\mathcal{T}^2$, where $1$ denotes $\{\emptyset\}$ and $\mathcal{T}^2$ contains (ordered) pairs of binary trees. By "natural" I mean that the bijection interacts nicely with some standard operations that one may want to perform on the tree, for instance counting its nodes: the number of nodes of the joined tree is simply the sum of the numbers of nodes of the two subtrees, plus one. We can keep track of this through a generating function, which counts all trees in $\mathcal{T}$ with a weight $z^n$ for some formal variable $n$:

$$T(z)=1+z+2z^2+5z^3+14z^4+42z^5+\cdots$$

Keeping track of the number of nodes, the bijection implies that

$$T(z) = 1 + z T(z)^2$$

since a tree is either empty (then it is counted with weight $z^0=1$) or it has a root (contributing a weight $z^1$) and two subtrees. Solving this equation gives

$$T(z)=\frac{1-\sqrt{1-4z}}{2z}$$

which easily leads to the usual closed form formula for Catalan numbers.

In fact, it is possible to go the other way around. Given a closed form for the generating function $T(z)$, we find that $T(z) = 1 + z T(z)^2$, and we can predict the existence of a bijection $\mathcal{T}\to\{\emptyset\}\cup \mathcal{T}^2$ which sends the empty tree to $\emptyset$ and a tree with $n\geq 1$ nodes to a pair of trees with in total $n-1$ nodes. That does not fix the bijection completely, of course. We could imagine a more sensitive generating function whose weights would depend on more than one variable $z_i$. Again, from relations on $T(z_1,\ldots)$ we would deduce the existence of a bijection which preserves some properties of the tree.

Manipulating the complex number $T(1)$ instead of the full $T(z)$ to find relations is no doubt easier, but has two drawbacks: a relation only means that there is a bijection between the corresponding sets, telling us nothing about its naturalness properties, and $T(1)$ as it is is divergent, which means that not all relations lead to actual bijections. For instance, $T(1)^6=1$ has no corresponding bijection since the LHS is infinite and the RHS finite. Thus, $T(1) = T(1)^7$ does not immediately mean that there is a "nice" bijection $\mathcal{T}\to \mathcal{T}^7$. Blass constructed such a bijection starting from $\mathcal{T}\to 1+\mathcal{T}^2$, and Fiore, Leinster mapped out in detail the consequences of having an isomorphism $\mathcal{X}\to p(\mathcal{X})$ for a polynomial $p$ (with non-negative integer coefficients).

Writing the first few terms of the series, we immediately see that $T(z)^7\neq T(z)$, so Blass's bijection cannot preserve the number of nodes. And indeed it doesn't, but the difference between the the total number of nodes of the seven trees and the number of nodes of the joined tree remains bounded. What does changing the number of nodes do to the generating function? $T(z) \to z^k T(z)$ for an integer $k$. So we can expect that using the relation $T(z) = 1 + z T(z)^2$ and the change $T(z) \leftrightarrow z T(z)$ should let us go from $T(z)$ to $T(z)^7$ in a finite number of steps. In effect, considering $T(z)$ and $zT(z)$ to be equivalent is the same as taking $z=1$, that is, ignoring the number of nodes. Allowing only a finite number of steps $T(z)\to z^k T(z)$ means that the number of nodes changes by a bounded amount $C$. One can check painfully that there is indeed such a sequence of steps, which implies the existence of a nice bijection.

Note that the existence of this bijection implies that the number of septuplets of trees with $n$ nodes in total is less than the number of trees with $n+C$ nodes. If someone works out an independent proof that this is the case, I think it would benefit this answer.

---

The Fibonacci generating function

$$F(z)=1+z+2z^2+3z^3+5z^4+8z^5+\cdots=\frac{1}{1-z−z^2}$$

counts the number of ways to split $n$ into parts of size $1$ or $2$, in other words it counts the number of sequences of $1$ and $2$ with sum $n$. The geometric series

$$\tilde{F}(z)=1+2z+4z^2+8z^3+\cdots=\frac{1}{1-2z}$$

counts the number of words of length $n$ in an alphabet of $2$ letters, in other words it counts sequences of $1$ and $2$ with $n$ digits. A generating function which encapsulates both is

$$G(z_1,z_2)=\frac{1}{1-z_1-z_2}$$

whose coefficient of $z_1^{n_1} z_2^{n_2}$ is the number of sequences of $n_1$ $1$ and $n_2$ $2$. The Fibonacci series weighs $2$ twice as much as $1$, so $F(z)=G(z,z^2)$. The geometric series weighs them equally, thus $\tilde{F}(z)=G(z,z)$. In both cases, taking $z=1$ corresponds to $G(1,1)=-1$.

The way I described the two generating functions, I think it's obvious that there is a natural bijection between the sets counted by $1+1+2+3+5+8+13+\cdots$ and $1+2+4+8+16+\cdots$. Since $G(1,1)=-1$, it's natural to ask whether $G(1,1)^3=G(1,1)$ correspond to any natural bijection. I think the answer is no.

First, I failed to write an analogue of $T(z)=1+zT(z)^2$ for $T$ that we could use for $G$. Essentially all I could write boiled down to $G(z_1,z_2)=1+(z_1+z_2)G(z_1,z_2)$, which states that a sequence of digits is either empty or it is $1$ or $2$ followed by a sequence of digits. This would seem promising, but it is linear in $G$, which means that applying it any number of times starting from $G(z_1,z_2)$ will never produce quadratic terms or higher powers of $G$. We will never get $G=G^3$.

Why are we failing in this way? Well, the number of $k$-tuples of sequences of digits has the generating function

$$1/(1-2z)^k=\sum_{n\geq 0} \binom{n+k-1}{n} 2^n z^n$$

which tells us that the number of $k$-tuples of sequences with in total $n$ digits is $\binom{n+k-1}{n} 2^n$. This is asymptotically $\# n^k 2^n$ for large $n$, where $\#$ is some number. The number of $(k-1)$-tuples of sequences with in total $n+C$ digits is $\# n^{k-1} 2^n \ll \# n^k 2^n$. Therefore, it is impossible to package $k$ sequences into fewer sequences of digits under the constraint that the total number of digits does not grow by more than a bounded shift $n\to n+C$.