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 '17 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 '17 at 3:34
  • 2
    $\begingroup$ I just noticed that math.stackexchange.com/questions/2511943/… is essentially the same question. $\endgroup$ Nov 14 '17 at 15:01

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 '17 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.