I am looking into the puzzle count the number of rectangles in a regular $8*8$ chessboard.
For a 1 by 1 chessboard there are 0 rectangles
For a 2 by 2 chessboard there are 4 rectangles (2 by 1)
For a 3 by 3 chessboard there are 6 rectangles of 1 by 2, 3 rectangles of 1 by 3, 6 rectangles of 2 by 1 and 3 rectangles of 3 by 1 i.e. total 22
For a 4 by 4 rectangles there are 56 rectangles in total (12 of 1 by 2, 12 of 2 by 1, 8 of 2 by 4, 8 of 4 by 2, 4 of 1 by 4, 4 of 4 by 1, 2 of 2 by 4, 2 of 4 by 2, 2 of 3 by 4, 2 of 4 by 3).
So we have the following sequence (4, 22, 56, ...):
| 2 $\times$ 2 | 3 $\times$ 3 | 4 $\times$ 4 | 5 $\times$ 5 | 6 $\times$ 6 | 7 $\times$ 7 | 8 $\times$ 8 |
|---|---|---|---|---|---|---|
| 4 | 22 | 56 |
I can't see a pattern in the sequence. Is there one that I am missing?
Counting all rectangles (i.e. including squares) can be done be first choosing the horizontal lines at top and bottom of the rectangle. This can be done in $\begin{pmatrix}n+1\\2\\\end{pmatrix}$ ways.
The same is true for the vertical lines. So the total is $\begin{pmatrix}n+1\\2\\\end{pmatrix}^2.$
If you want to exclude squares then you can find them separately and subtract from the total.