# Partitioning an $n \times n$ checkerboard into subsets

Let $S(m)$ be the number of partitions of an $n \times n$ checkerboard into $m$ subsets such that all the squares in each subset are connected contiguously. So for each $n,$ $m$ goes from $1$ to $n^2.$ For a $2 \times 2$ board, for example, $S(1) = 1,$ $S(2) = 6,$ $S(3) = 4$ and $S(4) = 1.$ The $3 \times 3$ case is proving to be quite an effort in brute force.

How do I approach this problem so that the cases for $n > 2$ are more tractable? Thank you in advance for any guidance you can provide.

By "contiguously" I mean that any pair of squares in a subset must be connected by a sequence of squares in which successive squares share an edge.

-
I think he means the number of different such partitions. – Yuval Filmus Jul 25 '12 at 6:12
There's still a problem: by the current definition, $S(2) = 2$ and $S(3) = S(4) = 0$ for $n=2$. The way the subsets are described forces them to have at least 2 squares each. I suspect you just meant to say they're connected. – Erick Wong Jul 25 '12 at 7:16
@Brian: Please clarify the question itself; people shouldn't have to delve into the comments to understand it. As Erick pointed out, in its current form the question unambiguously requires each square to share an edge with another square in the subset; I don't see any room for interpretation that would allow for a one-square subset. You could express what you meant by requiring any pair of squares in a subset to be connected by a sequence of squares in which successive squares share an edge. – joriki Jul 25 '12 at 7:55
The current form not only excludes one-square subsets, it also allows arbitrary disconnected subsets as long as each connected component has at least two squares. This is also apparently not what you had in mind. – joriki Jul 25 '12 at 7:56
@Brian: I'm confused. Now you've edited the question, but apart from the fact that this formulation unnecessarily treats the single-square case separately, more importantly it still allows for disconnected subsets as long as all connected components contain at least two squares. Is that really what you want? – joriki Jul 25 '12 at 8:05

I think it is hard to do by hand, but it should yield to computer solution. As you are counting rotations and reflections separately, there is almost an easy answer. Start with $S(n^2)=1$ as you need each square to be separate. There are $2n(n-1)$ internal edges, so $S(n^2-1)=2n(n-1)$ because you just pick one edge to glue together. Similarly, $S(n^2-2)= {2n(n-1) \choose 2}=n(n-1)(2n^2-2n+1)$ because you just pick two edges to glue. The problem comes when you can form a square as there are four ways to glue three edges to get the same square and gluing all four edges doesn't decrease the piece count by one. Maybe that will prompt some thought.
For the program, I would again start with all the squares separate. Then glue all possible pairs to make the $n^2-1$ piece dissections. Then glue pairs of those to make the $n^2-2$ piece dissections, but the challenge is finding and eliminating the duplicates. I would encode a board with $n^2$ numbers, the piece number of each square, starting from the upper left. If you have glued each of the top row of a $3 \times 3$ to the square below and glued the right two dominoes, it would look like $122122345$