How Many Squares on a Chessboard?

And if you stop by Washington Square Park in NYC, or Harvard Square in Cambridge, you could ask, how many chessboards on a square?

I'll see myself out.

There's a much simpler explanation. 

The number of proper rectangles formed by the lines on a chessboard is simply the number of non-vertical, non-horizontal diagonals you can draw on a 9x9 grid of dots, each diagonal formed with exactly 2 points.

You have 81 choices for the first point, and 81 - (16+1) choices for the second point, since you can't choose any points in the same row/column of your first chosen point, nor can you choose the first point itself. 

Since this method counts each diagonal 4 times, the final count is just 81*64/4 = 1296. 

So the general rule, as someone mentioned earlier, would just be n^2(n+1)^2/4, for the number of proper rectangles on an n by n board. 

Since you see such a simple expression for this formula, that generally implies some intuitive explanation, and a simple one at that.

The first intuitive explanation is simply what I said though - you have an (n+1) by (n+1) grid of dots, and after choosing the first dot, you've eliminated one row, and one column, and so you must now choose the second dot from an n by n board, and divide by 2, since you count each diagonal twice.

But if you also note that n(n+1)/2 is the sum of the first n naturals, you might be able to come up with a much cleverer explanation still. I can't think of one right now though. 

Whoa, that's a great way to explain it. Where did you learn this?

Well, I'm studying math. I also did competitive math in high school, where this kind of stuff is commonplace. 

Although you'd have to divide by 4, not 2.

So basically you've solved similar problems, ok that makes sense.

I don't know why 81*64/2 doesn't work though. Just visualizing it and what you said that seems to make sense.,,

Oh, because a rectangle has 4 corners (2 diagonals) so you're actually counting them 4 times.

Easy - 64 + 49 + 36 + 25 + 16 + 9 + 4 + 1, which is 204

This is also easy.  Base it on the upper left corner.  There are 64 rectangles with a8 as the upper left corner.  56 with b8 as the upper left corner.  48 with c8, etc.  56 with a7 as the upper left corner, 49 with b7, 42 with c7, etc.

So it's the Sum of 1 to 8 times 8 plus the sum of 1 to 8 times 7, plus ... plus the sum of 1 to 8 times 1.

The sum of 1 to 8 is 36, so it's 36 * 8 + 36 * 7 + 36 * 6 + 36 * 5 + 36 * 4 + 36 * 3 + 36 * 2 + 36 * 1 which is also 36 * (8 + 7 + 6 + 5 + 4 + 3 + 2 + 1) which is 36 * 36 which is 1296.

So 1296 Rectangles, of which 204 of them are also squares.

There are no squares on a chessboard, however there are two playing.

You're right - it's 4. So in fact you have to divide by 4 in both my formulas, which I've edited. 

This kind of approach may seem clever, but if you take a combinatorics/counting class, you learn standard counting techniques, which can extend to many different counting scenarios by forming a correspondence between the two scenarios. 

Here, there's the correspondence between the rectangles and diagonals. 

Something that's more illustrative is asking: if a,b,c are whole numbers {0,1,2,...}, then how many different (a,b,c) triples are possible such that a+b+c = 8? Or something similar. 

Then the correspondence is that you can have _ _ _ _ _ _ _ _ _ _  (10 slots), where you place 2 dividers onto 2 of the slots. Then the number of empty slots before the first divider is "a", then "b" is the next number, then "c", and notice how you just need to count how many ways you can put 2 slots onto 10 slots, which is 10 choose 2. 

Stuff like this is why I chose to study math - very nice, elegant patterns, etc. 

or in other and more simpler words....they are already counted....

Another "trick" you have is: What is the probability that if you roll 3 fair dice, that the numbers will appear in strictly ascending order? 

There are 6^3 ways of rolling the dice to get a sequence of numbers. 

But if you want ascending order, instead of doing the count, you can see it's the correspondence between selecting 3 distinct numbers from {1,2,3,4,5,6}, because once you've selected them, there's only one way to order them.

So it's just (6 choose 3) / 216, as the probability, which is 5/54. 

But I'm going off topic.

The problem's been solved anyways.

I am used to (at least the basic) combinations and permutations questions... like how many arrangements of ___ letters thing. But using diagonals to represent rectangles was new to me, and pretty cool I thought.

Yeah, but if you're explaining to a confused person, saying it in the most compact way is not helpful.

The pattern, as you alluded to, is  1^2, (1+2)^2, (1+2+3)^2, (1+2+3+4)^2......... or ­(Σn)^2.  When you expand the statement, it shows you both the number and size of the rectangles (one being the reverse of the other).  (1+2+3)^2 = (1+2+3)(1+2+3) = 1 + 2 + 3 + 2 + 4 + 6 + 3 + 6 + 9 = 36.  If you take this as the number of rectangles, then the sizes of the rectangles are 9, 6, 3, 6, 4, 2, 3, 2, 1.

for number of rectangles there is only simple formula (n+1 choose 2) to be squared = 36 time 36 = 1296 ye iz correct