{"id":399,"date":"2019-06-26T23:54:49","date_gmt":"2019-06-26T23:54:49","guid":{"rendered":"http:\/\/funfacts.104.42.120.246.xip.io\/?page_id=399"},"modified":"2019-11-18T23:53:31","modified_gmt":"2019-11-18T23:53:31","slug":"domino-and-square-tilings","status":"publish","type":"page","link":"https:\/\/math.hmc.edu\/funfacts\/domino-and-square-tilings\/","title":{"rendered":"Domino and Square Tilings"},"content":{"rendered":"\n
\"\"<\/figure><\/div>\n\n\n\n

How many ways can you tile a (1 x n) board with (1 x 1) squares and (1 x 2) dominoes?<\/p>\n\n\n\n

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…<\/p>\n\n\n\n

Hey, they are all Fibonacci numbers! These are numbers you get when you start a sequence 0 and 1 and generate the next sequence member by adding the previous two numbers: i.e., 0, 1, 1, 2, 3, 5, 8, …<\/p>\n\n\n\n

Presentation Suggestions:<\/strong>
Draw pictures, and have students count the number of tilings themselves.<\/p>\n\n\n\n

The Math Behind the Fact:<\/strong>
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.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

How to Cite this Page:<\/strong>\u00a0
Su, Francis E., et al. “Domino and Square Tilings.”\u00a0Math Fun Facts<\/em>. <http:\/\/www.math.hmc.edu\/funfacts>.<\/p>\n\n\n\n

References:<\/strong>
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<\/a><\/em>, Section 7.1. Benjamin and Quinn, Proofs that Really Count<\/em><\/a>.<\/p>\n\n\n\n

Fun Fact suggested by:<\/strong>
Arthur Benjamin<\/p>\n","protected":false},"excerpt":{"rendered":"

How many ways can you tile a (1 x n) board with (1 x 1) squares and (1 x 2)...<\/p>\n","protected":false},"author":7,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"tags":[92,9,76,4,93],"class_list":["post-399","page","type-page","status-publish","hentry","tag-combinatorial-proof","tag-combinatorics","tag-fibonacci","tag-medium","tag-tiling"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/399","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/comments?post=399"}],"version-history":[{"count":3,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/399\/revisions"}],"predecessor-version":[{"id":1408,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/399\/revisions\/1408"}],"wp:attachment":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/media?parent=399"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/tags?post=399"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}