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 . 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, ). 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 , we show the rooted, unlabeled, binary, ordered trees with \(n\) leaves for \(n\leq 4\).

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 that \(C(x) = x + x^2 + 2x^3 + 5x^4 + \cdots\). 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\). 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\), giving us that \[\begin{aligned}\end{aligned}\] (This is valid since \(n\geq 2\).) Since \(c_0=0\), we can actually write this as \[\begin{aligned}\end{aligned}\]

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.