# leaf-labelled unordered, rooted binary trees and perfect matchings

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.

• You can click on both statistics on "search for distribution" to observe the distribution coincidence yourself. Nov 9 '17 at 9:03
• Rewriting the formula for the number of matchings of $[2n]$ with $k$ terminal closers as $M_{2(n-k)} \big(\!\binom{k}{2(n-k)}\!\big) k!$ looks helpful, at least for an enumerative proof. Nov 10 '17 at 8:42
• I am very sorry, but the observation about alignments in the comment I just deleted was completely wrong. Nov 12 '17 at 18:40
• Sketch of an interpretation of the formula in the comment: construct a leaf labelled tree such that for every node the smallest leaf of the left subtree is smaller than the smallest leaf of the right subtree. Begin with a path of $k$ left branches and label the leaf $1$. Then attach trees to each of the $k$ right branches. The relative order of the smallest label in each of these specifies a permutation of $[k]$. The multisubset specifies which labels appear in which subtree and the splitting of a tree in $M_{2(n-k)}$ into $k$ subtrees. It remains to understand how the splitting works. Nov 13 '17 at 10:42
• Here is a refinement: let $\tau$ be the map from perfect matchings to binary trees detailed in Example 5.2.6 of Enumerative Combinatorics 2, let $d_1(T)$ be the depth of label 1 in the tree $T$, let $i(m)$ be the number of initial openers of the matching $m$ and let $i(T)$ the smallest label whose sister is smaller, minus one. Note that $i(m) = i(\tau(m))$. Then the distributions of $\big(d_1(\tau(m)), i(m)\big)$ and $\big(i(T), d_1(T)\big)$ are the same. Put differently, the distribution $\big(d_1(T), i(T)\big)$ is symmetric. Nov 16 '17 at 22:23

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.