The problem
How many rectangles (with sides horizontal and vertical) can be made by choosing lattice points as vertices on an n × n grid?
First, be clear about what's being asked
- A lattice point is a point where grid lines cross, so both its coordinates are whole numbers.
- An n × n grid here means n small squares across and n up. So it has (n + 1) × (n + 1) lattice points. A chessboard is an 8 × 8 grid with 9 × 9 = 81 lattice points.
- All four corners must be lattice points, and the sides must run along the grid (no tilting).
- Squares count as rectangles. So does the whole grid.
Before doing any maths: how many rectangles do you think there are on an 8 × 8 chessboard? Write down your guess. We'll check it at the end.
Play with it
Click a lattice point, then click the opposite corner to make a rectangle. Challenge: find every rectangle on the 2 × 2 grid. Then try the 3 × 3 grid.
Notice how easy it is to miss one, or to count one twice. To be sure, we need a system. The rest of this guide builds one.
Step 1 · Translate it into maths
Can you reduce this problem to a simple mathematical, logical or algebraic statement?
A rectangle is a picture, and pictures are hard to count. Lists of numbers are much easier to count. So ask: what is the least information that pins down one rectangle exactly?
Make some rectangles below and watch their coloured "shadows" on the two axes.
What rules must those numbers obey?
Call the edges x1, x2, y1, y2. Which values are allowed? Can x1 = x2? Does the order matter?
Show the rules
0 ≤ x1 < x2 ≤ n and 0 ≤ y1 < y2 ≤ n
- Whole numbers from 0 to n, because the corners are lattice points on the grid.
- Strictly less than, because if x1 = x2 the "rectangle" is squashed flat into a line.
- In order (left before right), because otherwise we'd count every rectangle twice: once as (1, 3) and once as (3, 1).
The number of rectangles = the number of ways to choose whole numbers x1, x2, y1, y2 with 0 ≤ x1 < x2 ≤ n and 0 ≤ y1 < y2 ≤ n.
Every rectangle gives exactly one such list, and every such list gives exactly one rectangle, so the two match up perfectly. Keep this statement in mind: in Step 5 you'll find it was almost the whole answer.
Step 2 · Split it into parts
Can you split this problem up into distinct parts that are each easier to count?
We want to sort the rectangles into groups so that every rectangle lands in exactly one group, with no gaps and no double counting. Some ways to group them:
- by shape: all the 1 × 1s, all the 2 × 1s, all the 1 × 2s, …
- by whether it's a square or not
- by where its bottom-left corner is
Which grouping makes each group easy to count?
Grouping by shape. All rectangles with the same shape are copies of each other slid around the grid. Counting one group means answering a single question: how many places can this shape sit?
Careful: a 2 × 1 (2 wide, 1 tall) and a 1 × 2 are different rectangles on the grid, so they're different groups.
How many places can one shape sit?
Choose a grid size and a shape. Predict the number of positions, then slide the shape around to check.
The general rule
An a × b rectangle (width a, height b) on an n × n grid can have its left edge at x = 0, 1, …, n − a and its bottom edge at y = 0, 1, …, n − b. These two choices don't affect each other, so we multiply:
positions of an a × b rectangle = (n − a + 1)(n − b + 1)
So here's the plan: for every shape a × b, count its positions, then add up over all the shapes. That's a lot of shapes, though, so let's warm up on an easier version first.
Step 3 · Solve a simpler case: squares
Is there a simpler version of the problem you can solve first?
Squares are rectangles where width = height. Instead of two numbers (a and b) there's only one: the side length k. It's the same method with fewer shapes.
Count the squares on small grids
Add up the squares of every size. Use the explorer if you need to.
The pattern for squares
A k × k square fits in (n − k + 1)² places. Adding over k = 1, 2, …, n:
S(n) = n² + (n − 1)² + … + 2² + 1² = n(n + 1)(2n + 1)6
The last step is the well-known formula for the sum of the first n square numbers. Check: S(3) = 3 · 4 · 7 ÷ 6 = 14 ✓
The method works: group by shape → count the positions of each shape → add up. Now let's use it on all rectangles.
Step 4 · Small cases, then look for a pattern
Can you do it for n = 1, n = 2, n = 3? Is there a pattern: is it linear, polynomial or exponential?
The shape table
Each cell is one shape, with the width across the top and the height down the side. Predict how many places the shape fits, then click the cell to check.
Totals
Add up every cell of the table for that grid size.
What kind of growth is this?
Type in your totals (or load them) and look at the differences between terms and the ratios of terms.
- Linear: the 1st differences are constant.
- Polynomial of degree d: the dth differences are constant.
- Exponential: the ratios are constant.
So R(n) grows like…
Look harder at the numbers
1, 9, 36, 100, 225, …
What kind of numbers are these? And what about the 1st differences 8, 27, 64, 125?
Show what's hiding
They're perfect squares: 1², 3², 6², 10², 15². And 1, 3, 6, 10, 15 are the triangular numbers 1, 1 + 2, 1 + 2 + 3, …
The differences are perfect cubes: 2³, 3³, 4³, 5³. So R(n) is also 1³ + 2³ + … + n³.
A conjecture:
R(n) = (1 + 2 + … + n)² = (n(n + 1)2)²
But a pattern from four or five cases isn't a proof. Why should the answer be a perfect square? Time to look back.
Step 5 · Look back: is there an even simpler view?
You solved it by counting the shapes systematically and grouping them cleverly. Now look back: is there an even simpler way to see it?
Your shape table, one more time
Here's the shape table with every count filled in and the row totals added. Now tick Relabel. Instead of labelling by width and height, it labels each column by its number of positions across (i) and each row by its number of positions up (j). What famous table appears?
Writing it as a sum over i and j
The shape-by-shape count is a double sum over widths a and heights b:
R(n) = n∑a=1n∑b=1 (n − a + 1)(n − b + 1)
Now substitute i = n − a + 1 (positions across) and j = n − b + 1 (positions up). As a runs 1 → n, i runs n → 1. They're the same numbers in reverse order, so:
R(n) = n∑i=1n∑j=1 i · j
So what does the double sum equal?
n∑i=1n∑j=1 i · j = (n∑i=1 i)(n∑j=1 j) = (1 + 2 + … + n)²
The double sum factorises into (a sum across) × (a sum up). That's why the answer is a perfect square: the across part and the up part never interact.
What does 1 + 2 + … + n count by itself?
It answers a 1-dimensional version of the problem: how many segments can you make by choosing 2 of the n + 1 points on a line?
Back to the statement from Step 1
Remember: a rectangle is just a choice of x1 < x2 and y1 < y2. In other words, pick 2 of the n + 1 vertical grid lines and 2 of the n + 1 horizontal grid lines. Try it:
R(n) = n+12 × n+12 = (n(n + 1)2)²
Choose the left and right sides, then choose the bottom and top. The two choices are independent. A chessboard has 92 = 36 choices each way, so it has 36² = 1296 rectangles.
Which way was better?
Both! Counting shape by shape is a general method. It's what worked for squares, where width and height are tied together so the sum doesn't factorise. The look-back view explains the answer: it's a perfect square because a rectangle is two independent 1-dimensional choices.
Step 6 · Check it, then push further
Your guess
Computer check
This counts every rectangle by brute force (it tries every x1 < x2, y1 < y2) and compares the result with the formulas.
Extensions
How many rectangles are there on an m × n grid (m across, n up)?
Answer
m+12 × n+12 = m(m+1)n(n+1)4
The two choices are still independent. They just come from different numbers of lines.
How many rectangles on a chessboard are not squares?
Answer
1296 − 204 = 1092. That's over 84% of them!
What if "n × n grid" meant n × n lattice points instead of squares?
Answer
Then there are n lines each way, so R = n2². It's the same idea with the label shifted by 1. Always check which convention a question uses!
How many boxes (cuboids) can you find in an n × n × n cube made of unit cubes? Try a 3 × 3 × 3 cube.
Answer
Now there are three independent choices of a pair of planes: n+12³. For a 3 × 3 × 3 cube: 6³ = 216.
In Step 4 the differences R(n) − R(n − 1) were perfect cubes. Can you prove they always are?
Answer
Write Tn = 1 + 2 + … + n. Using the difference of two squares:
Tn² − Tn−1² = (Tn − Tn−1)(Tn + Tn−1) = n · n² = n³
Adding these up gives a famous identity: 1³ + 2³ + … + n³ = (1 + 2 + … + n)². Rectangles prove it!
Now allow squares at any angle, as long as all four corners are lattice points. How many are there on a 3 × 3 grid?
Hint
Every tilted square fits snugly inside an upright k × k "bounding box". How many squares fit snugly inside one k × k box?
Answer
Each k × k box holds exactly k squares: the box itself plus k − 1 tilted ones. So the total is Σ k(n − k + 1)². For n = 3 that's 9 + 8 + 3 = 20. In general it's n(n+1)²(n+2)12.
- Translate the problem into a precise statement (a rectangle ↔ four numbers).
- Split it into groups that don't overlap (by shape).
- Simplify: solve an easier version first (squares).
- Experiment: try small cases, make a table, and test the pattern with differences and ratios.
- Look back: find the structure that explains the pattern (the double sum factorises into two independent choices).