Mudd Math Fun Facts!
hosted by the Harvey Mudd College Math Department created, authored and ©1999-2007 by Francis Su
You can now subscribe to our RSS feed to get the latest Fun Facts!
Get a random Fun Fact!
No subject limitations
Search only in selected subjects
    Algebra
    Calculus or Analysis
    Combinatorics
    Geometry
    Number Theory
    Probability
    Topology
    Other subjects
  Select Difficulty  
Enter keywords 

  List All : List Recent : List Popular
  About Math Fun Facts / How to Use
  Contributors / Fun Facts Home
© 1999-2007 by Francis Edward Su
All rights reserved.

From the Fun Fact files, here is a Fun Fact at the Easy level:

Domino and Square Tilings

Figure 1
Figure 1

How many ways can you tile a (1 x n) board with (1 x 1) squares and (1 x 2) dominoes?

Let's see...
A (1 x 1) board can only be tiled 1 way.
A (1 x 2) board can be tiled 2 ways: either two squares or one domino.
A (1 x 3) board can be tiled 3 ways: three squares, or a domino-square, or a square-domino.
A (1 x 4) board can be tiled 5 ways...

Hey, they are all Fibonacci numbers!

Presentation Suggestions:
Draw pictures, and have students count the number of tilings themselves.

The Math Behind the Fact:
The Fibonacci property can be seen by conditioning on whether the first tile is a square or domino: the number of tilings where the first tile is a square is the number of ways to tile the remaining (n-1)-length board, and the number of tilings where the first tile is a domino is the number of ways to tile the remaining (n-2)-length board. A generalization of this idea can be used to develop combinatorial interpretations for many "Gibonacci" identities (recurrences in which the first terms are not necessarily 1 and 1); see the Benjamin-Quinn-Su reference for more on this.

An alternate generalization asks how many ways to tile an (m x n) board with dominoes; note that the (2 x n) case is equivalent to tiling a (1 x n) board with squares and dominoes. See the Graham-Knuth-Patashnik reference.

Other generalizations can be found in the Brigham-Caron-Chinn-Grimaldi reference. If you like this Fun Fact, you'll like all the stuff that is in the Benjamin-Quinn book in the references.

How to Cite this Page:
Su, Francis E., et al. "Domino and Square Tilings." Mudd Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

Bookmark this page on: | Digg this! | Del.icio.us | Technorati | Reddit | Fark | Squidoo | Furl | Blinklist | Yahoo MyWeb | Google | Stumbleupon |

References:
    A. Benjamin, J. Quinn, and F. Su, "Phased Tilings and Generalized Fibonacci Identities", Fibonacci Quarterly, 2000.
    Brigham, Caron, Chinn and Grimaldi, "A Tiling Scheme for the Fibonacci Numbers", J. Recreational Math, 28(1), 1996-7, pp. 10-17.
    Graham, Knuth, Patashnik, Concrete Mathematics, Section 7.1. Benjamin and Quinn, Proofs that Really Count.

Keywords:    combinatorial proof, combinatorics
Subjects:    combinatorics
Level:    Easy
Fun Fact suggested by:   Arthur Benjamin
Suggestions? Use this form.
4.15
 
current
rating 		Click to rate this Fun Fact...
    *   Awesome! I totally dig it!
    *   Fun enough to tell a friend!
    *   Mildly interesting
    *   Not really noteworthy
and see the most popular Facts!

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!