2
$\begingroup$

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.

  • 0
    @Brian: What's wrong with the formulation I suggested? "Connected" raises the question whether diagonal connection counts as a connection.2012-07-25

1 Answers 1

1

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$

  • 0
    Thank you. That gives me a fresh way of looking at the problem.2012-08-31