# Counting chessboard rectangles

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?

• In the preview the table looks ok – Jim Jan 26 at 21:30
• I thought this syntax for the tables should work meta.stackexchange.com/questions/356997/… – Jim Jan 26 at 21:33
• Does it help to insert an empty line before (and after) the table? – Martin R Jan 26 at 21:35
• @MartinR: That worked! – Jim Jan 26 at 21:39
• What exactly counts as a rectangle? What about 1x1 rectangles? Or 2x2, 2x3, 3x3 on the 3 by 3 board? Etc ... – Martin R Jan 26 at 21:43

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.$$
• first choosing the horizontal lines at top and bottom of the rectangle what do you mean by this? – Jim Jan 26 at 21:52
• A rectangle has a top and a bottom edge. There are $n+1$ possibilities for these two lines ranging from $0$, bottom line, to $n$, top line. – S. Dolan Jan 26 at 21:54
• By multiplying i.e. $\begin{pmatrix}n+1\\2\\\end{pmatrix}^2.$ aren't we including invalid configurations? I.e. 2 lines on the left with vertical lines on the right that don't form a shape? – Jim Jan 26 at 21:57
• $\begin{pmatrix}n+1\\2\\\end{pmatrix}$ is all possible choices of 2 horizontal lines from the 9 right? The same for vertical. What I don't get is how will the multiplication not include invalid combinations. Would it be possible to elaborate a bit on that? – Jim Jan 26 at 22:02