Number of unlabeled rooted trees with n vertices and k leaves

Question

I know that we can write the corresponding multivariate generating function as follows: $\sum y^kx^n$ such that $n$ is the number of vertices and $k$ is the number of leaves. Then we can obtain $f(x,y)=xy+x(\frac{1}{1-f(x,y)}-1)$. On the other hand I know that the number of unlabeled rooted trees with n vertices and k leaves is $\frac{1}{n}{n \choose k}{n-2 \choose n-k-1}$. How can I obtain the coefficient of the generating function to show this identity?

Answer 1

We will compute the number of unlabeled ordered rooted trees on $n$ nodes and having $k$ leaves.

The combinatorial class equation for these trees with leaves marked is

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{T} = \mathcal{Z}\times\mathcal{U} + \mathcal{Z} \times \textsc{SEQ}_{\ge 1}(\mathcal{T}) \quad\text{or}\quad \mathcal{T} = \mathcal{Z}\times\mathcal{U} + \mathcal{Z} \times \sum_{p\ge 1} \mathcal{T}^p.$$

This yields the functional equation for the generating function $T(z)$ $$T(z) = zu + z\frac{T(z)}{1-T(z)}$$ or $$z = \frac{T(z)}{u+T(z)/(1-T(z))} = \frac{T(z)(1-T(z))}{T(z)+u(1-T(z))}.$$

Note that leaves in addition to being marked as such also carry the node marker so that the total number of nodes includes the leaves. If this is not desired subtract the number of leaves from the number of nodes to get the count of genuine internal nodes.

Starting the computation we seek

$$n T_n(u) = [z^{n-1}] T'(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n}} T'(z) \; dz.$$

and will compute this by a variant of Lagrange inversion. We put $T(z) = w$ so that $T'(z) \; dz = dw$ and we find (here we have used the fact that $w=uz+\cdots$)

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(w+u(1-w))^n}{w^n(1-w)^n} \; dw.$$

Extract the coefficient on $[u^k]$ to get

$${n\choose k} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1-w)^k w^{n-k}}{w^n(1-w)^n} \; dw \\ = {n\choose k} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^k} \frac{1}{(1-w)^{n-k}} \; dw.$$

Collecting everything we thus have

$$[u^k] [z^n] T(z) = \frac{1}{n} {n\choose k} {k-1+n-k-1\choose n-k-1}$$

or indeed

$$\bbox[5px,border:2px solid #00A000]{ [u^k] [z^n] T(z) = [u^k] T_n(u) = \frac{1}{n} {n\choose k} {n-2\choose n-k-1}}$$

as claimed. This formula holds for $n\ge 2$ where $1\le k\le n-1.$ Note that the case $k=0$ will always produce zero as it ought to (there is no ordered tree with no leaf) owing to the binomial coefficient ${n-2\choose n-1}.$ Note however that when $n=1$ and $k=0$ we get ${-1\choose 0}$ which evaluates to one, yet the ordered tree on one node is also a leaf.

There is an earlier version of this computation at the following MSE link, which is not as streamlined yet includes a verification of the closed form using the Maple combstruct package.

Re-writing the binomial coefficients we find

$$\frac{1}{n} {n\choose k} {n-2\choose n-k-1} = \frac{1}{n} {n\choose k} {n-2\choose k-1} = \frac{1}{k} {n-1\choose k-1} {n-2\choose k-1}.$$

This choice of representation makes it clear that what we have here are Narayana numbers from the Catalan triangle, shifted by one. This is OEIS A001263. We can also prove that these values add to the Catalan numbers, shifted as well.

We get

$$\sum_{k=1}^{n-1} \frac{1}{n} {n\choose k} {n-2\choose n-k-1} = \frac{1}{n} \sum_{k=0}^{n-1} {n\choose k} {n-2\choose n-k-1} \\ = \frac{1}{n} \sum_{k=0}^{n-1} {n\choose k} [z^{n-k-1}] (1+z)^{n-2} = \frac{1}{n} [z^{n-1}] (1+z)^{n-2} \sum_{k=0}^{n-1} {n\choose k} z^k.$$

We may extend $k$ beyond $n-1$ owing to the coefficient extractor in front:

$$\frac{1}{n} [z^{n-1}] (1+z)^{n-2} \sum_{k\ge 0} {n\choose k} z^k = \frac{1}{n} [z^{n-1}] (1+z)^{n-2} (1+z)^n \\ = \frac{1}{n} [z^{n-1}] (1+z)^{2n-2} = \frac{1}{n} {2n-2\choose n-1}.$$

These are indeed the familiar Catalan numbers, thus shown to count ordered trees.