Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
2  
I think you want to use Lagrange inversion. See Stanley ECII, Theorem 5.4.2. –  Martin Rubey Jul 13 '10 at 15:34
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.