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?
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
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 
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: 
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 
We need to figure out the coefficient for 
Claim: 
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 
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?
A rainbow of tolerance and acceptability!
Again, the coefficients of
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
Baking and Math 
Combinatorics!
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).