B3(z) = Original notation
T(z) == name he's giving for function
T(z) = 1 + zT(z)3
What this says: Either Tree is empty (1) or Tree has one node (z) + 3 more ternary trees (T(z)) Because there are 3 of them, we cube (T(z))
Bpi(z)2 <-- Two-pi-ary Trees. Topiary. Muahaha.
F(z, u) where z = length of the path, and u = height of the path.
F(zj, uk) = the number of j-length meanders that end k steps above 0.
Meander: A walk that MUST stay above zero, and ends at an arbitrary place.
For ternary trees, you must "walk" in steps that are either +1 or -2. As we go through this, picture a graph in your mind. Exponents represent coordinants on that graph, where z's exponent is the x axis and u's exponent is the y axis. z3u4 represents a pt (3,4) on that graph. And coefficients will represent the different number of ways we could have gotten to that point in that step of the walk. So 3u means there were 3 different ways to get to u.
To help with this visualization, I will write both the exponential form of the step, but also the point that it would represent on the graph.
We start at 0. == 1 (0, 0)
z1 our only option is to go right one, and up one. --> z1u1 --> (1, 1)
z2 again, our only doption is right one, up one --> z2u2 --> (2, 2)
z3 we can either go up one, or down two --> z3(1 + u3) --> possible points here are (3, 0), (3, 3)
z4 Remember from the earlier line. We're currently either sitting at 0, or 3. So, we can go up one to u1, or down two to u1, or up one to u4) so --> z4(2u + u4), three options: (4, 1), (4,1), (4, 4);
z5 --> There are three ways to get to u2 and one way to get to u5 --> z5(3u2+u5) (5, 2), (5, 2), (5, 2) (5, 5)
z6> There are 3 ways to get to zero, 5 ways to get to u3 and one way to get to u6 --> z6>(3 + 4u4 + u6) (6, 0), (6, 0), (6, 0), (6, 3), (6, 3), (6, 3), (6, 3), (6, 6)
So far, we are 6 steps into our walk, and we have following equation.
z1u1 + z2u2 + z3(1 + u3) + z4(2u + u4) + z5(3u2+u5) + z6(3 + 4u4 + u6)
At this point, if you remove the z's and u's and focus solely on the coefficients and exponents of u, you are able to place them into a table. Treating each row as an "iteration" and each column as a point ux, you are able to see the various different ending points that would be available on any artbitrary z-length meander along a ternary tree.
Each number on the following graph represents the number of possibilities your meander would have to end at that point, given that length (z).
| z = 0 | 1 | |||||||
|---|---|---|---|---|---|---|---|---|
| z == 1 | 0 | 1 | ||||||
| z == 2 | 0 | 0 | 1 | |||||
| z == 3 | 1 | 0 | 0 | 1 | ||||
| z == 4 | 0 | 2 | 0 | 0 | 1 | |||
| z == 5 | 0 | 0 | 3 | 0 | 0 | 1 | ||
| z == 6 | 3 | 0 | 0 | 4 | 0 | 0 | 1 | |
| z == 7 | 0 | 7 | 0 | 0 | 5 | 0 | 0 | 1 |
| u0 | u1 | u2 | u3 | u4 | u5 | u6 | u7 |
0 --> 1
1 --> 0 1
2 --> 0 0 1
3 --> 1 0 0 1
4 --> 0 2 0 0 1
5 --> 0 0 3 0 0 1
6 --> 3 0 0 4 0 0 1
7 --> 0 7 0 0 5 0 0 1
8 --> 0 0 12 0 0 6 0 0 1
What patterns can we see here? As you move onto the next row, you look at the row above you.
We know that we are constrained to steps of either +1, -2. In this case, adding moves you to the left, subtracting moves you to the right. So, to determine each cell in a new row, look at the cell directly above it. Go one cell back, then go two cells forward, add those two numbers, and that's the number that goes in the cell in question.
Look at row 8. How did we get twelve? Up one, left one (+1), up one, right 2 (-2) gives up 7 and 5, those combine to equal 12.
Each row always terminates with 1.