13

Is there a formula to evaluate the number of all squares in the $m \times n$ grid? Well, I'm just curious, I've seen the question like this somewhere at the university, to solve this they were dividing the grid with $m - 1$ and $n - 1$ lines...I don't know what's next.

Sepideh Bakhoda
  • 5,816
khernik
  • 1,369

2 Answers2

20

Suppose $n\ge m$.

  • Number of squares of size 1: $m\cdot n$
  • Number of squares of size 2: $(m-1)\cdot (n-1)$
  • ...
  • Number of squares of size m: $1\cdot (n-m+1)$

Result: $$\begin{align} \sum_{k=1}^m k \cdot (n-m+k) & =(n-m)\sum_{k=1}^m k +\sum_{k=1}^m k^2 \\ & = (n-m) m(m+1)/2 + m(m+1)(2m+1)/6 \\ & = \frac{m(m+1) (3n-m+1)}{6}\end{align}$$

MJD
  • 65,394
  • 39
  • 298
  • 580
Phira
  • 20,860
1

Rectangles in rectangle $$\frac{(n^2+n)(m^2+m)}{4}$$

Rectangles in square $$\frac{(n^2+n)^2}{4}$$

Squares in rectangle $$m≥ n-1,\frac{(n^2+n)}{2}m-\frac{(n^3-n)}{6}$$

Squares in square $$\frac{(n^2+n)(2n+1)}{6}$$

Michael
  • 197
  • Where does the first formula come from? Is that clear? – Joe Tait Feb 25 '14 at 19:12
  • @JoeTait: There are $n+1$ horizontal lines, of which you pick two. There are $m+1$ vertical lines, of which you pick two. – Ross Millikan Feb 25 '14 at 19:16
  • @RossMillikan How can I get the total number of rectangles in different sizes in a rectangular grid of mXn. For example : let say m=2 and n=2, have total of 9 rectangles. 4 are of size 1, 4 are of size 2 and 1 is of size 3. than how to calculate all the rectangles of size 1X1, 1X2, 2X1, 2X2 .... – pa1pal Feb 09 '16 at 16:40
  • 1
    @pa1pal: Let us have a grid $6 \times 8$ and look for the number of $2 \times 3$ rectangles. There are $7$ horizontal lines and you can choose any of $5$ of them to be the top edge of your rectangle. There are $9$ vertical lines and you can choose any of $6$ of them to be the left edge. There are therefore $5 \cdot 6=30$ rectangles that are $2$ high and $3$ wide. – Ross Millikan Feb 09 '16 at 16:48
  • @RossMillikan Got it. If I want to look for 1 x 2 so I have to choose any 6 rows and any 7 vertical lines. Total of 6*7=42 rectangles. Now In a 6 x 8 grid there are total of 756 unit squares present. If I want to have a number of rectangles which comprises of 1 square, 2 square, 3 square and so on ... One way is I can calculate all the 1 x 2 and 2 x 1 rectangles and add them for the case of 2 squares. Is there any other way ? – pa1pal Feb 09 '16 at 17:02
  • @pa1pal: how do you get 756 unit squares in a 6 x 8 grid? I only get 48. – Ross Millikan Feb 09 '16 at 19:52
  • @RossMillikan sorry not unit squares. But the total number of rectangles in a m x n grid. Which is (n)(n+1)*(m)(m+1) / 4 – pa1pal Feb 10 '16 at 11:04