The Full Question
If we let $T=$ the family of rooted ternary trees, $t_n =$ be number of trees in $T$ with $n$ nodes and $T(x) = \sum\limits_{n=0}^{\infty}w_nx^n$ be the generating function of $T$.
A) Determine the values of $t_1,t_2,t_3$
B) Describe how once can decompose every tree in $T$ that has at least one node into a sequence of three smaller trees in $T$ plus the root node
C) Derive from B an equation that must be satisfied by $T(x)$. Do not attempt to find a closed form
My Work
$t_0 = 1,t_1=1,t_2=3,t_3=9$
I suppose if we consider any ternary tree of length $n$ then we have to think of ways we can connect a tree(s) to the root. I suppose I can have all my trees on the left, or all my trees on the right or all my trees in the middle. Or I can have all my trees on the left and middle, all left right, all middle right, or have them split middle left right. So I suppose if I made those all cases I could count it using Inclusion-Exclusion, but that seems like kind of a strange off the kilter approach to take. Could anyone help me find a better solution to part B?
Best Answer
Marko’s comprehensive answer is a bit overwhelming if you’ve not encountered that approach; let me see if I can offer one closer to what you’ve seen before.
Once you have a root, you can hang three trees from it: one is its left subtree, another is its centre subtree, and the third is its right subtree. (These are ordered trees, so left, centre, and right are meaningful here.) Any of these subtrees can of course be empty. Suppose that the left subtree has $i$ nodes, the centre one has $j$ nodes, and the right one has $k$ nodes, and you’re building a tree with $n$ nodes; then $i+j+k=n-1$, the root being the $n$-th node. This is the decomposition requested in part (B), and it gives you the recurrence
$$t_n=\sum_{\large{{0\le i,j,k}\atop{i+j+k=n-1}}}t_it_jt_k=\sum_{i=0}^{n-1}t_i\sum_{j=0}^{n-1-i}t_jt_{n-1-i-j}\;.\tag{1}$$
The problem now is to convert this into an equation that $T(x)$ must satisfy.
The last summation in $(1)$ is clearly one term of the convolution of the sequence $\langle t_n:n\in\Bbb N\rangle$ with itself; specifically, it’s the coefficient of $x^{n-1-i}$ in $\big(T(x)\big)^2$. The same reasoning shows that the entire right-hand side is the coefficient of $x^{n-1}$ in $\big(T(x)\big)^3$, so it’s the coefficient of $x^n$ in $x\big(T(x)\big)^n$. $(1)$ says that it’s also the coefficient of $x^n$ in $T(x)$, so to a first approximation we have $T(x)=x\big(T(x)\big)^3$. A little care is needed here, however, because $x\big(T(x)\big)^3$ has a $0$ constant term, and we know that $t_0=1$; thus, the correct relationship is
$$T(x)=1+x\big(T(x)\big)^3\;.$$
Note that with a bit more experience you won’t have to go through to convolution steps: you’ll be able to recognize that summing over $m$ indices whose sum is constant is basically taking an $m$-th power of the generating function.