Confounding Chessboards!

I begin my blogging career by writing this cute little post on Chessboards and Combinatorics. It is not a great deal but it's a fun way to begin and it also has quite a bit of recall value I must admit for I am constantly besieged by people who often forget the solution to this very trivial problem. And lest my conscience prick me with the proverbial "needle", I admit that I too am of the ilk! :p .Anyhow, the question that concerns us now is to find the number of squares and rectangles in an ordinary 8x8 chessboard. I don't wish to use the vertical line and horizontal line method for this which "en effet" reduces the problem to the simplistic 9C2*9C2=1296 for the rectangles. Oh! the answers by the way are 204 squares and 1296 rectangles(including squares) or 1296-204=1092 pure rectangles!!

The method i propose goes somewhat like this..

1>. The number of squares in a chessboard-

             

The various sizes of the squares can range only from 1x1 to 8x8.

Let us then begin with squares of the 8x8 variety-

Not surprisingly there is only 1 8x8 square in a standard 8x8 chessboard! (what was i even thinking?!!)..not quiet the stuff legends are made of, but I think I should save that for a later post ..

7x7 squares- We need to select 7 squares out of the 8 available, in both the horizontal and vertical directions.
The key point to keep in mind is that all 7 must be together i.e they must  be 7 adjacent horizontal and similar vertical squares. After we get the number of ways in which we can find such squares in both the directions we just need to multiply them together to get the total number of 7x7 squares that exist in the said chessboard.

This same logic is extended to the rest of the problem.

In the horizontal direction, the 7 squares can be selected in-
 fact{(8-7+1)}=fact(2) =2 ways                                                    ; fact()= factorial function

This is because 7 adjacent squares are considered to be a single group leaving just 1 square out and we reduce the problem to the number of ways of finding the arrangements of 2 entities. Proceeding in a similar manner in the vertical direction we also get 2 ways
 for selecting 7 adjacent squares. Multiplying them we thus get 2*2=4 (7x7 squares)

6x6 squares and so on..

To find the number of 6 adjacent squares in horizontal and vertical directions we again take 6 squares to be 1 and reduce our requirement to the finding of the number of ways in which we arrange (8-6+1)=3 entities.
The next obvious step would be to find the factorial of 3 and be done with this part but for the fact that out of the 3 new entities formed 2 are alike and we are not interested in their arrangements. Hence the answer for 6x6 is 3!/(2!)=3 squares in either direction. Thus making a total of 3*3=9  6x6 squares .

We extend the same logic to the rest of the square sizes and end up with the familiar --
8x8= 1^2
7x7= 2^2
6x6= 3^2
5x5=4^2...and so on

Adding it all up we get the total number of squares for the 8x8 chessboard to be 204.

Extending that result to an NxN chessboard we get the general formula for number of squares as summation of (N^2)= {N*(N+1)*(2N+1)}/6 .


2> The number of rectangles in such a chessboard can be found in the same manner but with some changes-

The size of a rectangle can vary from 1x1, 1x2,1x3...8x7,8x8..

A representative example for this which helps lead to the solution is-

The number of  rectangles of size 6x4-- the 6 vertical squares can be selected in fact{(8-6+1)}/fact(2)=fact(3)/fact(2)=3 ways and for each of those 3 ways the 4 horizontal squares can be selected in fact{(8-4+1)}/fact(4)=5 ways . Hence, there are 5*3= 15   6x4 rectangles in a chessboard.

Continuing this way we find that the number of rectangles takes this form.

8(1+2+3+4+5+6+7+8)+7(1+2+3+4+5+6+7+8)....=(1+2+3+4+5+6+7+8)*(1+2+3+4+5+6+7+8)= 1296.

Extending this logic to an NxN chessboard we get the number of rectangles as ={N(N+1)/2}*{N(N+1)/2}
which incidentally is the formula for the summation of N^3.

Thus the number of squares in an NxN chessboard= summation N^2
         "      "          "  rectangles in an NxN chessboard= summation N^3

:)