Number of unlabeled rooted trees with n vertices and k leaves 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?
 A: 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.
