2
$\begingroup$

I am looking for verification for my attempt at the solution. I have found that my answer disagrees with an answer I found here: Extract Coefficients From A Function

Problem at hand: For a plane planted tree $T$, let $h(T)$ denote the number of nodes of T which have an even number of children. For each $n ∈ \mathbb{N}$, determine the average value of $h(T)$ among all the PPTs with $n$ nodes. (This question can be found in Chapter 8 of David Wagner's Combinatorial Enumeration notes from CO 330 in University of Waterloo).

Attempt at Solution: Let $\Omega$ be the set of all plane planted trees. Let $n(T)$ denote the number of nodes in a tree $T$. Define the bivariate generating function $U(x,y)$ by $$U(x,y) = \sum_{T\in \Omega}x^{n(T)}y^{h(T)}.$$

We may decompose $\Omega$ as follows: if the root vertex of $T$ were removed, then $T$ would correspond to a $k-$tuple of trees $(T_1,T_2,\ldots,T_k)$ for some $k\geq 0$ (where we take the convention that $T_0 = \{\}$). So, $$T \leftrightarrow (T_1,\ldots,T_k)$$ if $T$ is not the tree with one vertex.

Moreover, our weights extend as follows: \begin{align*} n(T) &= 1+n(T_1)+\dotsb+n(T_m)\\\ h(T) &= \begin{cases} h(T_1) +\dotsb + h(T_{m}) & \text{$m$ odd}\\ 1+h(T_1)\dotsb +h(T_m) & \text{$m$ even} \end{cases} \end{align*}

and so \begin{align*} W(x,y) &= \sum_{k\geq 0} x\left[\sum_{(T_1,\ldots,T_{2k})}x^{n(T_1)+\dotsb+n(T_{2k})}y^{1+h(T_1)+\dotsb+h(T_{2k})}+\sum_{(T_1,\ldots,T_{2k+1})}x^{n(T_1)+\dotsb+n(T_{2k+1})}y^{h(T_1)+\dotsb+h(T_{2k+1})} \right]\\ &= \sum_{k\geq 0}x\left[ yW^{2k}(x,y)+W^{2k+1}(x,y) \right]\\ &= x\frac{y+W(x,y)}{1-W(x,y)^2} \end{align*} We would like to find $T_n = \{T\in\Omega: h(T) = n\}$. So we look for $$T_n =[x^n]\left.\frac{\partial}{\partial y}W(x,y)\right |_{y=1}$$ Hence, if we let $G(u) = \frac{y+u}{1-u^2}\in \mathbb{Q}(y)$ and hence $$W(x,y) = xG(W(x,y))$$ so by the Lagrange Implicit Function Theorem, \begin{align*} [x^n]\left.\frac{\partial}{\partial y}W(x,y)\right |_{y=1} &= \left.\frac{\partial}{\partial y}[x^n]W(x,y)\right |_{y=1}\\ &= \left.\frac{\partial}{\partial y}\frac{1}{n}[u^{n-1}]G(u)^n\right|_{y=1}\\ &= \frac{1}{n}[u^{n-1}]\left.\frac{\partial}{\partial y}G(u)^n\right|_{y=1}\\ &= \frac{1}{n}[u^{n-1}]\frac{n}{1-u^2}\left[\frac{1+u}{1-u^2}\right]^{n-1}\\ &= [u^{n-1}]\frac{1}{1-u^2}\left[\frac{1}{1-u}\right]^{n-1}\\ &= \sum_{k= 0}^{n-1}\binom{n+k-1}{k}(-1)^{n-k} \end{align*}

I realize I have to divide it by the number of PPT's with $n$ nodes to find the average, which is not too much of a concern. My main concerns are: 1) Is my attempt correct? 2)Is there a closed form for the final binomial summation?

$\endgroup$
1
$\begingroup$

We can actually simplify the computation of the generating function quite a bit. We have by inspection that $$T(z) = uz + z \frac{T(z)}{1-T(z)^2} + uz \frac{T(z)^2}{1-T(z)^2}.$$ This is the species $$\mathcal{T} = \mathcal{Z}\times\mathfrak{S}_{\text{odd}}(\mathcal{T}) + \mathcal{U}\mathcal{Z}\times\mathfrak{S}_{\text{even}}(\mathcal{T}).$$ where the even sequence operator includes the case of zero subnodes. (The reason I wrote the functional equation the way I did was to have the base case of the recursion be clearly recognizable.)

We seek $$\left.\frac{d}{du} T(z)\right|_{u=1}$$ so re-write the above to prepare for differentiation. $$T(z) - T(z)^3 = uz - uz T(z)^2 + z T(z) + uz T(z)^2$$ or $$T(z) - T(z)^3 = uz + z T(z).$$

Differentiate, $$\frac{d}{du} T(z) - 3 T(z)^2 \frac{d}{du} T(z) = z + z \frac{d}{du} T(z).$$ Put $u=1$ and introduce $$G(z) = \left.\frac{d}{du} T(z)\right|_{u=1}$$ and $S(z) = T(z, 1)$ so that $S(z)$ has the functional equation $$S(z) = z + z \frac{S(z)}{1-S(z)} \quad\text{or}\quad S(z)-S(z)^2 = z.$$ This gives $$G(z) - 3 S(z)^2 G(z) = z + z G(z)$$ or $$G(z) = \frac{z}{1 - 3 S(z)^2 - z}.$$

We seek $$q_n = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} G(z) dz$$ which is $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{z}{1 - 3 S(z)^2 - z} dz.$$

Put $w = S(z)$ so that the functional equation yields $$w(1-w) = z.$$ This gives $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1-2w}{w^{n+1}(1-w)^{n+1}} \frac{w(1-w)}{1 - 3 w^2 - w(1-w)} dw$$ or $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1-2w}{w^n(1-w)^n} \frac{1}{(1+w)(1-2w)} dw.$$ which finally becomes $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^n(1-w)^n} \frac{1}{1+w} dw.$$ For the residue from the pole at zero use the following series expansion: $$\sum_{k=0}^\infty {k+n-1\choose n-1} w^k \times \sum_{k=0}^\infty (-1)^k w^k.$$ The coefficient $[w^{n-1}]$ is $$\sum_{k=0}^{n-1} {k+n-1\choose n-1} (-1)^{n-1-k}.$$ This gives the sequence $$1, 1, 4, 13, 46, 166, 610, 2269, 8518, 32206, 122464, 467842, 1794196,\ldots$$ which is OEIS A026641. By the looks of that entry we have the correct result.

This formula matches the one obtained by the OP.

There is another computation in the same spirit at this MSE link.

Addendum. This calculation can also be found at this MSE link.

$\endgroup$
  • $\begingroup$ Marko, thank you for the response and the effort you took to explain this to me. Would you know how to prove that the two answers are the same however? $\endgroup$ – Pavelshu Jun 6 '14 at 1:48
  • $\begingroup$ Surely you do not mean the binomial coefficients? The complex integral is from page 167/168 of Wilf's generatingfunctionology (second edition) where we see that the LIF is really just the Cauchy Residue Theorem. So I decided we may as well apply it directly. The justification is in the Wilf book, same page. The second line where you compute $W(x,y)$ is exactly the same as my functional equation. With species it is easier to spot what is happening quickly. $\endgroup$ – Marko Riedel Jun 6 '14 at 21:30
  • $\begingroup$ My apologies. I am looking for a less "analytical" proof as my background in complex analysis leaves much to be desired. Regardless, thank you for the time you took to help me. $\endgroup$ – Pavelshu Jun 6 '14 at 22:09

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.