MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given $k,n\in\mathbf{N}$ with $n\ge k$, define the set $\mathcal{F}(k,n)$ of $(k,n)$-forests of binary rooted trees (where a $(k,n)$-forest is a collection of $k$ rooted trees, which have a totality of $n$ leaves).

My aim is to count the cardinality of $\mathcal{F}(k,n)$.

For example it is well known that $|\mathcal{F}(1,n+1)|$ is given by the $n$-th Catalan number $c_n=\frac{1}{n+1}{{2n}\choose{n}}$.

Using generating functions (and something like Maple), we have an explicit way to obtain any $f_{k,n}:=|\mathcal{F}(k,n)|$: if $C(z)$ denotes the generating function of $c_n$, then the $n-k$-th coefficient of $C(z)^k$ is exactly $f_{k,n}$.

Isn't there any explicit formula for such numbers?

Is there an asymptotic estimate and is it a good one?

share|cite|improve this question
I think you want to use Lagrange inversion. See Stanley ECII, Theorem 5.4.2. – Martin Rubey Jul 13 '10 at 15:34
up vote 8 down vote accepted

The number of $(k,n)$-binary forests is the $(n-1,n-k)$ entry of Catalan's triangle. Thus the formula is: $$ f_{k,n} \:=\: \frac{\:k\:}{n}\binom{2n-k-1}{n-1}. $$ Given this formula, you can use Stirling's approximation to obtain asymptotic estimates.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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