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.

  • 1
    You define $S(m)$ to be a partition, then you write $S(2)=6$. 6 is not a partition. Please think through your question and rewrite it so it says what you really want to say.2012-07-25
  • 3
    I think he means the number of different such partitions.2012-07-25
  • 0
    Sorry. I think I have it in proper form now.2012-07-25
  • 2
    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.2012-07-25
  • 0
    @ErickWong. Yes, that was what I meant. For subsets of size 1 there is no other square to share an edge with, so I thought I left open the possibility of subsets of size 1 with my definition. In any event, size 1 subsets are allowed.2012-07-25
  • 2
    @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.2012-07-25
  • 2
    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.2012-07-25
  • 2
    @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?2012-07-25
  • 0
    @joriki. I'm sorry I've made such a hash of my question. I was worried that just saying 'connected' would be too vague, but perhaps that would have been the better way to go. I have tried one more edit to try and clarify my intent.2012-07-25
  • 0
    @joriki. I see what you mean now. I will just use the word 'connected' in my next edit.2012-07-25
  • 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