Lemma 9.27.
For each \(k\ge 1\text{,}\)
\begin{equation*}
\binom{1/2}{k}=\frac{(-1)^{k-1}}{k}\frac{\binom{2k-2}{k-1}}{2^{2k-1}}.
\end{equation*}
Section 9.7 Solving a nonlinear recurrence
In this section, we will use generating functions to enumerate the a certain type of trees. In doing this, we will see how generating functions can be used in solving a nonlinear recurrence equation. We will also make a connection to a counting sequence we encountered back in Chapter 2. To do all of this, we must introduce a bit of terminology. A tree is rooted if we have designated a special vertex called its root. We will always draw our trees with the root at the top and all other vertices below it. An unlabeled tree is one in which we do not make distinctions based upon names given to the vertices. For our purposes, a binary tree is one in which each vertex has \(0\) or \(2\) children, and an ordered tree is one in which the children of a vertex have some ordering (first, second, third, etc.). Since we will be focusing on rooted, unlabeled, binary, ordered trees (RUBOTs for short), we will call the two children of vertices that have children the left and right children.
In Figure 9.26, we show the rooted, unlabeled, binary, ordered trees with \(n\) leaves for \(n\leq 4\text{.}\)
Let \(C(x) = \sum_{n=0}^\infty c_n x^n\) be the generating function for the sequence \(\{c_n\colon n\geq 0\}\) where \(c_n\) is the number of RUBOTs with \(n\) leaves. (We take \(c_0=0\) for convenience.) Then we can see from Figure 9.26 that \(C(x) = x + x^2 + 2x^3 + 5x^4 + \cdots\text{.}\) But what are the remaining coefficients? Let’s see how we can break a RUBOT with \(n\) leaves down into a combination of two smaller RUBOTs to see if we can express \(c_n\) in terms of some \(c_k\) for \(k\lt n\text{.}\) When we look at a RUBOT with \(n\geq 2\) leaves, we notice that the root vertex must have two children. Those children can be viewed as root nodes of smaller RUBOTs, say the left child roots a RUBOT with \(k\) leaves, meaning that the right child roots a RUBOT with \(n-k\) leaves. Since there are \(c_k\) possible sub-RUBOTs for the left child and \(c_{n-k}\) sub-RUBOTs for the right child, there are a total of \(c_kc_{n-k}\) RUBOTs in which the root’s left child has \(k\) leaves on its sub-RUBOT. We can do this for any \(k=1,2,\dots,n-1\text{,}\) giving us that
\begin{equation*}
c_n = \sum_{k=1}^{n-1} c_kc_{n-k}.
\end{equation*}
(This is valid since \(n\geq 2\text{.}\)) Since \(c_0=0\text{,}\) we can actually write this as
\begin{equation*}
c_n = \sum_{k=0}^{n} c_kc_{n-k}.
\end{equation*}
Let’s look at the square of the generating function \(C(x)\text{.}\) By Proposition 8.3, we have
\begin{align*}
C^2(x) \amp = c_0^2 + (c_0c_1 + c_1c_0)x + (c_0c_2 +c_1c_1 + c_2c_0)x^2 +
\cdots\\
\amp = 0 + 0 + (c_0c_2 +c_1c_1 + c_2c_0)x^2 + (c_0c_3 +
c_1c_2+c_2c_1+c_3c_0)x^3 + \cdots.
\end{align*}
But now we see from our recursion above that the coefficient on \(x^n\) in \(C^2(x)\) is nothing but \(c_n\) for \(n\geq 2\text{.}\) All we’re missing is the \(x\) term, so adding it in gives us that
\begin{equation*}
C(x) = x + C^2(x).
\end{equation*}
Now this is a quadratic equation in \(C(x)\text{,}\) so we can solve for \(C(x)\) and have
\begin{equation*}
C(x) = \frac{1\pm \sqrt{1-4x}}{2} = \frac{1\pm (1-4x)^{1/2}}{2} .
\end{equation*}
Hence, we can use Newton’s Binomial Theorem to expand \(C(x)\text{.}\) To do so, we use the following lemma. Its proof is nearly identical to that of Lemma 8.12, and is thus omitted.
Now we see that
\begin{align*}
C(x) \amp = \frac{1}{2} \pm \frac{1}{2} \sum_{n=0}^\infty\binom{1/2}{n}
(-4)^n x^n
= \frac{1}{2} \pm \frac{1}{2}\left(1+ \sum_{n=1}^\infty
\frac{(-1)^{n-1}}{n}\frac{\binom{2n-2}{n-1}}{2^{2n-1}}(-4)^n
x^n\right)\\
\amp =
\frac{1}{2} \pm\frac{1}{2} \mp\sum_{n=1}^\infty \frac{\binom{2n-2}{n-1}}{n} x^n.
\end{align*}
Since we need \(c_n\geq 0\text{,}\) we take the “minus” option from the “plus-or-minus” in the quadratic formula and thus have the following theorem.
Theorem 9.28.
The generating function for the number \(c_n\) of rooted, unlabeled, binary, ordered trees with \(n\) leaves is
\begin{equation*}
C(x) = \frac{1-\sqrt{1-4x}}{2} = \sum_{n=1}^\infty \frac{1}{n}\binom{2n-2}{n-1}x^n.
\end{equation*}
