Counting triangles on a tin ceiling (solution, take 2)

This is the solution to a problem I posed in my previous blog post. Please read that post first.

[Update: I posted a solution to this problem two days ago. Yesterday Brent Yorgey pointed out that my analysis of “type 2” triangles was not quite correct. (See his comment below.) So I went back to the whiteboard and worked out the correct solution. Hopefully the formula given below is correct. Thanks, Brent!]

Here’s a recap of the problem: How many triangles are there in an ${n\times n}$ grid of squares with X’s through them (as shown below)?

We realized that there are two types of triangles. We’ll say a triangle is of “type 1” if the legs of the triangle run horizontally and vertically (as shown below).

A triangle is of “type 2” if the hypotenuse runs either horizontally or vertically (as shown below).

Type 1

Consider the type 1 triangles with ${k}$ horizontal (or vertical) segments in each leg. Examples of ${k=1, 2, 3}$ are shown in the diagram. When ${k=1}$ there are ${4n^{2}}$ such triangles in the ceiling. In particular, there are ${n^{2}}$ having the orientation shown, but then they can be rotated 90, 180, or 270 degrees. When ${k=2}$ there are ${4(n-1)^{2}}$ such triangles. When ${k=3}$ there are ${4(n-2)^{2}}$ , etc. Thus, the total number of type 1 triangles is

$\displaystyle \sum_{i=1}^{n}4i^{2}=\frac{4 n(n+1)(2n+1)}{6}.$

Type 2

Counting the type 2 triangles is tricker. Let ${k}$ denote the number of segments in the hypotenuse of the triangle. Examples of ${k=1,2,3}$ are shown in the diagram. The key observation is that each time ${k}$ increases by one unit the horizontal distance (in the given configuration) increases by a half unit.

For example, when ${n=4}$ here are the number of type 2 triangles of a given orientation for the possible values of ${k}$ (so the final count will be four times the sum of these).

$\displaystyle \left.\begin{array}{|c|c|c|c|}\hline k & \text{up-and-down} & \text{left-to-right} & \text{total}\\ \hline 1 & 4 & 4 & 4\cdot 4\\ \hline 2 & 3 & 4 & 3\cdot 4\\ \hline 3 & 2 & 3 & 2\cdot 3\\ \hline 4 & 1 & 3 & 1\cdot 3\\ \hline \end{array}\right.$

And here are the number when ${n=5}$ .

$\displaystyle \left.\begin{array}{|c|c|c|c|}\hline k & \text{up-and-down} & \text{left-to-right} & \text{total}\\ \hline 1 & 5 & 5 & 5\cdot 5\\ \hline 2 & 4 & 5 & 4\cdot 5\\ \hline 3 & 3 & 4 &3\cdot 4\\ \hline 4 & 2 & 4 & 2\cdot 4\\ \hline 5 & 1 & 3 & 1\cdot 3\\ \hline \end{array}\right.$

In general, for a given ${n}$ and ${k}$ and a given orientation we can fit ${n-k+1}$ triangles in one direction and ${n-\lceil\frac{k}{2}\rceil+1}$ in the other. Thus the number of type 2 triangles is

$\displaystyle 4\sum_{k=1}^{n}\big((n-k+1)(n-\Big\lceil\frac{k}{2}\Big\rceil+1)\big).$

It follows that there is a different closed form for this summation for ${n}$ even and ${n}$ odd.

Consider the case that ${n}$ is even. I’ll skip most of the algebraic details, but essentially I summed the values for even ${k}$ and odd ${k}$ separately.

$\displaystyle 4\sum_{k=1}^{n}\big((n-k+1)(n-\Big\lceil\frac{k}{2}\Big\rceil+1)\big).$

$\displaystyle =4\sum_{i=1}^{\frac{n}{2}}\big((2i-1)(\frac{n}{2}+i)+(2i)(\frac{n}{2}+i)\big)$

$\displaystyle =16\sum_{i=1}^{\frac{n}{2}}i^{2}+(8i-4)\sum_{i=1}^{\frac{n}{2}}i-2n\sum_{i=1}^{\frac{n}{2}}1$

$\displaystyle =\frac{10n^{3}+15n^{2}+2n}{6}.$

Now suppose ${n}$ is odd.

$\displaystyle 4\sum_{k=1}^{n}\big((n-k+1)(n-\Big\lceil\frac{k}{2}\Big\rceil+1)\big).$

$\displaystyle =4\sum_{i=1}^{\frac{n+1}{2}}\big((2i-1)(\frac{n-1}{2}+i)\big)+4\sum_{i=1}^{\frac{n-1}{2}}\big((2i)(\frac{n+1}{2}+i)\big)$

