Counting Rectangles in an n X m Checked Board

We have a checked board like a chess board, but instead of 8 x 8 it has a dimension of n x m . The task is to count the number of rectangles of all possible dimensions i x j in that checked board. Also the question arises how many squares of all possible dimensions are there. We will solve this problem by establishing formulas by construction. After this we can calculate the number of rectangles and squares of a Chess Board or any other such checked board.

Counting all Rectangles

Let there be an n X m checked board with n rows and m columns. In the checked board the smallest rectangle will be referred as boxes. We have to find out how many rectangles can be made with such smallest boxes.

We can select n boxes along the horizontal and for each such selected n boxes, we can select m boxes along the vertical. This will make n X m boxes of dimension 1 X 1

We can select n boxes along the horizontal and for each such selected n boxes, we can select 2 adjacent boxes along the vertical in (m-1) ways. This makes n X (m-1) boxes of dimension 1 X 2

Note that the two boxes selected are adjacent, and thus can be selected only in a way for example (1,2), (2,3), (3,4), ..., (k, k+1)..., (m-1,m) making (m-1) pairs.

Similarly, for each n boxes selected along the horizontal, 3 adjacent boxes along the vertical can be selected in (m-2) ways, making n X (m-2) boxes of dimension 1 X 3

Thus selecting n boxes along the horizontal we can select i adjacent boxes in (m-(i-1)) = (m-i+1) ways, which will make n X (m-i+1) boxes of dimension 1 X i, with i=1,2, ..., m

Therefore total boxes of dimension 1 X i is :

$n\times(m-0)+n\times(m-1)+n\times(m-2)+n\times(m-3)+\ldots\ldots+n\times(m-i+1)+\ldots\ldots+n\times3+n\times2+n\times1=n\sum_{i=1}^{m}i$

When we have finished with counting the number of boxes of dimension 1 X i we now count all boxes of 2 X i. This is counted similarly like the above process.

We can select 2 adjacent boxes along the horizontal in (n-1) ways and for each such selected 2 adjacent boxes we can select (m-i+1) boxes along the vertical as before, with i=1,2, ..., m
Similarly it makes $(n-1)\sum_{i=1}^{m}i$ rectangle of dimension 2 X i, and with the same approach it makes $(n-2)\sum_{i=1}^{m}i$ rectangles of dimension 3 X i .

Generally, j adjacent boxes can be selected along the horizontal in (n-j+1) ways, and for each such selected j adjacent box, we can select i adjacent boxes along the vertical in (m-i+1) ways, and makes boxes of i X j dimension.

Therefore the total boxes of dimension i X j for i=1,2, ... , m, and j=1,2, ... ,n are :

$(n-0)\times\sum_{i=1}^{m}i+(n-1)\times\sum_{i=1}^{m}i+(n-2)\times\sum_{i=1}^{m}i+(n-3)\times\sum_{i=1}^{m}i+\ldots\ldots+(n-j+1)\times\sum_{i=1}^{m}i+\ldots\ldots+3\times\sum_{i=1}^{m}i+2\times\sum_{i=1}^{m}i+1\times\sum_{i=1}^{m}i$
$= \left(\sum_{i=1}^{m}i\right)\times\left((n-0)+(n-1)+(n-2)+(n-3)+\ldots\ldots+(n-j+1)+\ldots\ldots+3+2+1\right)$
$= \left(\sum_{i=1}^{m}i\right)\times\left(\sum_{j=1}^{n}j\right)=\frac{m(m+1)}{2}\times\frac{n(n+1)}{2}$

With this formula we can count the number of all possible dimension rectangles in a Chess Board, which has 8 X 8 boxes. Therefor n = 8, m = 8

$\left(\sum_{i=1}^{8}i\right)\times\left(\sum_{j=1}^{8}j\right)=\frac{8(8+1)}{2}\times\frac{8(8+1)}{2}=36\times36=1296$

Rectangles of all possible Dimensions in a n X m checked board = $\left(\sum_{i=1}^{m}i\right)\times\left(\sum_{j=1}^{n}j\right)=\frac{m(m+1)}{2}\times\frac{n(n+1)}{2}$

Counting all Squares

To find the number of all possible dimension squares in the n X m checked board, we should select as described below:

