Ternary Trees == Tribal Dancers!

Just in case you are completely weirded out by the title. Here is a little illustration.

A ternary with no children:

dOdddO
// \ = //\ = a tribal dancer.
dddddd/
ddddd/ \

So a forest ternary trees = a gang tribal dancers.

This is exactly what my scratch paper looked like when I was scratching my head, trying to figure out how to solve this problem during the fourth week. Imagine how much effort I had to put in just to explain to friends who were studying with me that I have graduated from kindergarten and I didn’t suck at doodling.

Wow, that was fun. Here comes back the serious stuff. The ternary trees question is EXCEEDINGLY HARD! It’s hard not because its solution involved strong induction, permutation, combination, and excellent tree-drawing skills, but because it requires two variable to nail the problem. TWO VARIABLES. As a student just graduated from MAT137, I did not see that coming! I tried so hard to actually come up with a formula using a single variable and I inevitably failed. I vividly remember how my eyes lit up when the friendly TA Tim Capes told me that we need two variables to get the solution. What an awesome question! Well, it was even more awesome to learn that this question was delayed to the second assignment due to its extreme awesomeness! Hurray, ternary trees! Hurray, tribal dancers.