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?

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

1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$
    – Peter
    Jul 20, 2021 at 15:42
  • $\begingroup$ @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$. $\endgroup$
    – Jim Belk
    Jul 20, 2021 at 17:33
  • $\begingroup$ I see, thank you! $\endgroup$
    – Peter
    Jul 21, 2021 at 4:36

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.