Polya Problem Solving Question

I think the toughest question we've been given all year was from Assignment 1/Assignment 2. Yep, I'm talking about the ternary tree question. The question can be found here
http://www.cdf.toronto.edu/~heap/236/f08/A2/a2.pdf (It's the very first question on the assignment). Anyway, I looked back and realized that many of the methods I used on my way to coming up with a solution to this problem were from Polya himself. So I've decided to go back and reanswer the question using the Polya Problem Solving techniques.

1. Understanding the Problem

To understand this problem, you have to first understand certain characteristics of a ternary tree. I know that all trees in general (whether it be binary, ternary, quatrenary (sp?), etc.) all comprise of a root node. In this case, a ternary tree will have a root node plus at least 3 child nodes. The only exception to this rule is the empty tree. Also when I say that a ternary tree must have at least 3 child nodes, I mean that in kind of an "abstract-way". Don't get me wrong, a ternary tree could just have the root node with zero children, but when drawing ternary tree it`s easy to look at it as if there are exactly three spots available from the root node. Whether these be empty or not is totally dependent on the question.

My goal is to form some sort of algorithm that finds the number of non-equivalent ternary trees with n nodes, where n /in N. The defn. of a non-equivalent ternary tree could be found in the question.


2. Devise A Plan

First things first, I'm going to completley forget about the mathematical mumbo-jumbo and think of this question in a much simpler form. I know that every ternary tree has exactly ONE root node no matter what, so given n nodes I can make things simpler by breaking the question down to "the # of non-equivalent ternary trees with n-1 nodes, where n /in N."

Then I will treat the number n-1 as a "budget" of nodes I'm allowed to spend on any ternary tree, T. I also know that any T will have at least 3 child nodes connecting from the root. I will call these left (TL), middle (TM), and right (TR). Then I have n-1 nodes to spend between L, M, and R. Thinking about this question in a straight-forward, logical form should produce the right answer. So, let's give it a try:


3. Carry Out The Plan

Let T be an arbitary ternary tree with n nodes. Then when n >= 2 I know T must have three sub-trees. Let TL, TM, and TR be defined as the left, middle and right subtrees of T respectively. Then minus the root, R, I know that TL, TM, TR are comprised of n-1 nodes. Then I have a "budget" of n-1 nodes to "spend" on either TL, TM or TR.

First I will consider TL. Assume k is the number of nodes I choose to spend on TL (\exists k \in N). Then I have n-1 nodes to choose from, so k can be any number of nodes within n-1 and k must be less then or equal to n-1. Then I have k=0Zn-1 F(k). Now I must consider TM and TR. Assume n is the number of nodes I have left to spend on TM and TR (\exists m \in N). Then I have n-1-k nodes to choose from, since I originally had n-1 nodes and I've already spent k nodes on TL. Then m is dependent on k, m can be any number of nodes within n-1-k, and m <= n-1-k. Then I have m=0Zn-1-k F(m). Then I have n-1-k-m nodes left to spend on TR. I can treat TR as being fully dependent on k and m, because all the nodes left in my "budget" must ultimately be "spent" in the end. Then the total number of nodes in TR must be equal to n-1-k-m, so I have F(n-1-k-m).

Adding together all of the possible combinations formed by each k and m will give you the total number of non-equivalent ternary trees of n nodes. Then k=0Zn-1 F(k) * m=0Zn-1-k F(m) * F(n-1-k-m) is true!


4. Conclusion

Sometimes looking at the question in a purely logical and simplistic way is very helpful in figuring out the solution. In this case, I used the number of nodes available to me as a "budget" and applied it to any arbritrary ternary tree. In the end, it worked out perfectly! Obviously you would use induction to prove this sort of thing, but I was simply just showing the "method" I used to base my induction around.