Compute the expected degree of the root of Cayley and Catalan trees

analytic-combinatoricscombinatoricsgenerating-functionstrees

Find the expected degree of the root of

  1. Cayley trees
  2. Catalan trees

I want to do this with probability generating functions, aka PGFs. Here is what I got so far:

  1. Let $\mathcal{C}$ be the class of rooted acyclic connected graphs, a.k.a. Cayley trees (non-plane rooted labelled trees), and let $X$ denote the degree of the root. Then we have

$$\mathcal{C} = \mathcal{A} \times \text{SET}\left( u\mathcal{C} \right)$$ and $$C(z,u) = z \exp(uC(z,1)).$$ Then the expected degree of the root in a random Cayley tree on $n$ vertices is given by

$$\mathbb{E}[X] = \frac{1}{[z^n]C(z,1)} [z^n] \frac{\partial}{\partial u} C(z,u) \bigg\vert_{u=1}
= \ldots$$

However, I do not see how to go on from here. I know that $$[z^n]C(z) = n^{n-1},$$ so $C_n$ is the $n$-th Cayley number. However, I do not see what to do with the term $[z^n] \frac{\partial}{\partial u} C(z,u) \bigg\vert_{u=1}$.

  1. Let $\mathcal{P}$ be the class of rooted acyclic connected plane graphs, a.k.a. Catalan trees (a.k.a. plane rooted trees), and let $X$ denote the degree of the root. Then we have

$$\mathcal{P} = \mathcal{A} \times \text{SET}\left( u\mathcal{P} \right)$$ and $$P(z,u) = z \exp(uP(z,1)).$$ Then the expected degree of the root in a random Catalan tree on $n$ vertices is given by

$$\mathbb{E}[X] = \frac{1}{[z^n]P(z,1)} [z^n] \frac{\partial}{\partial u} P(z,u) \bigg\vert_{u=1}
= \ldots$$

Again, I do not see how to go on from here. I know that $$[z^n]P(z) = \frac{1}{n} \cdot {{2n-2}\choose{n-1}},$$ but I do not see what to do with the term $[z^n] \frac{\partial}{\partial u} P(z,u) \bigg\vert_{u=1}$. However, I know that $P(z) = \frac{1-\sqrt{1-4z}}{2}$.

Could you please help me?

Best Answer

For Catalan trees let us recall the combinatorial class equation

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{C} = \mathcal{Z} \times \textsc{SEQ}(\mathcal{C}).$$

which gives the functional equation

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

Marking the root degree we get

$$\mathcal{Z} \times \mathcal{U}^0 \textsc{SEQ}_{=0}(\mathcal{C}) + \mathcal{Z} \times \mathcal{U}^1 \textsc{SEQ}_{=1}(\mathcal{C}) + \mathcal{Z} \times \mathcal{U}^2 \textsc{SEQ}_{=2}(\mathcal{C}) + \cdots$$

This gives the generating function

$$R(z, u) = z \sum_{k\ge 0} u^k C(z)^k = z \frac{1}{1-u C(z)}.$$

As a sanity check put $u=1$ to get $z/(1-C(z))$ which is correct. Differentiate and put $u=1$ to obtain

$$\left. \frac{\partial}{\partial u} R(z, u) \right|_{u=1} = \left. \frac{z}{(1-uC(z))^2} C(z) \right|_{u=1} = \frac{1}{z} C(z)^2 C(z) = \frac{1}{z} C(z)^3.$$

Now using Lagrange inversion by residues (Egorychev method) we seek

$$[z^n] \frac{1}{z} C(z)^3 = [z^{n+1}] C(z)^3 = \frac{1}{n+1} [z^n] 3 C(z)^2 C'(z) \\ = \frac{1}{n+1} \;\underset{z}{\mathrm{res}}\; \frac{1}{z^{n+1}} 3 C(z)^2 C'(z).$$

Next put $C(z)=w$ to get with $z= w (1-w)$

$$\frac{1}{n+1} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n+1} (1-w)^{n+1}} 3w^2 = \frac{3}{n+1} [w^{n-2}] \frac{1}{(1-w)^{n+1}} = \frac{3}{n+1} {n+n-2\choose n} \\ = \frac{3}{n+1} {2n-2\choose n}.$$

It follows that the average degree of the root is

$$\frac{3}{n+1} {2n-2\choose n} n {2n-2\choose n-1}^{-1} = \frac{3}{n+1} \frac{(n-1)!^2}{(n-1)! (n-2)!}$$

or

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

This result was verified with the combstruct package, see below.

with(combstruct);
with(combinat);

trees :=
proc(n)
    option remember;
    local spec, k, res;

    res := 0;
    for k to n-1 do
        spec := { T1= Prod(Z, Sequence(T1)),
                  Z=Atom,
                  T2 = Prod(Z, Sequence(T1, card=k))};
        
        res := res +
        k*count([T2, spec, unlabeled], size=n);
    od;

    res/(1/n*binomial(2*n-2,n-1));
end;
Related Question