EDITORIAL POLICY Mathematics Magazine aims to provide lively .mel appealing mathematical exposition. The Magazine is not a research journal, so the terse style appropriate for such a journal (lemma-theorem-proof-corollary) is not appropriate for the Magazine. Articles should include examples, applications, historical background, and illustrations, where appropriate. They should be attractive and accessible to undergraduates and would, ideally, be helpful in supplementing undergraduate courses or in stimulating student investigations. Manuscripts on history are especially welcome, as are those sbow­ ing rel.1tionships among various branches of mathematics and between mathematics and other disciplines. A more detailed statement of author guidelines appears in this Magazine, Vol. 74, pp. 75-76, and is available from the Editor or at www.maa.org/pubs/mathmag.html. Manuscripts to be submitted should not be concurrently submitted to, accepted for publication by, or published by another journal or pub! isher. Submit new manuscripts to Frank Farris, Editor, Mathematics Magazine, Department of Mathematics, Santa Clara University, Santa Clara, CA 95053-0373. Manuscripts should be laser printed, with wide line spacing, and prepared in a style consistent with thP format of Mathematics Magazine. Authors should mail three copies and keep one copy. In addition, authors should supply the full five-symbol 2000 Mathematics Subject Classification number, as described in Mathematical Reviews. The cover image displays my license plate as I figuratively drive off into the sunset. Thanks to Don Deland for suggesting the apt caption. This represents my farewell as editor of the MAGAZINE. The experience has been exciting, exhilarating, and exhausting. I have found myself overjoyed and overwhelmed. I am happy that I chose to take on this task, and I am happy that my term is coming to a close. A special note of appreciation goes to Frank Farris as he returns to the editorial office for Volume 82 beginning with the February 2009 issue. AUTHORS Carlos Ueno received his BS from the Universi­ dad Complutense de Madrid and his MS from thl' University of Toronto. He is currently a te,lchl'r of Mathematics at IES jandfil (Fuerteventura, Ca­ nary Islands, Spain), where he tries to tran'>mit th<• beauty of math to his teenage students. He i; .llso planning to complete a PhD program in mathemat­ ics, working on problems related to the ;tudy oi im­ ages of real polynomial maps in Euclidean spaces. In his spare time Carlos enjoys the good company of his school colleagues , the wonderful beachl's of Fuerteventura, and the exploration of virtual worlds through the Internet. Frank Swetz is Professor Emeritus of Mathematics and Education at the Pennsylvania State Univer­ sity. At present, he is co-editor, with Victor Katz, of the MAA e-journal ConvergPnce. His com erns with humanistic mathematics tl'aching haw led him into studies about the history of mathemat­ ics and ethnomathematics. His most recent book is The Legacy the Meaning A. K. Peters of the Luoshu: a 4000 Year Search ti1r of the Magic Square of Order Three, (2008). In his spare time he grows veg­ etables and trains Mongolian fighting crickets. Vesna Stojanoska is a graduate student at North­ western University, studying algebraic topology; more precisely, she is trying to understand aspects of stable homotopy theory. She began untangling braids and otherwise working on this article while she was an undergraduate at the American Univer­ sity in Bulgaria. Orlin Stoytchev is a professor at the American Uni­ versity in Bulgaria. He received his PhD from the Mathematics Department of Virginia Tech. His in­ terests can be summarized as "the different aspects of symmetries in mathematics and physics." He has published works on Von Neumann algebras and on representations of finite- and infinite-dimensional Lie groups and their algebras. The idea for the present article came from an attempt to find an accessible way to demonstrate a rather nontrivial topological fact to his students. MATHEMATICS MAGAZINE E D ITOR A l l e n J. Schwenk Western Michigan University ASSOC I AT E E D I TORS Pau l J. Cam pbel l Beloit College A n n a l isa Cra n n e l l Franklin & Marshall College Dea n n a B. H a u n sperger Carleton College Warren P. Joh nson Connecticut College E l g i n H . Jo h n ston Iowa State University Vi ctor J. Katz University of District of Columbia Ke ith M. Ken d i g Cleveland State University Ro g er B. N e l sen Lewis & Clark College Ken n eth A. Ross University of Oregon, retired Dav i d R. Scott University of Puget Sound Pau I K. Stockmeyer College of William & Mary, retired H a rry Wa l d m a n MAA, Washington, DC E D I TO R I A L ASS I STA N T Margo Chapman MATHEMATICS MAGAZINE (ISSN 0025-570X) is published by the Mathematical Association of America at 1529 Eighteenth Street, N.W., Washington, D.C. 20036 and Montpelier, VT, bimonthly except july/August. The annual subscription price for MATHEMATICS MAGAZINE to an individual member of the Association is $131. Student and unemployed members receive a 66% dues discount; emeritus members receive a 50% discount; and new members receive a 20% dues discount for the first two years of membership.) Subscription correspondence and notice of change of address should be sent to the Membership/ Subscriptions Department, Mathematical Association of America, 1529 Eighteenth Street, N.W., Washington, D.C. 20036. Microfilmed issues may be obtained from University Microfilms International, Serials Bid Coordinator, 300 North Zeeb Road, Ann Arbor, Ml48106. Advertising correspondence should be addressed to MAA Advertising 1529 Eighteenth St. NW Washington DC 20036 Phone: (866) 821-1221 Fax: (202) 387-1208 E-mail: advertising®maa.org Further advertising information can be found online at www.maa.org Change of address, missing issue inquiries, and other subscription correspondence: MAA Service Center, maahq®maa.org All at the address: The Mathematical Association of America 1529 Eighteenth Street, N.W. Washington, DC 20036 Copyright © by the Mathematical Association of America (Incorporated), 2008, including rights to this journal issue as a whole and, except where otherwise noted, rights to each individual contribution. Permission to make copies of individual articles, in paper or electronic form, including posting on personal and class web pages, for educational and scientific use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear the following copyright notice: Copyright the Mathematical Association of America 2008. All rights reserved. Abstracting with credit is permitted. To copy otherwise, or to republish, requires specific permission of the MAA's Director of Publication and possibly a fee. Periodicals postage paid at Washington, D.C. and additional mailing offices. Postmaster: Send address changes to Membership/ Subscriptions Department, Mathematical Association of America, 1529 Eighteenth Street, N.W., Washington, D.C. 20036-1385. Printed in the United States of America ARTICLES Matrices a n d Til ings with Right Tro min oes C A R L O S U E N O I E S Cruz de Piedra 3 5 0 1 4 Las Pal mas de Gran Canaria, SPA I N 320 MATHEMATICS MAGAZIN E Let us start by defining an m-binary path as a descending path from a top corner to a bottom corner of an m x 1 rectangle, in such a way that it goes along the sides of the unit squares forming such a rectangle. We always assume that the first and last segments are vertical (see FIGURE 1c). We can see that the vertical edges of these paths can be on the left side or the right side of the hosting rectangle. If we assign the value 0 to its left side and the value 1 to its right side, each m-binary path can be associated to an m-bit string, as shown in FIGURE 2. 0 1 0 1 = 5 �paths intom-bit10001strings.= 17 �Figure 2 Turning00101m-binary Conversely, each m-bit string corresponds to a unique m-binary path. Therefore, there are 2m different m-binary paths, and each one can be identified with a number between 0 and 2m- 1, written in its binary form. In the rest of this article, we identify an m-binary path and its associated m-bit string with the symbol j, 0 ::;: j ::;: 2m- 1, where the binary representation of j gives the corresponding path-whenever we drop the bar in j we will be referring to the number instead of the path it represents. Now, let us consider two consecutive m-binary paths "i and j in an m x 2 rectangle, which can be considered as formed by two m x 1 consecutive rectangles (see FIGURE 3). Figure 3 Two consecutive 5 -binary paths. These paths bound a region inside the rectangle, which can be covered or not with right trominoes. We write ("i, J)m to denote the number of different tilings by right trominoes of the region bounded by "i and j. As an example, FIGURE 3 illustrates the fact that (5, 19)5 6 grey cells. = 1, since there is exactly one way to tile the region consisting of the Given a nonnegative integer m, we define the transfer matrix Gm as the matrix whose coefficients are Gm [i, j] = ("i, J)m-we refer to the coefficient at position [i, D of any matrix A as A[i, j]. A special case arises whenever "i =2m- 1 and j =0, because these consecutive m-binary paths do coincide, and the region bounded by them does not contain any cell. In this situation we set (2m- 1, O)m = 1, meaning by this that there is just one way to tile this null-area region, which consists in not placing any right tromino on it. Also, for the degenerate case m = 0 a similar argument leads us to set Go = [1] as most convenient. The three next matrices in this sequence are VO L . 8 1 , N O . 5 , D EC EM B E R 2 008 [� �l 3 21 0 0 0 0 0 0 0 2 0 0 I 0 I 0 0 0 I 0 0 0 0 0 0 0 0 0 0 0 0 I 0 0 0 0 0 Gz = G 1 = [l 00 00 Il G3 = 000 00I 00I 0 000 000 00 000 0 0 0 0 0 0 0 We invite the reader to check the validity of some coefficients in these matrices, in order to get more familiar with their meaning. The matrices { G m} are our object of study in the next section, for they constitute our main tool to compute the number of different tilings for rectangles and other related regions. Transfer matrices We now consider m-binary paths in an m x n rectangle R. If we consider such a rectangle as the union of n consecutive m x 1 rectangles (see FIGURE 4), then wk repre­ sents an m-binary path in the kth unit-width rectangle. Figure 4 m x 1 rectan g l es form i n g an m x n rectan g l e. Given an m-binary path wk and a tiling T in R, we say that wk and T are compatible if the path goes along the edges of the trominoes forming the tiling T. For example, the tiling shown in FIGURE 1b is compatible with the path 0 in the first column, with and with the the path 37 in the second column, with the path 22 in the third column path 63 in the fourth column. It is not hard to observe the following fact. LEMMA 1 . Let R be an m x n rectangle. Then, each tiling with right trominoes determines a unique set of n consecutive m-binary paths w1, • • • , Wn, all of them compatible with the tiling. Proof. Let us consider the vertical sides 10 , 11, • • • , ln of the n consecutive m x 1 rectangles that R has. We can partition this rectangle in regions Rb 1 ::::; k ::::; n - 1 , each one formed by the union of the trominoes with interiors intersecting h (see FIGURE 5). The interior of Rk coincides with the interior of the region bounded by two compatible and consecutive m-binary paths wk and wk +i· Moreover, when considering the next region Rk +l and its bounding paths w�+i and w�+Z we must have wk +1 = w�+i, for obvious reasons. Therefore, we can associate to the tiling T an ordered set of compatible and consecutive m-binary paths {w1, w2, • • • , wn}, where we have w1 = 0, Wn = 2 m - 1 . To see uniqueness, let us suppose there are different sets { w1, w2, • • • , Wn} and { w;, w;, . . . , w�} of consecutive m-binary paths for the same tiling T. Then we would have for some k that wk =/= w�, but this is impossible for that would imply that there is at least one complete tromino in the region bounded by these different paths, both included in the same m x 1 rectangle, and this cannot happen. • 322 MATHEMATICS MAGAZIN E 1----l-····""""11---1·-----·· -............. . i Figure 5 The region R3 is bounded by twom-binary paths compatible with the tiling. In order to take full advantage of the sequence of matrices { G m}, we need now to generalize our study to a wider family of regions, which include rectangles as a special case. DEFINITION 1. An m-strip of order n 2: 2 bounded by m-binary paths w1 and Wn is the region in an m x n rectangle bounded on the left by w1 and on the right by Wn· We refer to it as Sm(WJ, Wn, n), and we write N(Sm(w1, Wn, n)) to denote its number of different tilings. Figure 6 The strip Ss(26, 3, 9). I!! particular, an m x n rectan_gl� can Sm(O, 2m- 1, n), or as the strip Sm(O, 0, n + ized to tilings of m-strips. be considered either as the strip 1). Clearly Lemma 1 can be general­ The next result is straightforward. LEMMA 2. Given any m-binary path Wn -l in the ( n - l)th column of an m x n rectangle R, with n 2: 3, the number of tilings of the strip Sm(W�o Wn, n) that are compatible with Wn-l is given by the product N(Sm(WJ, Wn-l• n- 1)) . (Wn-h Wn)m. Notice that when Wn-l runs through all the possible m-binary paths, the sum of these products is precisely N(Sm(w1, Wn, n)). Now we are ready to give a full meaning to our family { Gm} of transfer matrices. PROPOSITION 1. The number of different tilings of the strip Sm(w1, Wn, n), n 2: 2, is given by the coefficient G;:,-I[WJ, Wn]. Proof We use induction on the order n of the strip. For n = 2, let us consider two consecutive m-binary paths w1 and w2 in am x 2 rectangle. Then, from the definition of the matrix G m we have VOL. 81 I N O. 5, DECEM B E R 2 008 323 Now let us assume that the result is valid for a natural number n - 2 ::: 2. Then and therefore the statement is also true for n. • With respect to rectangles, the number of different tilings in an m x n rectangle can m be expressed either as G::,-1[0, 2 - 1 ] or as G::,[O, 0]. We will use both possibilities indiscriminately. Main result In this section our goal is to give an explicit expression for the sequence of matrices {Gm}. In order to achieve this, we need some auxiliary matrices. We define GLm as the matrix with GLm[i, j] = (i', j){;,, where (i', ]} {;, = (Oi', Oj} can be viewed as the number of tilings of the region bounded by consecutive paths i' and j, which has been modified by adding an extra unit square on the upper left corner of the m x 2 rectangle. Similarly, let GRm be the matrix with GRm[i, j] = (i', ]} �.where (i', j} � = (li', 1]} represents the number of possible tilings of the region bounded by i' and j, which has been modified by adding an extra unit square on the upper right corner. Finally, let GTm be the matrix with coefficients GTm[i, j] = (i', ]} � .where (i', j} � = (Oi', 1]} is the number of possible tilings of the region bounded by paths i' and j, which includes two extra unit squares on the top of the rectangle. To understand better the meaning of these new matrices, the reader can observe FIGURE 7 and realize that (5, 31}; --R - - (5, 3 1 }5 = 1 and (5, 3 1 }5 T = 0. Figure 7 = 1 , One extra unit square on the left, on the right, and two extra unit squares on the top. It is not a hard task to verify that the relations listed in TABLE 1 hold; most of them are trivial. As an example, in FIGURE 8 we have i' = 1 6, j = 63, and the relation T - -}R - -L (0-l, 1 - 1 } m+l = ( l, 1 } m + ( l, 1 m reduces to the equality 4 = 2 + 2. From these relations we get the following result. THEOREM 1 . ties: The matrices Gm, GLm, GR"' and GTm satisfy the following proper­ (Oi, O])m+I (Oi, 1J)m+l (li, OJ)m+l (li, 1J)m+l