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?

How many ways to tile this floor using these colored tiles?

How many ways to tile this floor using these colored tiles?

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

I don't know why the red tiles are so unhappy

I don’t know why the red tiles are so unhappy

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

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?

How do you fill me?

How do you fill me?

A rainbow of tolerance and acceptability!

A rainbow of tolerance and acceptability!

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

About these ads

2 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).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 258 other followers

%d bloggers like this: