1
$\begingroup$

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?

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

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.

$\endgroup$
10
  • $\begingroup$ first choosing the horizontal lines at top and bottom of the rectangle what do you mean by this? $\endgroup$ – Jim Jan 26 at 21:52
  • 1
    $\begingroup$ 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. $\endgroup$ – S. Dolan Jan 26 at 21:54
  • $\begingroup$ 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? $\endgroup$ – Jim Jan 26 at 21:57
  • $\begingroup$ The combinations formula is for a choice of two different lines. $\endgroup$ – S. Dolan Jan 26 at 21:59
  • $\begingroup$ $\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? $\endgroup$ – Jim Jan 26 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.