Extract Coefficients From A Function

Question

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!

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

Answer 2

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