Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thanks!

share|improve this question
add comment

2 Answers 2

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|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
add comment

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

whence

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

share|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
add comment

Your Answer

 
discard

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.