# 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?

• I think you want to use Lagrange inversion. See Stanley ECII, Theorem 5.4.2. Jul 13, 2010 at 15:34

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.
• This formula gives $f_{n-1,n} = n-1$, but shouldn't there only be one $(n-1,n)$-binary forest, namely one tree with two leaves, and $n-2$ trees with one leaf? Or does this formula count forests with labelled trees, so that it makes a difference whether the "first" or "second" tree is the one with two leaves? Jul 20, 2021 at 15:42
• @Peter Order matter here. That is, $f_{k,n}$ counts the number of ordered $k$-tuples of rooted trees having a total of $n$ leaves. This is consistent with OP's assertion that $f_{k,n}$ is the $(n-k)$'th coefficient of $C(z)^k$. Jul 20, 2021 at 17:33