# Bijective proof of formula for rooted binary forests

For $n\ge 1$, let $f(n)$ be the number of rooted complete (unordered) binary trees with $n$ leaves labeled from $1$ to $n$ ("complete binary" means that every vertex has either $0$ or $2$ children and "unordered" means that the we do not specify which child is the left child or the right child). Then it is well known (e.g., Example 5.2.6 of Stanley's Enumerative Combinatorics 2) that the exponential generating function of $f(n)$ is given by $$F(x) := \sum_{n\ge1} f(n)\, {x^n\over n!} = 1 - \sqrt{1-2x}.$$

Now fix a positive integer $r$ and for $n\ge r$, let $f(n,r)$ be the number of rooted complete binary forests with $n$ leaves labeled $1$ to $n$, and $r$ roots labeled $n+1$ to $n+r$. By generatingfunctionology (e.g., Proposition 5.1.3 of Stanley's Enumerative Combinatorics 2), $$\sum_{n\ge r} f(n,r)\, {x^n\over n!} = F(x)^r = (1 - \sqrt{1-2x})^r.$$ This equation yields a formula for $f(n,r)$, and in fact we have:

Theorem. $$f(n,r) = {r(2n-r-1)!\over 2^{n-r}(n-r)!}.$$

The current proof I have of the Theorem simply notes that the generating function $F(x)^r$ coincides with a generating function for the Catalan tree, for which the coefficients are known to obey the above formula. My question is:

Is there a bijective proof of the Theorem?

• In Example 5.2.6 that you cite, Stanley explains a bijective interpretation of the first result you mention. Presumably this can be modified to handle the case of forests with $r$ roots? Mar 28 '17 at 3:24
• @SamHopkins : That was my first thought too and I'm probably just being an idiot, but I don't see how to do that. Mar 28 '17 at 3:34
• I just noticed that math.stackexchange.com/questions/2511943/… is essentially the same question. Nov 14 '17 at 15:01

• Yes, I think that does it! To be more explicit, $f(n,r)=r!b(n,r)$ where $b$ is given in Corollary 3.6 of this paper, and it looks like the paper's proof of Corollary 3.6 is bijective. Nov 19 '17 at 19:24