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, q as a variable. In our polynomial, we’ll have the coefficients of representing the number of ways to tile using k tiles. So to represent the configurations in our picture above, we have .
We can ask ourselves, is there a pattern here? Let’s try a 1×2 floor.
Doing the same procedure as above, we get this polynomial: .
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 1xr floor gets a polynomial of .
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 q term in any polynomial, because there’s only one big fat tile that can do it. Similarly, there’s only every one term.
We need to figure out the coefficient for in the polynomial, and based on our 1×2 to 1×3 analysis, it should be related to the coefficient for in the polynomial. Let’s label these so we don’t have to keep writing it all out:
will be the coefficient for in the polynomial, and will be the same for the nth polynomial.
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.
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 . We can read off what the polynomials should be: for a 1×6 tiling, my polynomial will be .
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 are # of ways to tile with k 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