*left segments*. Every figure in the third row has three

*right segments*. And let's say that

*n*is the number of left segments and

*m*is the number of right segments.

Look at the figures with

*n*= 1 in the first column.

It's the triangular numbers again! I haven't found a shape-counting problem that doesn't involve the triangular numbers. Check out my explanations for the first two problems if you'd like more insight.

If

*n*= 1, there are T(*m*) triangles.
Now look at the figures with

*n*= 2 in the second column. The figure with*n*= 2 and*m*= 1 has already been dealt with through its mirror image in the first column, so let's jump to*m*= 2.
If we think of the figure as being split into an upper piece and a lower piece by the interior left segment, then we can count the triangles in the lower piece (blue), the triangles in the upper piece (red), and the triangles that overlap (green).

Notice that for the blue regions and green regions we get triangular numbers, but in the red region the number of triangles is just the number of right segments. Now that the general pattern has been illustrated, I will sometimes just color the regions and omit a thorough inventory of every triangle.
It looks like we're ready to write a formula for figures in the second column.

If

*n*= 2, there are 2T(*m*) +*m*triangles.
Let's advance to the third column (

*n*= 3) and skip*m*= 1 and*m*= 2 since we've already covered their mirror images. Recursive thinking will really start to come in handy now. In everything that follows the blue region will be a figure for which we have already developed a formula, the red region will represent all the triangles outside the blue region, and the green regions will represent the triangles that overlap. Here's how it looks for*n*=*m*= 3.
The structure is similar for

*n*= 3 and*m*= 4.
And I think we're ready for another formula.

If

*n*= 3, there are 3T(*m*) + 3*m*triangles.
Once we're ready we can look at all the formulas we've written for the columns and see if we can figure out how

*n*fits into the formula. For me personally, I had to work out the formula for one more column before really seeing the pattern. Here's how things turned out for*n*= 4.
I'd like to solve!

If

*n*= 1, there are T(*m*) triangles.
If

*n*= 2, there are 2T(*m*) +*m*triangles.
If

*n*= 3, there are 3T(*m*) + 3*m*triangles.
If

*n*= 4, there are 4T(*m*) + 6*m*triangles.
For any

*n*, there are*n*T(*m*) +*m*T(*n*-1) triangles.
I was so delighted to yet again see my friends, the triangular numbers, this time as coefficients in a sequence of formulas. But I also thought the formula must be wrong, because it lacked symmetry between

*n*and*m*. It turns out that there is symmetry after all, because*n*T(

*m*) +

*m*T(

*n*-1) =

*n*T(

*m*-1) +

*m*T(

*n*).

__Proof by Induction__
If

*n*= 1, the number of triangles is T(*m*). In this case the formula gives*n*T(

*m*) +

*m*T(

*n*-1) = 1T(

*m*) +

*m*T(0) = T(

*m*) +

*m*(0) = T(

*m*),

so the base case holds.

Suppose that if

*n*=*k*, the number of triangles is*k*T(*m*) +*m*T(*k*-1). We want to show that if*n*=*k+*1, the number of triangles is (*k*+1)T(*m*) +*m*T(*k*).
By the induction hypothesis, there are

*k*T(*m*) +*m*T(*k*-1) triangles in the blue region. There are T(*m*) triangles that can be formed by selecting two elements from among the*m*right segments and the base of the figure. Finally, for each of the*k*interior left segments there are*m*triangles that can be formed by using that interior segment and the left segment on the perimeter of the figure. Taking the sum of all these triangles we get*k*T(

*m*) +

*m*T(

*k*-1) + T(

*m*) +

*km*

= (

*k*+1)T(*m*) +*m*(T(*k*-1)+*k*)
= (

*k*+1)T(*m*) +*m*T(*k*).

__Summary of Shape-Counting Problems #1-3__
Here is a rough summary of the formulas for the first three shape-counting problems I've written about:

It's quite beautiful how the triangular numbers appear in all these formulas, and it's possible to gain a deeper understanding of all these formulas by thinking about the combinatorial meaning of the triangular numbers. My route to the last formula in particular was rather tortured. Can you see how to justify the formula just by taking combinations of line segments? Anyway, stay tuned... the most exciting shape-counting problems are yet to come!

## No comments:

## Post a Comment