Problem Episode on tenary tree

Dene the set of ternary trees, T3, as:
(a) The empty tree, /\, is an element of T3.
(b) If trees TL; TM; TR are elements of T3 having no nodes in common, and R is a node that is not in
TL; TM or TR, then T = (R; TL; TM; TR) is an element of T3. We call TL the left subtree, TM the
middle subtree, and TR the right subtree, of T.
Consider two trees equivalent if (a) they are both /\ (the empty tree), or (b) they have equivalent left
subtrees, equivalent middle subtrees, and equivalent right subtrees. So there is one ternary tree with
zero nodes: /\, and one ternary tree with one node: (R;/\;/\; /\). For arbitrary natural number n, nd
a (possibly recursive) formula for the number of non-equivalent ternary trees with n nodes. Prove your
formula is correct.
Artist's impression of the three non-equivalent ternary trees with two nodes.

1.UNDERSTANDING THE PROBLEM
Given the definition of a tenary tree with 3 nodes. We need to generize a (possibly recursive) formula for the number of non-equivalent ternary trees with n nodes. Then we need to prove it.

2.DEVISING A PLAN
1, Analyze the tenary tree by trying some small number of nodes.
2, Generate a formula for the number of nodes of the tenary tree.
3, Prove the formula is correct by induction.

CARRYING OUT THE PLAN
1)Analysis:
Notice that if we separately analyzes the ways a tree displayed with n nodes,
we can show it as a sum of all possible ways.
Let's take 3 nodes for example. let the possible ways be G(n)
Then, case1, if the left subtree has 0 nodes
case 1a, if the middle subtree has 0 nodes,
the right subtree has 2 nodes. G(n) = G(0)*G(0)*G(2)
case 1b, if the middle subtree has 1 nodes,
the right subtree has 1 nodes. G(n) = G(0)*G(1)*G(1)
case 1c, if the middle subtree has 2 nodes,
the right subtree has 0 nodes. G(n) = G(0)*G(2)*G(0)

Symmetrically, case2 will be when left subtree has 1 nodes and case3 will be
when left subtree has 2 nodes.

Then the total way of displaying is
G(n) = G(0)*G(0)*G(2) + G(0)*G(1)*G(1) + G(0)*G(2)*G(0) + G(1)*G(0)*G(1) +
G(1)*G(1)*G(0) + G(2)*G(0)*G(0) = 3 + 1 + 3 + 1 + 1 + 3 = 12

2) So, the close form
G(n) = 1, if n < i="0}^(n-1)" j="0}^(n-1-i)">= 2

3)
let P(n) be "There are G(n) non-equivalent ternary trees with n nodes."

claim: for all natural number n , P(n)

Proof.

Base case: if n = 0, then there is only one way to display the ternary tree.
Hence P(0) is true.
if n = 1, then there is still one way to display the ternary tree by
putting this nodes on the root. Hence P(1) is also true.

Induction step: Assume for any arbitrary natural number n,
P(2),P(3),...,P(n-1) are true. We need to prove that P(n) is true.
case 1. if n <>= 2, then by Induction Hypothesis, G(i), G(j), and G(n-1-i-j)
are all true, 0 <= i <= n-1, 0 <= j <= n-1-i. Notice that if we separately analyzes the ways a tree displayed with n nodes, we can show it as a sum of all possible ways. When there are n-1 nodes, we assume n-1 cases where the left subtree contains {0,1,...,n-2} nodes(exclude root). Then for each of these case, we analyze how many ways a tree can be displayed when the middle subtree contains {0,1,..,n-2}nodes. In specific, we determine, when there are i nodes in left subtree and j nodes in middle subtree, how many ways the ternary tree can be displayed. Notice that when there are i nodes in left subtree, there are maximum (n-1)-i-1(exclude root) nodes in middle subtree and the right subtree will have (n-1)-1-i-j nodes. We know when calculating possible ways, we multiply each possible case together. In this situation, G((n-1)') = G(i)*G(j)*G((n-1)-1-i-j). We add all possible G(n')s and we get G(n-1) = \sum_{i=0}^(n-2) (\sum_{j=0}^((n-1)-i-1) G(i)*G(j)*G((n-1)-1-i-j) ). Now, we assume there are n nodes, Then, similar to G(n-1), there will be n cases, where the left subtree has {0,1,...,n-1} nodes. and the middle subtree may contains {0,1,..,n-1}nodes. when left subtree has i nodes, the middle subtree will maximum has n-1-i nodes and the right subtree will have n-1-i-j nodes. We have each little case with G(n') = G(i)*G(j)*G(n-1-i-j) We add all possible G(n')s and we get G(n) = \sum_{i=0}^(n-1) (\sum_{j=0}^(n-1-i) G(i)*G(j)*G(n-1-j)) Hence P(n) is true. We have shown that for any natural number n >= 2,
P(n-1) implies P(n).
Thus, for any natural number n >= 2, P(n).
Consider both cases, we now have shown that P(n), for any natrual number n.

4, Looking Back
Usually we can use this episode to generate the number of nodes on a tree with n children.
Even though it is somehow complecate than a simple induction proof.