Second Assignment

The first question on this assignment seemed complicated at first because it involved a combinatorial explosion. The trick in solving this question was to find a pattern and generalize it for all number of nodes. I made sure I understood the question thoroughly before I proceeded to solve it. I started out by drawing ternary trees from the root node. I expanded each combination of nodes and noticed the pattern as the number of nodes increased. I realized that the distribution of the nodes among the three sub-trees behaved like combination without replacement. Thus I devised a summation formula that yielded the total number of non-equivalent ternary trees given n nodes. The number of nodes available for each sub-tree is the total number of nodes minus that used by the previous sub-trees at that specific height. I tried the formula on different number of nodes and convinced myself that it works for all n.