The other day I was thinking about putting dominoes onto a 4-by-4 grid without any of the dominoes contacting each others’ sides. I wanted to know how many dominoes you could fit onto the 4-by-4 grid in this way, and what the different configurations looked like. I was pretty sure that the answer to the first question was that four dominoes could be fit onto the grid. I was less sure that I had found all of the configurations allowed. (I had three configurations.)
So, I started from square one: I found all of the ways (up to symmetry) of putting one domino on the grid (there are four). Then combining those I found all of the ways of putting two dominoes on (there are 20). Then by taking all of my configurations of two dominoes and adding one I found all of the ways of putting three dominoes on (there are 20). Finally I used my 3-domino configurations and found all of the 4-domino configurations by adding one to the ones that allowed it. I discovered that I had missed a 4-domino configuration! So there are four 4-domino configurations. And since I couldn’t legally add a domino to any of those, I knew there were no 5-domino configurations. Cool.
But wait…4, 20, 20, 4. There’s symmetry there! Could it be that this is a general thing? Is there a way to transform the four 1-domino configurations into the four 4-domino configurations? Likewise, did the same (or a similar) transformation change the 20 2-domino configurations into the 20 3-domino configurations? It might be something like the binomial coefficients: the number of ways to choose two people out of a group of five is the same as the number of ways to choose three people out of a group of five.
Then, my heart sank…I thought of this fact: there is exactly one configuration with no dominoes (just an empty grid), but there are zero 5-domino configurations. The symmetry is broken. There apparently is no such transformation.
Still, the 4, 20, 20, 4 pattern is fascinating (even if the pattern is really 1, 4, 20, 20, 4). I shared this with Jason Lee, a mathematical friend. Jason thought (as I had originally) that there was some transformation that we were missing. He suggested we look at larger grids to see if we see similar patterns. I bet him a bottle of rootbeer that we wouldn’t. He accepted the bet, and proceeded to code up an algorithm for enumerating domino configurations with grid-size as a parameter. The algorithm didn’t find any such nice symmetries for larger grids. I wish I could be more specific about the details, but I don’t have them in front of me right now. In the next couple of days I’ll talk to Jason about sharing his Python code here on my blog, along with specifics of numbers of configurations for larger grids. In any case, I got my rootbeer!
Above I’ve posted a drawing of the 4, 20, 20, 4 configurations mentioned (click on it to see it enlarged). Do you see a reason for the symmetry? Is there some transformation we’re missing? In any case, I think it makes for a nice picture.
By the way, the original impetus for thinking about this was the December 2012 IBM Ponder This puzzle. There we are asked to place numbers in a 6-by-6 grid. The highest numbers that we can place are fives, and the rules given there imply that any fives come as dominoes of four-five pairs lying in the central 4-by-4 grid with our no-contact constraint.