A Nice Construction

		1	2	3	4
0	1	1	3	10	43
1	0	1	2	7	30

At the end is the matrix that corresponds to [1,2,3,4] … but that's not the only matrix present! Looking backward, we see the matrices that correspond to [1,2,3], [1,2], and [1], and at the start is the identity matrix that corresponds to the empty expansion. (As usual, we have to swap the columns to obtain the matrices.)

So, we know about [1,2,3], but not about [2,3,4]. Let's correct that.

			2	3	4
	0	1	2	7	30
	1	0	1	3	13

See how the denominators in the first table are equal to the numerators in the second? That's not a coincidence. To compute the denominators in the first table, we start with the initial conditions (1,0) and then use a₀ to compute q₀ and so on.

q₀ = a₀q₋₁ + q₋₂

That's correct from a theoretical perspective, but from a practical perspective, since q₋₁ = 0, we always have q₀ = q₋₂ = 1. So, if we want, we can pretend that we start with the initial conditions (0,1) and then use a₁ to compute q₁ and so on. But, that's also exactly how we compute the numerators in the second table!

That's not a new result, by the way. I mentioned it way back in the fourth bullet point of Chains and Denominators.

Since the denominators in the first table are equal to the numerators in the second, we can pack the tables together. If we continue the process with [3,4] and so on, we can construct a nice triangle.

		1	2	3	4
0	1	1	3	10	43
1	0	1	2	7	30
	1	0	1	3	13
		1	0	1	4
			1	0	1
				1	0

That triangle contains exactly the matrices that correspond to the sub-expansions of [1,2,3,4], no more and no less. There are fifteen of them, including five copies of the identity matrix.

Here's an idea I picked up from programming that makes it easier to count the sub-expansions. When we have a string, list, or array, any type of linear data structure, there are two kinds of index numbers. Let's say we have a string of length 4.

	0		1		2		3
	a		b		c		d
0		1		2		3		4

The numbers in the top row refer to the elements of the data structure, here characters, while the numbers in the bottom row refer to the spaces between the elements. Numbers of the first kind are the most common, as in a typical for loop, …

for (int i=0; i<n; i++)

… but numbers of the second kind are more common than you might think. Examples? The position of an iterator is one. The cursor position in a text field is one. Two cursor positions define a selection, and a selection is a substring, or perhaps a sub-expansion.

Unfortunately, people generally aren't aware that there are two kinds of numbers, so there aren't good conventions for the second kind. If we have a number of the first kind, of course we should call it an index and use the variable name i, but if we have a number of the second kind, it's not clear what we should do. Maybe call it a position? And use the variable name pos? But that's a problem for another time.

Next let's do the same construction for the reversed expansion [4,3,2,1].

		4	3	2	1
0	1	4	13	30	43
1	0	1	3	7	10
	1	0	1	2	3
		1	0	1	1
			1	0	1
				1	0

As you might have guessed, the new triangle is the transpose of the old triangle (across the other diagonal). The reason is easy to understand.

1. Every sub-expansion of the reversed expansion is the reverse of a sub-expansion of the original expansion, so every matrix in the new triangle is the transpose of a matrix in the old triangle.
2. How can all the transposed matrices possibly fit together into a new triangle unless the new triangle is the transpose of the old triangle?

Of course that's just the fun version of the second step. Here's the serious version.

2. Take another look at how we constructed the original triangle. It turns out that the start and end positions of the sub-expansions are also Cartesian coordinates that tell us where the matrices are located! The origin is in the upper left, the x axis (start position) points down, and the y axis (end position) points to the right. When we reverse the expansion, the sub-expansion (x,y) maps to the sub-expansion (4−y,4−x). That mapping is exactly the transposition we were looking for, so all the matrices end up exactly where they should.

Finally, let's carry the expansion coefficients from the new triangle back to the old triangle.

		1	2	3	4
0	1	1	3	10	43	1
1	0	1	2	7	30	2
	1	0	1	3	13	3
		1	0	1	4	4
			1	0	1
				1	0

Consider the number 30 in the upper right. We can compute it horizontally, using the old coefficient 4 above, but we can also compute it vertically, using the new coefficient 2 to the right.

30 = 4 ×	7 + 2
30 = 2 ×	13 + 4

Every number in the triangle can be computed in two ways!

Of course I need to add some caveats about “every number”. When we run the second algorithm, the first two columns are given, not computed. So, in the triangle, the 1s in the outer diagonal and the 0s in the next diagonal are always given. The 1s in the third diagonal can be regarded as given, but can also be regarded as computed in up to two ways, depending on things. Every other number is always computed, and can be computed in two ways.

Although it's easy to explain, it's still hard to believe that those interlocking computations work.

And, of course they work not just for [1,2,3,4] but for any finite expansion. You may have noticed that I like to explain things not abstractly, with definitions and proofs, but concretely, with a nice large example. I think there's a name for that rhetorical technique, but I can't remember what it is.

You may also have noticed that I like two-dimensional arrays of numbers, especially ones computed via local rules. Here are all the examples I could find, ordered by batch year and month.

• I like the algorithm in Powers of N a lot because I discovered it myself.
• The triangle in Pascal's Triangle looks more like a two-dimensional array if you rotate it 45 or 135 degrees counterclockwise.
• Does the table in Logarithmic Forms follow a local rule? Technically yes! But it doesn't feel local.
• Does the table in Partitions follow a local rule? Technically maybe not—p(n,k) depends on p(n−k,k), so the extent of the rule increases with k. But it does feel kind of local.