Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$


share|cite|improve this question
up vote 3 down vote accepted

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}\;.$$

share|cite|improve this answer
Thanks! - I did not know that =). – Nizbel99 Nov 8 '12 at 22:35
@user43552: You’re welcome! – 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\;.$$

share|cite|improve this answer
Thank you =) - I did not think at all to use the binomial theorem to derive it. – 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}.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.