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?

  • $\begingroup$ 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? $\endgroup$ Mar 28, 2017 at 3:24
  • 1
    $\begingroup$ @SamHopkins : That was my first thought too and I'm probably just being an idiot, but I don't see how to do that. $\endgroup$ Mar 28, 2017 at 3:34
  • 2
    $\begingroup$ I just noticed that math.stackexchange.com/questions/2511943/… is essentially the same question. $\endgroup$ Nov 14, 2017 at 15:01

1 Answer 1


I think the following might do the trick:

Erdös, Péter L., A new bijection on rooted forests, Discrete Math. 111, No.1-3, 179-188 (1993). ZBL0785.05049.

  • $\begingroup$ 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. $\endgroup$ Nov 19, 2017 at 19:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .