2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ When $n=4,k=2$, your formula gives $\frac14\binom{4}2\binom{2}1=3$ unlabeled rooted trees with four vertices, but I only count two; a path of length four with a root in the middle, or a claw with a root not in the middle. Am I counting the wrong thing? $\endgroup$ – Mike Earnest Feb 11 '19 at 15:41
  • 1
    $\begingroup$ @MikeEarnest, looking at the identity given for the generating function the order of the children at each node matters: otherwise it would be $f(x,y) = xy + x \sum_{i=1}^\infty Z(S_i, f(x,y), f(x^2,y^2), \ldots)$. So the path of length 4 rooted at the second vertex is counted separately from the path of length 4 rooted at the third vertex. $\endgroup$ – Peter Taylor Feb 12 '19 at 8:22
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Please define the calligraphic notations. $\endgroup$ – darij grinberg Feb 11 '19 at 16:01
  • $\begingroup$ The Lagrange inversion is from page $732$, section $A.6$ of Analytic Combinatorics by Flajolet and Sedgewick. The class equation uses the sequence operator, which is on page $27$, section $1.2$ of the same text. $\endgroup$ – Marko Riedel Feb 11 '19 at 16:07

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.