So I am trying to determine the average number of nodes with an even amount of children in a plane planted tree with n nodes. I created the generating function, did some manipulation, then applied LIFT (Lagrange Implicit Function Theorem) which gave me the following: $A = 2^{n-1}[u^{n-1}](\frac{1}{1-u})^n$, where $[u^{n-1}]$ denotes the coefficient of $u^{n-1}$ in the function above. So my question is... where do I go from here? Typically, these functions have just been binomial-like, so extracting the coefficient has been easy. However, I have no clue how to extract it in this case. Could anyone show me how?

I should also add that once I have this coefficient and obtain the value of A, in order to calculate the "average value", I will need to divide it by the total number of plane planted trees with n nodes, which I also have as $T= \frac{1}{n}\binom{2n-2}{n-1}$



It’s a standard generating function:

$$\frac1{(1-x)^n}=\sum_{k\ge 0}\binom{n+k-1}kx^k\;.$$

You can prove this by induction on $n$:

$$\begin{align*} \frac1{(1-x)^{n+1}}&=\frac1{1-x}\sum_{k\ge 0}\binom{n+k-1}kx^k\\ &=\sum_{k\ge 0}x^k\sum_{k\ge 0}\binom{n+k-1}kx^k\\ &=\sum_{k\ge 0}\sum_{i=0}^k\binom{n+i-1}ix^k\\ &=\sum_{k\ge 0}\binom{n+k}kx^k\;. \end{align*}$$

In particular, you have

$$A = 2^{n-1}[u^{n-1}]\left(\frac{1}{1-u}\right)^n=2^{n-1}\binom{2n-2}{n-1}\;.$$

  • $\begingroup$ Thanks! - I did not know that =). $\endgroup$ – Nizbel99 Nov 8 '12 at 22:35
  • $\begingroup$ @user43552: You’re welcome! $\endgroup$ – Brian M. Scott Nov 8 '12 at 22:40

If you want some details, the generalized binomial theorem says that for $|x|<1$, $\alpha\in\Bbb R$

$$(1+x)^\alpha=\sum_{k=0}^\infty {\alpha\choose k}x^k$$

where $${\alpha\choose k}:=\frac{1}{k!}\prod_{m=0}^{k-1}(\alpha-m)$$

If $\alpha=-n$ we have

$$(1-x)^{-n}=\sum_{k=0}^\infty {-n\choose k}(-1)^kx^k$$ so

$$\begin{align} {\left( { - 1} \right)^k}{-n\choose k} &= {\left( { - 1} \right)^k}\frac{1}{{k!}}\prod\limits_{m = 0}^{k - 1} {( - n - m)} \cr &= \frac{1}{{k!}}\prod\limits_{m = 0}^{k - 1} {\left( { - 1} \right)( - n - m)} \cr &= \frac{1}{{k!}}\prod\limits_{m = 0}^{k - 1} {(n + m)} \cr &= \frac{1}{{k!}}\prod\limits_{m = 0}^{k - 1} {(n + k - 1 - m)} ={n+k-1\choose k}\end{align} $$


$$\frac1{(1-x)^n}=\sum_{k= 0}^\infty\binom{n+k-1}kx^k\;.$$

  • $\begingroup$ Thank you =) - I did not think at all to use the binomial theorem to derive it. $\endgroup$ – Nizbel99 Nov 8 '12 at 22:46

Here is some enrichment material to complete this calculation. First note that these planted plane trees correspond to ordinary plane trees with an extra node attached at the root.

The species equation for these enumerating by the internal nodes (i.e. excluding the node where the tree is planted) is $$\mathcal{T} = \mathcal{Z}\times \mathfrak{S}(\mathcal{T}).$$ This gives the functional equation $$T(z) = z\frac{1}{1-T(z)} \quad\text{or}\quad z = T(z)(1-T(z)).$$ Now to extract coefficients from this by Lagrange inversion use $$[z^n] T(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z)\;dz$$

and put $w=T(z)$ where $dz = 1-2w\; dw$ to obtain $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1} (1-w)^{n+1}} w \times (1-2w) \;dw$$ which is $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \left(\frac{1}{w^n (1-w)^{n+1}} - 2\frac{1}{w^{n-1} (1-w)^{n+1}} \right) \; dw.$$

This yields $${n-1+n\choose n} - 2{n-2+n\choose n} = {2n-1\choose n} - 2{2n-2\choose n}$$ which is $$\frac{2n-1}{n}{2n-2\choose n-1} -2\frac{n-1}{n}{2n-2\choose n-1} = \frac{1}{n} {2n-2\choose n-1}.$$ These are of course the Catalan numbers.

The species equation for these trees with the even outdegree marked is $$\mathcal{Q} = \mathcal{Z}\times \mathcal{U}\mathfrak{S}_\mathrm{even}(\mathcal{Q}) + \mathcal{Z}\times \mathfrak{S}_\mathrm{odd}(\mathcal{Q}).$$ This gives the functional equation $$Q(z) = uz\frac{1}{1-Q(z)^2} + z\frac{Q(z)}{1-Q(z)^2}$$ or $$Q(z)(1-Q(z)^2) = uz + z Q(z).$$ To compute the total number of even degree nodes introduce $$G(z) = \left.\frac{\partial}{\partial u} Q(z)\right|_{u=1}.$$

Differentiate the functional equation and put $u=1$ to get $$G(z)(1-T(z)^2) + T(z) (-2T(z) G(z)) = z + z G(z).$$ This yields $$G(z) = \frac{z}{1-z-3T(z)^2}.$$

To extract coefficients from $G(z)$ use $$[z^n] G(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{z}{1-z-3T(z)^2}\;dz.$$

Using the same substitution as before we obtain $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1} (1-w)^{n+1}} \frac{w(1-w)}{1-w(1-w)-3w^2} \times (1-2w) \;dw$$ which is $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1} (1-w)^{n+1}} \frac{w(1-w)}{(1-2w)(1+w)} \times (1-2w) \;dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^n (1-w)^n} \frac{1}{1+w}\;dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^n (1-w)^n} \sum_{q\ge 0} (-1)^q w^q \; dw.$$

Extracting coefficients from this we obtain $$\sum_{q=0}^{n-1} {q+n-1\choose n-1} (-1)^{n-1-q}.$$

This gives OEIS A026641 which is $$1, 1, 4, 13, 46, 166, 610, 2269, 8518, 32206,\ldots$$ where we find the above workings confirmed.

It follows that the average number of even outdegree nodes in a random rooted plane tree is given by the formula $$ n \times {2n-2\choose n-1}^{-1} \times \sum_{q=0}^{n-1} {q+n-1\choose n-1} (-1)^{n-1-q}.$$


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.