How to Count Rectangles!

Hi there! Me again. *munches*

Sorry, I still haven't finished my hamburger since the last time we count squares, I hope you don't mind that.

Anyway, we are here to see how to count rectangles of a certain size in a grid.

Consider this question: How many 3×23\times2 rectangles are there in the 4×54\times5 grid below?

I'm a little bit picky here, note that dimensions here are expressed as width×\timesheight, so in this case I only want 3×23\times2 rectangles (that is, a rectangle of width 3 and height 2) and not the 2×32\times3 ones.

If we mark an 'X' on every bottom-right corner of every 3×23\times2 rectangle, we would see this:

Hey, that means counting the number of 3×23\times2 rectangles in the original grid is the same as counting how many X's are there, or in other words, it is the same as counting the number of unit squares in an 2×42\times4 grid.

There are 2×4=82\times4=8 unit squares in a 2×42\times4 grid, therefore, the number of 3×23\times2 rectangles in the original grid is 8! Hooray!

*munches*


Mmm... so in general, how many x×yx\times y rectangles (xx is the width of the rectangle, yy is the height of the rectangle) are there in an a×ba\times b grid (aa is the width of the grid, bb is the height of the grid), given that xax\leqslant a and yby\leqslant b?

Again imagine marking an 'X' on every bottom-right corner of every x×yx\times y rectangle, we will get a grid full of X's.

The width of the "X grid" is ax+1a-x+1, while the height of the "X grid" is by+1b-y+1.

Since the number of x×yx\times y rectangles in an a×ba\times b grid equals the number of unit squares in the "X grid", hence the number of x×yx\times y rectangles in an a×ba\times b grid is (ax+1)(by+1)(a-x+1)(b-y+1)

*munches*

The number of x×yx\times y (xx is the width of the rectangle, yy is the height of the rectangle) rectangles (the exact x×yx\times y rectangle, not including rotated variations such as y×xy\times x) in an a×ba\times b grid (aa is the width of the grid, bb is the height of the grid) provided that xax\leqslant a, yby\leqslant b is (ax+1)(by+1)(a-x+1)(b-y+1)


This is one part of Quadrilatorics.

Note by Kenneth Tan
3 years, 5 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

I think another way to do it is breaking them up. For example, if we want to count the number ot rectangles in 10×1010×10 grid, is first counting the number of rectangles in 10×110×1 grid then xounting the number of rectangles in 10×210×2 grid, then in 10×310×3, and so in, in this way we would be able to establish a pattern in the number of rectangles, and by arithmetic/geometric progression, we would het the answer.

Ashish Siva - 3 years, 5 months ago

Log in to reply

Yes, but in this case I only want to count rectangles of a specific size.

Kenneth Tan - 3 years, 5 months ago

Log in to reply

We can do in that case too. Your questions are awesome.

Ashish Siva - 3 years, 5 months ago

Log in to reply

You may see the solution of my problem to see my approach.

Ashish Siva - 3 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...