Expected number of leaves of a planar tree with $n$ nodes

306 Views Asked by At

I want to find out the expected number of leaves of a planar tree with $n$ nodes using the bivariate generating function for the number of leaves in a planar tree.

For the (univariate) generating function we have $$P(z)=\frac{z}{1-P(z)}$$Solving the quadratic equation gives us $$P(z)=\frac{1-\sqrt{1-4z}}{2}$$

Does this imply that the bivariate generating function is given by $$P(z,u)=\frac{z}{1-u\frac{1-\sqrt{1-4z}}{2}}$$?

And for the expected number of leave I have to evaluate $$\frac{[z^n](\frac{\partial}{\partial u}P(z,u))\big |_{u=1}}{[z^n]P(z,1)}$$?

1

There are 1 best solutions below

0
On

The combinatorial class for plane trees with leaves marked is

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{P} = \mathcal{Z} \times \mathcal{U} + \mathcal{Z}\times \textsc{SEQ}_{\ge 1}(\mathcal{P})$$

This gives the functional equation

$$P(z) = uz + z \frac{P(z)}{1-P(z)}$$

or

$$z = \frac{P(z)(P(z)-1)}{u(P(z)-1)-P(z)}.$$

Now applying the residue operator for $n\ge 1$ we get (the constant term of $P(z)$ is zero)

$$[z^n] P(z) = \frac{1}{n} [z^{n-1}] P'(z) = \frac{1}{n} \; \underset{z}{\mathrm{res}} \; \frac{1}{z^n} P'(z).$$

We put $w=P(z)$ and find

$$\frac{1}{n} \; \underset{w}{\mathrm{res}} \; \frac{(u(w-1)-w)^{n}}{w^{n} (w-1)^{n}}.$$

Extracting the coefficient on $[u^k]$ where we must have $1\le k\le n-1$ we obtain

$$\frac{1}{n} {n\choose k} \; \underset{w}{\mathrm{res}} \; \frac{(w-1)^k (-1)^{n-k} w^{n-k}} {w^{n} (w-1)^{n}} \\ = \frac{1}{n} {n\choose k} \; \underset{w}{\mathrm{res}} \; \frac{1}{w^{k} (1-w)^{n-k}} \\ = \frac{1}{n} {n\choose k} {k-1+n-1-k\choose 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}.$$

As a sanity check we get for the sequence of leaf counts with $k$ increasing from $k=1$ to $n-1$ the following values

$$1, 1, 1, 1, 3, 1, 1, 6, 6, 1, 1, 10, 20, 10, 1, 1, 15, 50, 50, 15, 1, \ldots $$

which is OEIS A001263, the Narayana numbers. What we have is $N(n-1,k).$ When we look this up in turn at Wikipedia on Narayana numbers we find that the number of ordered rooted trees with $n+1$ vertices and $k$ leaves is $N(n,k)$ which means we have the correct value.

We continue with the expectation where we first need the total count of these trees which is

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

by Vandermonde. These are the familiar Catalan numbers $C_{n-1}.$ We get for the sum total of leaves

$$\sum_{k=1}^{n-1} {n-1\choose k-1} {n-2\choose k-1} = \sum_{k=0}^{n-2} {n-1\choose k} {n-2\choose k} \\ = \sum_{k=0}^{n-2} {n-1\choose k} {n-2\choose n-2-k} = {2n-3\choose n-2} = {2n-3\choose n-1}.$$

again by Vandermonde. This will produce for $n\ge 2$

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

Looking it up we find OEIS A088218 where it says "total number of leaves in all rooted ordered trees with $n$ edges" is $\frac{1}{2} {2n\choose n}.$ As before this is $n+1$ vertices so we definitely have the right answer.

We are ready at last to compute the queried expectation of the number of leaves for $n\ge 2$

$$\frac{(2n-3)!}{(n-2)! \times (n-1)!} \times n \times \frac{(n-1)! \times (n-1)!}{(2n-2)!} \\ = \frac{1}{2n-2} \times n \times (n-1).$$

This is

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2} n.}$$

Remark. In the above we have used OP's functional equation for $P(z)$ to deduce the type of tree being sought (ordered rooted or rooted plane tree).