Overview
In my previous two blog posts, I showed that the number of squares of various sizes in an nxn grid is $\sum_{{i}={1}}^{n}i^2 = \frac{n(n + 1)(2n + 1)}{6}$. In this post I'm going to use combinatorial Mathematics to derive a different closed form solution.
All posts in this series
- Counting squares in a grid
- Guessing a closed form solution for the sum of squares
- A combinatorial solution for counting squares in a grid
A quick review of combinations
In combinatorics, the combination function $\binom{n}{k}$ is used to counts the number of different ways that k items can be chosen from a set of n unique items, with the order of the k items being irrelevant. $\binom{n}{k}$ is usually read as "n combination k" or "n choose k". It is also known as the binomial coefficient. You can read more about combinations on Wikipedia.
You also need to know that: $$ \begin{align*} n! &= 1 . 2 . 3 ... n & \text{n! is the product of the first n natural numbers} \\ \binom{n}{k} &= \frac{n!}{(n-k)! k!} \\ &= \frac{n (n - 1) ... (n - k + 1)}{1 . 2 . 3 ... k} \end{align*} $$
The approach
We are going to use combinatorial Mathematics to count the number of possible squares in the grid. To do this we will need to define a coordinate system for the grid and a convenient data representation for a valid square in that grid. By a data representation, I mean a set of numeric values that can uniquely identify a particular square in the grid.
We will then use combinations to count all possible ways of generating valid data representations. But we will need to take into account that combinations generate unique numbers. That will require us to consider separate cases based on the number of identical variables in our representation.
A useful data representation
A recap of the problem
The problem is to count the total number of squares of any size in a grid. So if you think of a Chessboard, how many 1x1, 2x2, ..., 8x8 squares are there?
Let's consider whether there is a useful notation for describing any valid square in the grid.
Defining a coordinate system
First let's define a coordinate system for the grid.
We'll say that (x, y) is the coordinate of a space on the checkerboard in column x and row y. And we'll choose (1,1) to be the coordinate of the top-left corner. That way columns go from left to right and rows go from top to bottom - the same direction as reading pages in a book (for most cultures).
[This is just one possible convention... I could have started at the bottom left instead, like a chart, or made the corner square (0, 0) instead of (1,1).]
Comparing different representations for valid squares in the grid
We could use the co-ordinates $(x_1, y_1)$ and $(x_2, y_2)$ of two opposite corners of a square block. But that representation encodes any rectangle in the grid, not just the squares. We'd prefer to choose a data representation which enforces constraints naturally.
So what if we used $(x_1, y_1, s)$ as our data representation, where $(x_1, y_1)$ is the top left corner of the square and $s$ is the size of the sides of the square? This is better, because we have 3 variables representing a valid square instead of 4, and we have expressed the constraint that a square's sides have the same size.
However this representation is still a little cumbersome. To express the constraint that the square fits within the grid, we need to ensure that the bottom right corner is somewhere inside the grid. That requires calculating the x and y coordinates of the bottom-right corner. Our data representation would be more convenient if we could avoid all unnecessary calculations.
So let's encode the bottom-right corner into the data representation instead. This will give us our desired data representation...
The chosen data representation
We will represent a square in the grid by the triple $(x, y, s)$ where (x, y) is the bottom-right corner of the square and s is the size.
Our data representation (x, y, s) is summarized in the following diagram:
With this data representation, our constraints on a valid square are: $$ \begin{align*} 1 \leq x \leq n & \tag{1} \\ 1 \leq y \leq n & \tag{2} \\ 1 \leq s \leq n & \tag{3} \\ s \leq x & \tag{4} \\ s \leq y & \tag{5} \\ \end{align*} $$
There is some redundancy in constraint 3, since the other 4 constraints ensure that $s \leq n$. I've chosen to do it this way so that constraints 1, 2 and 3 all have the same form. They will be satisfied naturally when we use the combination function. Only constraints 4 and 5 will need to be considered explicitly.
Generating all possible data representations
Choosing values of x, y and s from the set {1, 2, ... n}
We can address constraints 1, 2 and 3 by choosing our variables x, y and s from the set {1, 2, 3, ..., n}. That allows us to use the combination function.
Unfortunately there's a catch! Combinations count unique numbers, and some of the variables x, y and s could be the same. So we'll need to consider separate cases depending on how many of the variables have unique values.
Let's start by defining variables for each case. Let $c_i$ be the number of ways of generating representations $(x, y, s)$ when $i$ unique numbers are taken from the set {1, 2, 3, ..., n}. The total number of squares is then $c_1 + c_2 + c_3$.
Counting $c_3$: the number of squares when x, y and s are all different
There are $\binom{n}{3}$ ways of choosing three unique numbers from the set {1, 2, ..., n}. Of these, the smallest must always be assigned to $s$ so that constraints 4 and 5 are addressed. However the largest could be assigned to x or y. This leads to two sub-cases: $$ \begin{align*} \text{ i) } & s < x < y \\ \text{ii) } & s < y < x \end{align*} $$
So we have two different representations generated from each set of three distinct numbers. Thus: $$ c_3 = 2 \binom{n}{3} $$
Counting $c_2$: the number of squares when only two of x, y and s are different
There are $\binom{n}{2}$ ways of choosing two unique numbers from the set {1, 2, ..., n}. But there are three different ways that these two numbers can be assigned to the values (x, y, s): $$ \begin{align*} \text{ i) } & s < x = y \\ \text{ ii) } & s = x < y \\ \text{ iii) } & s = y < x \\ \end{align*} $$
Thus: $$ c_2 = 3 \binom{n}{2} $$
Counting $c_1$: the number of squares when x, y and s are all the same
There are $\binom{n}{1} = n$ ways of choosing a single number from the set {1, 2, ..., n}.
Each such number will define a single solution with: $$ \begin{align*} s = x = y \\ \end{align*} $$ Clearly all the constraints will be satisfied. Thus: $$ c_1 = n $$
Putting it all together
So the total number of squares of various sizes in an n x n grid is: $$ c_1 + c_2 + c_3 = n + 3 \binom{n}{2} + 2 \binom{n}{3} $$
Checking the answer
In the second post of the series we showed that the number of squares is $ \frac{n(n + 1)(2n + 1)}{6} $. Let's check our answer by seeing if the two formulas are equivalent.
$$ \begin{align*} n + 3 \binom{n}{2} + 2 \binom{n}{3} &= n + 3 \frac{n (n - 1)}{2} + 2 \frac{ n(n - 1)(n - 2)}{6} \\ &= \frac{n}{6} [ 6 + 9 (n - 1) + 2(n - 1)(n - 2) ] & \text{ Extract } \frac{n}{6} \text { from all terms } \\ &= \frac{n}{6} [ 6 + 9n - 9 + 2n^2 - 6n + 4 ] \\ &= \frac{n}{6} [ 2n^2 + 3n + 1 ] \\ &= \frac{n}{6} [ (n + 1)(2n + 1) ] \\ &= \frac{n(n + 1)(2n + 1)}{6} \\ \end{align*} $$ So our calculations seem correct, since this is the formula we generated in the previous blog post.
The value of a good data representation
Rob Pike's 5th rule of programming supposedly states that:
Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.
This echoes Fred Brooks' statement in "The Mythical Man-Month" that: "Representation is the essence of programming".
This blog post is about Mathematics, not programming. But I'd argue that the elegance of this solution also comes from choosing the right data representation.
Conclusion
This is the third post in the series. The first three posts have shown that the number of squares in an nxn grid is: $$ \begin{align*} & \sum_{{i}={1}}^{n}i^2 & & \text{ from blog post 1} \\ = & \frac{n(n + 1)(2n + 1)}{6} & & \text{ from blog post 2} \\ = & n + 3 \binom{n}{2} + 2 \binom{n}{3} & & \text{ from blog post 3} \\ \end{align*} $$
Next time
This post had far less algebra than the previous blog post. But there was still some algebraic manipulation required to arrive at the formula $\frac{n(n + 1)(2n + 1)}{6}$. It's certainly not obvious why the formula has that specific form. My aim in the next two blog posts will be to address this. I want to arrive at that formula via a much more direct route.
No comments:
Post a Comment