# Open problem in combinatorics: tiling a floor (no background

25 Apr

As I mentioned a few weeks ago, I recently went to the second annual Midwest Women in Mathematics Symposium (yay!  My baby conference is now a toddler!)  The organizers added a problem session to the program, which ended up being super cool- each presenter had five minutes or so to present an open question that needed answering.  The idea was to search for nearby collaborators, which is such a cool way of doing it!  I loved a bunch of them, so thought I’d write up one.

This presentation was by Pamela Harris, an assistant professor at West Point.  We also need NO BACKGROUND for it, which is awesome!  All of these notes are derived from her 5 minute presentation + wikipedia searches.

Let’s say for example that we have a rectangular floor, say one foot by three feet.  We have a bunch of tiles of size 1×1, 1×2, 1×3.  The question is, how many different ways do we have to tile the floor?  A second question might be, how many different ways are there using 2 tiles?

This question is pretty straightforward with a 1×3 floor: I drew all the possibilities below.

Notice that in answer to our second question, there’s one way to use 3 tiles, two ways to use 2 tiles, and one way to use 1 tile.  We can encode this information in a polynomial using, say, as a variable.  In our polynomial, we’ll have the coefficients of $q^k$ representing the number of ways to tile using tiles.  So to represent the configurations in our picture above, we have $1q + 2q^2 + 1q^3 = q(1+2q+q^2) = q(1+q)^2$.

We can ask ourselves, is there a pattern here?  Let’s try a 1×2 floor. CHANGING THE PARADIGM- blue is happy! Green is still envious of that happiness though

Doing the same procedure as above, we get this polynomial: $1q + 1q^2 = q(1+q)$.

You can work out for yourself what happens with a 1×4 floor.  If you use some combinatorial thought (I’ll give an example below), you end up with any 1xfloor gets a polynomial of $q(1+q)^{r-1}$.

I haven’t thought about this problem before starting to type this, so you can have some insight into my mind right now!  Let’s try to figure out what happens when we go from a 1×2 tiling to a 1×3 tiling.  We still have the same tiles as in 1×2, but adding a red single square to them (this gives the first two configurations in our red-orange-yellow picture).  We can also add a red single square to the left side of the green picture, giving the third configuration.  Finally, we have the big 1×3 tile, which didn’t exist in the 1×2 world.

In fact, when we go from 1xn land to 1x(n+1) land, the only tiling that uses a tile not seen in 1xn is the last one, which consists of one big 1x(n+1) tile.  This adds a single q term to our polynomial (because we only used one tile).  In fact, there’s only ever one term in any polynomial, because there’s only one big fat tile that can do it.  Similarly, there’s only every one $q^{n+1}$ term.

We need to figure out the coefficient for $q^k$ in the $(n+1)^{th}$ polynomial, and based on our 1×2 to 1×3 analysis, it should be related to the coefficient for $q^k$ in the $n^{th}$ polynomial.  Let’s label these so we don’t have to keep writing it all out: $G(n+1,k)$ will be the coefficient for $q^k$ in the $(n+1)^{th}$ polynomial, and $G(n,k)$ will be the same for the nth polynomial.

Claim: $G(n+1,k) = G(n,k) + G(n,k-1)$.

Proof: Up to you!  All the thoughts from above should help out.  This is apparently a common exercise in combinatorics classes.  If I get requests I’ll put up a proof at a later post.

This recursive formula tells us exactly what the explicit formula should be, because it’s the formula for Pascal’s triangle. From wikipedia- Pascal’s triangle

Each entry in the triangle is formed by adding the two entries above it.  If you number the entries by (row, place in line), you’ll get our exact formula $G(n+1,k) = G(n,k) + G(n,k-1)$.  We can read off what the polynomials should be: for a 1×6 tiling, my polynomial will be $q+5q^2+10q^3+10q^4+5q^5+q^6 = q(1+1)^5$.

Good warm up!  So here’s the open problem: if you have the floor in the picture (so a 2xn rectangle, with a 1×1 bite taken out of the bottom left corner), and the only allowable tiles are the ones in the picture, what polynomials do you get?

Again, the coefficients of $q^k$ are # of ways to tile with tiles.

I googled “tilings with rectangles” and there were a TON of papers written on this topic.  So here are some Further reading suggestions (from least mathematical-intimidation seeming to most)

This one has the word “simple” in it and lots of pictures: http://www.inference.phy.cam.ac.uk/mackay/rectangles/

This one uses those little rods we had in middle school math: http://users.humboldt.edu/phyllis/papers/c-rodpaper2.html

This has lots of pictures and numbers (numbers are good/concrete): http://www.math.ucsd.edu/~ronspubs/82_04_tiling.pdf

This is 14 different proofs of the same theorem, using integrals, graph theory, induction, polynomials… you’ll probably like at least one of them! http://www.maa.org/sites/default/files/images/upload_library/22/Ford/Wagon601-617.pdf

This one is recent research- it was published in 2012.  It has Hausdorff spaces, discrete Morse theory, and homotopy equivalence on the first page.  I might read it for funsies.  http://arxiv.org/pdf/1204.5734v2.pdf

### 5 Responses to “Open problem in combinatorics: tiling a floor (no background”

1. EfficientAsianMan April 25, 2014 at 12:59 pm #

Combinatorics!

2. j2kun April 25, 2014 at 1:55 pm #

This reminds me of a tiling problem I saw while I was in Budapest. The theorem is that the number of ways to tile a 2xn rectangle with 2×1 dominoes is the n-th fibonacci number. It’s a neat little proof by induction.

On a different note, I thought that the algorithmic problem of counting tilings was #P-hard, but it appears not to be the case for dimension 2 (while it is #P-hard for higher dimensions).