Binary tree bijection

Question

I've been studying for an up coming exam in combinatorics and I came across something interesting by accident.

We have the two combinatorial constructions: $$\mathbb{U}\cong SEQ(\mathbb{ZU})$$ And $$\mathbb{T}\cong \mathbb{Z}*SEQ_2(\mathbb{T})+\epsilon$$

The first one I interpret as planar trees where the size is determined by number of edges.

The second one (and I need to confirm if this is correct), I'm interpreting as planar complete binary trees where size relates to the number of internal nodes (nodes that are not leaves).

When you convert these to generating fucntions:

$$U(z)=\frac{1}{1-zU(z)}$$ Which rearanges to: $$U(z)=zU^2(z)+1$$ And $$T(z)=zT^2(z)+1$$ Clearly the two generating functions are the same, so there must be a bijection between the two sets I interpret them to represent.

I'd love to spend time working it out, but I've got exams to cram for, so I was wondering if someone could enlighten me specifically using my interpretations (or the closest thing if I've got them wrong). I can't afford to waste any more time on it!

EDIT I forgot to mention that $\mathbb{Z}$ is the atomic class, and $\epsilon$ is the empty set, and that these are unlabelled objects.

EDIT 2 Fixed an error in the expression for $\mathbb{T}$

Answer 1

I agree with your interpretation of the second construction. The most natural interpretation of the first, however, seems to me to be ordered plane forests of rooted trees, where size is determined by the number of nodes. Ah, I see: that’s the same as rooted plane trees with size determined by the number of nodes not counting the root, which in turn is equivalent to your interpretation.

In The Book of Numbers J.H. Conway and R.K. Guy illustrate the desired bijection as follows. First, here are the $5$ rooted plane trees with $3$ edges. The vertices have been labelled with the integers $2,3,4$, and $5$, and sister vertices are shown with multiplication signs between them.

         2  
         |  
         3         3 × 2          3                2  
         |          \ /           |                |  
         4           4            4 × 2        4 × 3        4 × 3 × 2  
         |           |             \ /          \ /           \ | / 
         5           5              5            5              5    

We can interpret each tree as representing an exponentiation:

$$\begin{array}{lll} \large5^{4^{3^2}}=5^{\left(4^{\left(3^2\right)}\right)}&&5^{4^{3\cdot 2}}=5^{\left(\left(4^3\right)^2\right)}\\ 5^{4^3\cdot2}=\left(5^{\left(4^3\right)}\right)^2&&5^{4\cdot3^2}=\left(5^4\right)^{\left(3^2\right)}\\ 5^{4\cdot3\cdot2}=\left(\left(5^4\right)^3\right)^2 \end{array}$$

In each entry the expression on the left matches the tree, while the expression on the right is fully parenthesized (apart from the outermost pair of parentheses). The fully parenthesized versions are then easily converted to binary trees by adding $3$ internal nodes, especially if exponentiation is replaced by an arbitrary binary operation $*$:

$$\begin{array}{lll} 5*(4*(3*2))&&5*((4*3)*2)\\ (5*(4*3))*2&&(5*4)*(3*2)\\ ((5*4)*3)*2 \end{array}\tag{1}$$

     3   2     4   3           4   3                     5   4  
      \ /       \ /             \ /                       \ /  
   4   *         *   2       5   *         5   4 3   2     *   3  
    \ /           \ /         \ /           \ /   \ /       \ /  
 5   *         5   *           *   2         *     *         *   2  
  \ /           \ /             \ /            \ /            \ /  
   *             *               *              *              *

It’s not hard to see how to extend this example to the general case, and the forms at $(1)$ make it clear that we’re dealing with the Catalan numbers.