I am just stuck on a problem for my math class. We were given a large square made up of 16 smaller squares. Our task is to figure out how many rectangles can be drawn on the 4x4 grid. I know that there is supposed to be a pattern, but I cannot figure it out and I cannot figure out how to write an equation. I have started by drawing out the different combinations of rectangles that can be made, but it is not time suffiecient. I don't know another way to go about doing this, and I am not sure how to recognize a pattern in this, so any advice would be super helpful, thank you.
Rectangles in a square grid
- Thread starter Shell
- Start date
I just read Doctor Math's (Doctor Ian's) post to someone named Veronica.
He was supposedly demonstrating the total number of rectangles in a
3 X 3 square grid. He is incorrect. In part, he typed:
For the 3x3 case, that's
1x1 1x2 1x3
(9) (6) (3)
2x1 2x2 2x3 . . . . . . Total = 9 + 6 + 3 + 6 + 4 + 4 + 3 + 4 + 1 = 40
(6) (4) (4)
3x1 3x2 3x3
(3) (4) (1)
----------------------------------------------------------------------
It *should* have been this:
For the 3x3 case, that's
1x1 1x2 1x3
(9) (6) (3)
2x1 2x2 2x3 . . . . . . Total = 9 + 6 + 3 + 6 + 4 + 2 + 3 + 2 + 1 = 36
(6) (4) (2)
3x1 3x2 3x3
(3) (2) (1)
The amendment immediately above is by me, lookagain.
__________________________________________________
**Edit**
To count the number of rectangles in a general n X n rectangle, it is possible
to use a combinatorial argument. For example, in a 4 X 4 square grid,
it is made up by a 5 X 5 grid of points.
Any individual rectangle is formed by 2 distinct points in a row matched with
2 distinct points in a column. It is choosing the number of ways of n points
in a row taken two at a time, multiplied by the number of ways of n points
in a column taken two at a time.
So, for the question of the total number of rectangles in a 4 X 4 \(\displaystyle \ square \ \) grid,
you are looking at a 5 x 5 grid of \(\displaystyle points\ (vertices \ of \ each\)
\(\displaystyle vertical \ and \ horizontal \ rectangle).\)
And (5 choose 2) multiplied by (5 choose 2) =
\(\displaystyle \bigg(\dfrac{5!}{(5 - 2)!(2!)}\bigg) \bigg(\dfrac{5!}{(5 - 2)!(2!)}\bigg) \ = \ \)
\(\displaystyle (10)(10) \ = \ \)
\(\displaystyle 100\)
Last edited:
Lets start with the number of squares.
How many squares and rectangles are on a chess board?
If you determine the number of squares on smaller boards starting with one square you will readily discover a pattern that leads to a simple formula for a board of any number of squares.
A one square board obviously has only one square.
A 2x2 square board has 5 squares, the 4 basic ones and the one large 2x2 one.
A 3x3 square board has 14 squares, the smaller 9 plus 4 2x2's plus 1 3x3 one.
A 4x4 square board has 30 squares, the smaller 16 plus 9 3x3's, plus 4 2x2's plus 1 4x4 one.
Are you beginning to see the pattern?
1x1 - 1^2 = 1
2x2 - 2^2 + 1^2 = 5.
3x3 - 3^2 + 2^2 + 1^2 = 14.
4x4 - 4^2 + 3^2 + 2^2 + 1^2 = 30.
5x5 - 5^2 + 4^2 + 3^2 + 2^2 + 1^1 = 55.
What would your guess be for the number of squares on an 8x8 board? Can you derive a general expression for the answer? If not, see below.
Let N = the total number of squares in a square of nxn squares. Then
N = n^2 + (n-1)^2 + (n-2)^2................(n-n+1)^2 = n(n + 1)(2n + 1)/6
So for the typical chess board problem with 8x8 squares, the total number of definable squares is
N = 8^2 + 7^2 + 6^2 + 5^2 = 4^2 + 3^2 + 2^2 + 1^2 = 8(9)(16+1)/6 = 204.
The derivation of the above formula looks like the following:
From the data above
n................1.....2.....3.....4.....5.....6...
N................1....5....14...30....55...91...
Difference.......4....9....16....25...36
Difference.........5,,,,,7,,,,,9,,,,,11
Difference............2.....2.....2
We have a finite difference sequence with the 3rd differences constant making the general formula for the nth term of the form
..........................N = an^3 + bn^2 + cn + d
Using the tabular data above
a(1)^3 + b(1)^2 + c(1) + d = 1 or a + b + c + d = 1
a(2)^3 + b(2)^2 + c(2) + d = 5 or 8a + 4b + 2c + d = 5
a(3)^3 + b(3)^2 + c(3) + d = 14 or 27a + 8b + 3c + d = 14
a(4)^3 + b(4)^2 + c(4) + d = 30 or 64a + 16b + 4c + d = 30
Solve these and you will have N = n(n + 1)(2n + 1)/6.
A slightly simpler formula would be N = (n - 1) + n^2 but requires you knowing the (n - 1)th term, which then leads to the above formula. It is, however, simpler to derive them starting with 1, making the 2nd term (1 - 1) + 2^2 = 5, the third term 5 +3^2 = 14, the fourth term 14 + 4^2 = 30, the fifth term 30 + 5^2 = 55 and so on.
<---------------------------------------------------------------------------------------------------------------------------------------------------------------------------->
Now we ask ourselves, how many rectangles are there in a square nxn squares big? We count only "rectangles", not the squares which are special cases of rectangles. Remember, only rectangles where the length is longer than the width.
Again, the best way to creep up on a solution is to start out with the small size squares and see where it leads you. For a 2x2 square, we have a total of 4 possible rectangles, each 1x2 squares. For the 3x3 square, we can find 12 1x2 squares, 6 1x3 squares, and 4 2x3 squares for a total of 22 squares. For the 4x4 square, we can find 24 1x2's, 16 1x3's, 8 1x4's, 12 2x3's, 6 2x4's, and 4 3x4's for a total of 70 squares. For the 5x5 square, we get 40 1x2's, 30 1x3's, 20 1x4's, 10 1x5's, 24 2x3's, 16 2x4's, 8 2x5's, 12 3x4's, 6 3x5's, and 4 4x5's.
Did you notice anything as you looked through these nymbers? Lets put them into a tabular form. Along side each nxn square will be the number of squares identified at the top of the column.
1x2 1x3 1x4 1x5 2x3 2x4 2x5 3x4 3x5 4x5 Total
2x2 4 4
3x3 12 6 4 22
4x4 24 16 8 12 6 4 70
5x5 40 30 20 10 24 16 8 12 6 4 170
NOTICE ANYTHING???
1--The number of 1 square wide rectangles in each case is equal to n^2(n-1).
2--The number of 2 square wide rectangles in each case is equal to the number of 1 square wide rectangles in the previous case. The number of 3 square wide rectangles in each case is equal to the number of 2 square wide rectangles in the previous case.
The total number of rectangles in a square of nxn squares is equal to the sum of the 1 square wide rectangles for each rectangle from the 2x2 up to and including the nxn one being considered. Thus, the number of rectangles in a 5x5 square is the sum of the 1 square wide rectangles in the 1x1, 2x2, 3x3, 4x4, and 5x5 squares or 4 + 18 + 48 + 100 = 170. Therefore, for the typical chess board problem of 8x8 squares, we have a total of 4 + 18 + 48 + 100 + 180 + 294 + 448 = 1092.
The general expression for the number of rectangles can be derived from the following extension of our data so far.
Term.........1........2........3.........4.........5........6.........7.........................n = number of cells per side
Squares...1x1....2x2.....3x3.....4x4.....5x5.....6x6.....7x7.....8x8
R..............0........4........22......70......170.....350.....644....1092.............N = number of internal rectangles
1st diff...........4........18......48......100.....180.....294.....448
2nd diff..............14.......30......52........80.....114....154
3rd diff....................16.......22.......28.......34......40
4th diff..........................6.........6.........6........6
Therefore, we have a finite difference series ending in the constant difference of 6. An expression can be derived enabling the definition the nth term of any finite difference series. The expression is a function of the number of successive differences required to reach the constant difference. If the first differences are constant, the expression is of the first order, i.e., N = an + b. If the second differences are constant, the expression is of the second order, i.e., N = an^2 + bn + c. Similarly, constant third differences derive from N = an^3 + bn^2 + cn + d.
Our case will derive from N = an^4 + bn^3 + cn^2 + dn + e.
Using the data points (n1, N1), (n2,N2), (n3,N3), etc., we substitute them into N = an^4 + bn^3 + cn^2 + dn + e as follows:
(n1,N1) = (1,0) produces a(1^4) + b(1^3) + c(1^2) + d(1) + e = 0 or a + b + c + d + e = 0
(n2,N2) = (2,4) produces a(2^4) + b(2^3) + c(2^2) + d(2) + e = 4 or 16a + 8b + 4c + 2d + e = 4
(n3,N3) = (3,22) produces a(3^4) + b(3^3) + c(3^2) + d(3) + e = 22 or 81a + 27b + 9c + 3d + e = 22
(n4,N4) = (4,70) produces a(4^4) + b(4^3) + c(4^2) + d(4) + e = 70 or 128a + 64b + 16c + 4d + e = 70.
The solution to these four expressions leaves us with the number of individual rectangles within a square divided up into nxn smaller squares being R(nxn) = n^4 + 14n^3 - 102n^2 + 197n - 110.
If you want to derive the total number of squares and rectangles, then the total on an 8x8 checkerboard would be 204 + 1092 for a total of 1296, the square of 36.
Letting N(s,r)n = the total number of squares and rectangles in a square of nxn squares, we can also use
N(s,r)n = n(n + 1)(2n + 1)/6 + n(3n^3 + 2n^2 - 3n - 2)/12 = [(n^2 + n)^2]/4
For our 8x8 board, N(s,r)8 = [(n^2 + n)^2]/4 = [(64 + 8)^2]/4 = 1296
4 + 8)^2]/4 = 1296
Now apply the approach to your 16 square square.
How many squares and rectangles are on a chess board?
If you determine the number of squares on smaller boards starting with one square you will readily discover a pattern that leads to a simple formula for a board of any number of squares.
A one square board obviously has only one square.
A 2x2 square board has 5 squares, the 4 basic ones and the one large 2x2 one.
A 3x3 square board has 14 squares, the smaller 9 plus 4 2x2's plus 1 3x3 one.
A 4x4 square board has 30 squares, the smaller 16 plus 9 3x3's, plus 4 2x2's plus 1 4x4 one.
Are you beginning to see the pattern?
1x1 - 1^2 = 1
2x2 - 2^2 + 1^2 = 5.
3x3 - 3^2 + 2^2 + 1^2 = 14.
4x4 - 4^2 + 3^2 + 2^2 + 1^2 = 30.
5x5 - 5^2 + 4^2 + 3^2 + 2^2 + 1^1 = 55.
What would your guess be for the number of squares on an 8x8 board? Can you derive a general expression for the answer? If not, see below.
Let N = the total number of squares in a square of nxn squares. Then
N = n^2 + (n-1)^2 + (n-2)^2................(n-n+1)^2 = n(n + 1)(2n + 1)/6
So for the typical chess board problem with 8x8 squares, the total number of definable squares is
N = 8^2 + 7^2 + 6^2 + 5^2 = 4^2 + 3^2 + 2^2 + 1^2 = 8(9)(16+1)/6 = 204.
The derivation of the above formula looks like the following:
From the data above
n................1.....2.....3.....4.....5.....6...
N................1....5....14...30....55...91...
Difference.......4....9....16....25...36
Difference.........5,,,,,7,,,,,9,,,,,11
Difference............2.....2.....2
We have a finite difference sequence with the 3rd differences constant making the general formula for the nth term of the form
..........................N = an^3 + bn^2 + cn + d
Using the tabular data above
a(1)^3 + b(1)^2 + c(1) + d = 1 or a + b + c + d = 1
a(2)^3 + b(2)^2 + c(2) + d = 5 or 8a + 4b + 2c + d = 5
a(3)^3 + b(3)^2 + c(3) + d = 14 or 27a + 8b + 3c + d = 14
a(4)^3 + b(4)^2 + c(4) + d = 30 or 64a + 16b + 4c + d = 30
Solve these and you will have N = n(n + 1)(2n + 1)/6.
A slightly simpler formula would be N = (n - 1) + n^2 but requires you knowing the (n - 1)th term, which then leads to the above formula. It is, however, simpler to derive them starting with 1, making the 2nd term (1 - 1) + 2^2 = 5, the third term 5 +3^2 = 14, the fourth term 14 + 4^2 = 30, the fifth term 30 + 5^2 = 55 and so on.
<---------------------------------------------------------------------------------------------------------------------------------------------------------------------------->
Now we ask ourselves, how many rectangles are there in a square nxn squares big? We count only "rectangles", not the squares which are special cases of rectangles. Remember, only rectangles where the length is longer than the width.
Again, the best way to creep up on a solution is to start out with the small size squares and see where it leads you. For a 2x2 square, we have a total of 4 possible rectangles, each 1x2 squares. For the 3x3 square, we can find 12 1x2 squares, 6 1x3 squares, and 4 2x3 squares for a total of 22 squares. For the 4x4 square, we can find 24 1x2's, 16 1x3's, 8 1x4's, 12 2x3's, 6 2x4's, and 4 3x4's for a total of 70 squares. For the 5x5 square, we get 40 1x2's, 30 1x3's, 20 1x4's, 10 1x5's, 24 2x3's, 16 2x4's, 8 2x5's, 12 3x4's, 6 3x5's, and 4 4x5's.
Did you notice anything as you looked through these nymbers? Lets put them into a tabular form. Along side each nxn square will be the number of squares identified at the top of the column.
1x2 1x3 1x4 1x5 2x3 2x4 2x5 3x4 3x5 4x5 Total
2x2 4 4
3x3 12 6 4 22
4x4 24 16 8 12 6 4 70
5x5 40 30 20 10 24 16 8 12 6 4 170
NOTICE ANYTHING???
1--The number of 1 square wide rectangles in each case is equal to n^2(n-1).
2--The number of 2 square wide rectangles in each case is equal to the number of 1 square wide rectangles in the previous case. The number of 3 square wide rectangles in each case is equal to the number of 2 square wide rectangles in the previous case.
The total number of rectangles in a square of nxn squares is equal to the sum of the 1 square wide rectangles for each rectangle from the 2x2 up to and including the nxn one being considered. Thus, the number of rectangles in a 5x5 square is the sum of the 1 square wide rectangles in the 1x1, 2x2, 3x3, 4x4, and 5x5 squares or 4 + 18 + 48 + 100 = 170. Therefore, for the typical chess board problem of 8x8 squares, we have a total of 4 + 18 + 48 + 100 + 180 + 294 + 448 = 1092.
The general expression for the number of rectangles can be derived from the following extension of our data so far.
Term.........1........2........3.........4.........5........6.........7.........................n = number of cells per side
Squares...1x1....2x2.....3x3.....4x4.....5x5.....6x6.....7x7.....8x8
R..............0........4........22......70......170.....350.....644....1092.............N = number of internal rectangles
1st diff...........4........18......48......100.....180.....294.....448
2nd diff..............14.......30......52........80.....114....154
3rd diff....................16.......22.......28.......34......40
4th diff..........................6.........6.........6........6
Therefore, we have a finite difference series ending in the constant difference of 6. An expression can be derived enabling the definition the nth term of any finite difference series. The expression is a function of the number of successive differences required to reach the constant difference. If the first differences are constant, the expression is of the first order, i.e., N = an + b. If the second differences are constant, the expression is of the second order, i.e., N = an^2 + bn + c. Similarly, constant third differences derive from N = an^3 + bn^2 + cn + d.
Our case will derive from N = an^4 + bn^3 + cn^2 + dn + e.
Using the data points (n1, N1), (n2,N2), (n3,N3), etc., we substitute them into N = an^4 + bn^3 + cn^2 + dn + e as follows:
(n1,N1) = (1,0) produces a(1^4) + b(1^3) + c(1^2) + d(1) + e = 0 or a + b + c + d + e = 0
(n2,N2) = (2,4) produces a(2^4) + b(2^3) + c(2^2) + d(2) + e = 4 or 16a + 8b + 4c + 2d + e = 4
(n3,N3) = (3,22) produces a(3^4) + b(3^3) + c(3^2) + d(3) + e = 22 or 81a + 27b + 9c + 3d + e = 22
(n4,N4) = (4,70) produces a(4^4) + b(4^3) + c(4^2) + d(4) + e = 70 or 128a + 64b + 16c + 4d + e = 70.
The solution to these four expressions leaves us with the number of individual rectangles within a square divided up into nxn smaller squares being R(nxn) = n^4 + 14n^3 - 102n^2 + 197n - 110.
If you want to derive the total number of squares and rectangles, then the total on an 8x8 checkerboard would be 204 + 1092 for a total of 1296, the square of 36.
Letting N(s,r)n = the total number of squares and rectangles in a square of nxn squares, we can also use
N(s,r)n = n(n + 1)(2n + 1)/6 + n(3n^3 + 2n^2 - 3n - 2)/12 = [(n^2 + n)^2]/4
For our 8x8 board, N(s,r)8 = [(n^2 + n)^2]/4 = [(64 + 8)^2]/4 = 1296
4 + 8)^2]/4 = 1296
Now apply the approach to your 16 square square.
Last edited:
I will make sure this is duly etched on his tombstone
I sent Dr. Ian an e-mail about it.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\(\displaystyle \text{Continuing with my general formula for the number of}\)
\(\displaystyle \text{squares and non-square rectangles . . . }\)
An n by n square grid of smallest squares translates to an
(n + 1) by (n + 1) square grid of points.
\(\displaystyle [C(n + 1, \ 2)][C(n + 1, \ 2)] = \)
\(\displaystyle \bigg(\dfrac{n(n + 1)}{2}\bigg)\bigg(\dfrac{n(n + 1)}{2}\bigg) = \)
\(\displaystyle \dfrac{n^2(n + 1)^2}{4} \ \ \ \ for \ a \ simplified \ formula \ of \ all\)
\(\displaystyle . \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ square/non-square \ rectangles\)
\(\displaystyle \text{So, for an 8 by 8 square formation of squares, }\)
\(\displaystyle \text{the total number of rectangles is }\)
\(\displaystyle \dfrac{(8)^2(9)^2}{4} = \)
\(\displaystyle \dfrac{64(81)}{4} = \)
\(\displaystyle \boxed{1,296}\)