After we select i adjacent boxes in (n-i+1) ways, we only select i adjacent boxes along the vertical which can be done is (m-i+1) ways. That is we select the same dimensions along the horizontal and the vertical to keep the selection a square. Note that if $m\geq n$ then we cannot select more than n adjacent boxes. The maximum number of boxes we can select adjacent is n boxes, because adjacent boxes greater than n will not exist in one of the dimensions. This will make the maximum dimension of the squares to be min{n,m} X min{n,m}. So in this method all the i X i dimension boxes will be selected. i = 1,2, ..., min{m,n}

Therefore the number of squares could be calculated by:

Taking $m\geq n$

$n\times m+(n-1)\times(m-1)+(n-2)\times(m-2)+(n-3)\times(m-3)+\ldots+(n-i+1)\times(m-i+1)+\ldots+2\times(m-2)+1\times(m-1)$
$= \sum_{i=0}^{n-1}(n-i)\times(m-i)=\sum_{i=1}^{n}i\times(m-n+i)=(m-n)\times\sum_{i=1}^{n}i+\sum_{i=1}^{n}i^{2}$
$= (m-n)\times\sum_{i=1}^{n}i+\sum_{i=1}^{n}i^{2}=(m-n)\times\frac{n(n+1)}{2}+\frac{n(n+1)(2n+1)}{6}$
$=\frac{3n(m-n)(n+1)+n(n+1)(2n+1)}{6}=\frac{n(n+1)\times(3(m-n)+(2n+1))}{12}=\frac{n(n+1)\times(3m-n+1)}{6}$

In the case of a Chess Board of 8 X 8 checked boxes, we have m = 8, n = 8

$(8-8)\times\sum_{i=1}^{8}i+\sum_{i=1}^{8}i^{2}=0+\frac{8(8+1)(2\times8+1)}{6}=204$

Therefore there are 204 squares of all possible dimensions in a Chess Board.

For a 5 X 3 checked board m = 5 and n = 3

$(5-3)\times\sum_{i=1}^{3}i+\sum_{i=1}^{3}i^{2}=2\times6+14=26$

Squares of all possible dimensions in a n X m checked board with $m\geq n$ = $(m-n)\times\sum_{i=1}^{n}i+\sum_{i=1}^{n}i^{2}=\frac{n(n+1)\times(3m-n+1)}{6}$

Counting Rectangles that are not Squares

We can calculate the number of rectangles which are not square in a checked board with n X m boxes by subtracting the previous formulas

$\left(\sum_{i=1}^{m}i\right)\times\left(\sum_{j=1}^{n}j\right)-\left((m-n)\times\sum_{i=1}^{n}i+\sum_{i=1}^{n}i^{2}\right)$ with $m\geq n$

So we get there are 1296 – 204 = 1092 rectangle of all dimensions which are not squares in a Chess Board.

9 thoughts on “Counting Rectangles in an n X m Checked Board”

jay.me says:

April 21, 2010 at 1:09 am

Hi Arjun =) You like math dont you, -looks like you are pretty good at it =)

1. phoxis says:
  
  April 21, 2010 at 1:10 pm
  
  This is the subject what i study in university. computer science. But don’t draw early conclusions that i am good at maths!
  
jay.me says:

April 23, 2010 at 6:11 pm

cool, …I still think you are =)

mayur rajpoot says:

February 28, 2013 at 10:45 pm

it’s very important for me…….
thanking you…..

Anonymous says:

May 15, 2014 at 5:51 pm

fantastic article. very well written and explained. Thank you

jamesjohnson20 says:

May 15, 2015 at 11:44 pm

hi ,
Thanks for making it clear. I was not able to find such clear explanation .and i have one doubt. After the step “Taking m > n” , In the second bullet point can you make it clear please

jamesjohnson20 says:

May 16, 2015 at 12:15 am

can you explain how this step \sum_{i=0}^{n-1}(n-1)\times(m-i) has transformed into \sum_{i=1}^{n}i\times(m-n+1) please

Ashfaq says:

February 23, 2016 at 6:58 am

You are a champ!!

Aakash says:

May 13, 2016 at 8:58 pm

i can’t under stand what Therefore total boxes of dimension 1 X i is :

n\times(m-0)+n\times(m-1)+n\times(m-2)+n\times(m-3)+\ldots\ldots+n\times(m-i+1)+\ldots\ldots+n\times3+n\times2+n\times1=n\sum_{i=1}^{m}i

this means.

plz can someone explain how to Count Rectangles in an n X m Checked Board. plzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz