leaf-labelled unordered, rooted binary trees and perfect matchings

Question

While playing with findstat.org, I noticed the following coincidence:

The number of leaf labelled unordered rooted binary trees with $n+1$ leaves $\{1,\dots,n+1\}$, with the leaf labelled $1$ at distance $k$ to the root (http://findstat.org/St001041)

equals

the number of perfect matchings of $\{1,\dots,2n\}$ with $k$ terminal closers (http://findstat.org/St000838).

The distribution of these numbers is given at http://oeis.org/A102625, and I expect that a computational proof would not be very hard to find.

However, I am interested in a bijective proof.

UPDATE: belated, I should mention that I eventually found a bijective proof but only have a rather brief writeup currently.

Answer 1

I unfortunately got stuck, but I am leaving my work here anyway in case it helps someone else. Happy to delete this if the community feels it is not worthy of being an answer.

---

Your first link references a book that provides a bijection between the following two sets.

• unordered rooted binary trees with $n+1$ labeled leaves
• matchings of $\{1,\ldots,2n\}$

Note that a binary tree with $n+1$ leaves will have $2n$ non-root nodes, which hints that the above bijection involves labeling of the non-root nodes of a tree. Indeed, this is what the book describes.

I will defer the details to the book, but roughly the bijection is as follows. Take a binary tree with $n+1$ labeled leaves. We will label the remaining non-root nodes with $n+2,\ldots,2n$ in the following way.

• Consider all unlabeled non-root nodes whose two children are both labeled, and label as $n+2$ the one that has a child with the smallest label.
• Repeat this procedure and label the next node as $n+3$, and so on.

Then to convert these node labelings to a matching on $\{1, \ldots, 2n\}$, just take each pair of sibling nodes' labels as a pair in your matching.

Here is an example from the book, when $n=6$. Try starting with only the $7$ leaves labeled, and then complete the labeling for the rest of the non-root nodes.

Note that one needs to check this is a bijection; I will not do so here.

---

Now, let us consider your original question, which asks for a bijection between the following two sets.

• unordered rooted binary trees with $n+1$ labeled leaves, and leaf "$1$" at distance $k$ from root
• matchings of $\{1, \ldots, 2n\}$ with $k$ terminal closers

Unfortunately, the above bijection does not immediately solve the problem. For example, the matching $(1,2),(3,4),(5,6)$ has one terminal closer, but in the corresponding tree given by the bijection, leaf $1$ is distance $2$ from the root.

Thus, I suspected one can find some intermediate bijection that, when combined with the tree-matching bijection described above, will produce your desired bijection of these last two sets. But I was unsuccessful in actually finding one that worked.

Some closing remarks and possible bijection building-blocks:

• One can consider $k$ initial openers, rather than $k$ terminal closers
• One can consider the depth of some other leaf, rather than leaf $1$
• More generally, one can permute the items in the matching before/after using the tree-matching bijection.
• The tree corresponding to a matching with $k$ terminal closers has a path $\text{root} \to 2n \to (2n-1) \to \cdots \to (2n-k+1)$, and the node $2n-k$ is a sibling of one of these nodes.