$\displaystyle =16\sum_{i=1}^{\frac{n+1}{2}}i^{2}+(8i-4)\sum_{i=1}^{\frac{n+1}{2}}i-2(n-1)\sum_{i=1}^{\frac{n+1}{2}}1-4(n+1)^{2}$

$\displaystyle =\frac{10n^{3}+15n^{2}+2n-3}{6}.$

Adding the number of type 1 and type 2 triangles and simplifying the expression we find that the total number of triangles in an ${n\times n}$ grid is

$\displaystyle \frac{6n^{3}+9n^{2}+2n}{2}$

when ${n}$ is even and

$\displaystyle \frac{6n^{3}+9n^{2}+2n-1}{2}$

when ${n}$ is odd.

Thus, here are the number of triangles for the first few ${n}$ -values:

$\displaystyle \left.\begin{array}{|c|c|}\hline n & \text{number of triangles} \\\hline 1 & 8 \\\hline 2 & 44 \\\hline 3 & 124 \\\hline 4 & 268 \\\hline \end{array}\right.$

In particular, there are 268 triangles in the ${4\times 4}$ example at the start of the blog post.

When I posted my first solution I claimed that this sequence was not in the On-line Encyclopedia of Integer Sequences database. Now that I’ve corrected the formula (and hence the fourth term of the sequence), I discovered that it is already there!. (They give more terms of sequence A100583: 8, 44, 124, 268, 492, 816, 1256, 1832, 2560, 3460, 4548, 5844, 7364, 9128, 11152, 13456, 16056, 18972, 22220, 25820, 29788, 34144, 38904, 44088, 49712, 55796, 62356, 69412, 76980, 85080, 93728, 102944, 112744, 123148, 134172, 145836.)

8 Comments

Pingback: Counting triangles on a tin ceiling « Division by Zero
Brent says:

February 11, 2011 at 4:37 pm

I don’t think your analysis of type 2 triangles is quite right. Every time you increase the hypotenuse of a type 2 triangle by 1 unit, the width (given the orientation you illustrated for type 2) only increases by 1/2 unit, so there are not always i(i-1) of them. The number of triangles that will fit from top-bottom decreases by 1 each time, but the number of triangles that fit left-right only decreases by 1 every OTHER time. For example, in the 4×4 grid shown, you can see that there are actually 3 (not 2) type 2 triangles with a hypotenuse of 4.

This makes things a bit trickier (although it does mean that the first case is actually not a special case!). I think the correct formula for the number of type 2 triangles is

$\displaystyle 4 \sum_{i=1}^n (n - i + 1) (n - \left\lceil\frac{i}{2} \right\rceil + 1)$

although I am not sure of a nice way to simplify this off the top of my head.
Brent says:

February 11, 2011 at 4:39 pm

Of course, I meant to say, 12 type 2 triangles with a hypotenuse of 4, three in each orientation.
1. Dave Richeson says:
  
  February 11, 2011 at 5:15 pm
  
  Ugh! Thanks, Brent. You are definitely correct about our mistake. Clearly I should have waited more than 20 minutes before typing up and publishing our “result” :-) I’m going to pull this off my blog temporarily until I can find a fix (or determine that there isn’t an elegant one).
2. Dave Richeson says:
  
  February 12, 2011 at 5:03 pm
  
  Check it out now. I think it is fixed.
  1. Brent Yorgey says:
    
    February 12, 2011 at 6:29 pm
    
    Looks good to me! You ought to submit a link to this blog post to be included in the OEIS entry.
Timstudiesmath says:

February 12, 2011 at 6:12 pm

I’m not sure about a closed form, but in counting triangles of Type 2, we can do the following. The number of triangles with hypotenuse on a particular vertical line is T(n), except for those that don’t fit in the n x n grid, which is easily seen to be A002623, the partial sum of alternate triangular numbers. Thus, {the number of triangles of type 2} = 4 n T(n) – {the (n-2)th term of A002623).
tendstoinfinity says:

February 20, 2011 at 3:49 am

Beautiful problem and an elegant solution, although i think we can count total number of triangles using coordinates of the points. I will think on this problem and as soon as I will post it in my blog. I have another problem on combinatorics, please help.
“THERE ARE 10 BOYS STANDING IN A QUEUE FOR A TICKET WORTH 5 RS. 5 OF THEM HAVING 5 RS NOTE AND 5 OF THEM HAVING 10 RS NOTE. IN HOW MANY WAYS THEY CAN STAND IN THE QUEUE SUCH THAT NONE HAVE TO WAIT FOR A CHANGE( THE SALESMAN DO NOT HAVE ANY MONEY TO BEGIN WITH). You can change RS with $ if you wish.

Comments are closed.

Share this:

Like this:

Related

8 Comments