Skip to main content
1 of 2
user47274
  • 1.3k
  • 15
  • 25

Counting $(n,k)$-forests of binary trees

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?

user47274
  • 1.3k
  • 15
  • 25