# 100 combinatorics/grid.dissection.p

## Description

This article is from the Puzzles FAQ,
by Chris Cole chris@questrel.questrel.com and Matthew Daly
mwdaly@pobox.com with numerous contributions by others.

# 100 combinatorics/grid.dissection.p

How many (possibly overlapping) squares are in an mxn grid? Assume that all

the squares have their edges parallel to the edges of the grid.

combinatorics/grid.dissection.s

Given an n*m grid with n > m.

Orient the grid so n is its width. Divide the grid into two portions,

an m*m square on the left and an (n-m)*m rectangle on the right.

Count the squares that have their upper right-hand corners in the

m*m square. There are m^2 of size 1*1, (m-1)^2 of size 2*2, ...

up to 1^2 of size m*m. Now look at the n-m columns of lattice points

in the rectangle on the right, in which we find upper right-hand

corners of squares not yet counted. For each column we count m new

1*1 squares, m-1 new 2*2 squares, ... up to 1 new m*m square.

Combining all these counts in summations:

m m
total = sum i^2 + (n - m) sum i
i=1 i=1
(2m + 1)(m + 1)m (n - m)(m + 1)m
= ---------------- + ---------------
6 2
= (3n - m + 1)(m + 1)m/6

-- David Karr

Continue to: