In How Many Ways can a Rectangle be Rectangled?

Abstract

There are $2^{n-1}$ ways to tile a $1\times n$ rectangle with rectangular tiles (of any length, of course they all must have width $1$), but in how many ways can you tile a $100\times 100$ checkerboard with such tiles? Neither humankind, nor computer-kind, will (most probably) ever know the exact number. But it is possible to compute these numbers for $m\times n$ rectangular grids, if $m$ is not too big, while $n$ can be as big as one wishes. This was initially done in 1988 by David Klarner and Spyros Magliveras, and beautifully extended, around 2006, by, at-the-time, first-year LSU undergraduate Joshua Smith, in collaboration with his faculty mentor, Helena Verrill. Here we extend this to weighted-counting, also keeping track of the number of tiles (that ranges from $1$ to $mn$), and the number of participating grid-edges (that range from $2m+2n$ to $2mn+m+n$). This quickly leads to statistical analyses (mean, variance, and higher moments) of these quantities. While we admire the clever approaches of Klarner-Magliveras and Smith-Verrill, we use two alternative approaches to the original problem, that are more amenable for deriving these generalizations. At the same time, we illustrate the power and beauty of experimental-yet-rigorous enumerative combinatorics.