ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 15 (2018) 337-346 https://doi.org/10.26493/1855-3974.1470.e79 (Also available at http://amc-journal.eu) Tilings of hyperbolic (2 x n) -board with colored squares and dominoes Takao Komatsu School of Mathematics and Statistics, Wuhan University, Wuhan, China Laszlo Nemeth University ofSopron, Institute ofMathematics, Hungary Laszlo Szalay University J. Selye, Department of Mathematics and Informatics, Slovakia Received 23 August 2017, accepted 20 December 2017, published online 26 June 2018 Several articles deal with tilings with squares and dominoes of the well-known regular square mosaic in Euclidean plane, but not any with the hyperbolic regular square mosaics. In this article, we examine the tiling problem with colored squares and dominoes of one type of the possible hyperbolic generalization of (2 x n) -board. Keywords: Tiling, domino, hyperbolic mosaic, Fibonacci numbers, combinatorial identity. Math. Subj. Class.: 05A19, 05B45, 11B37, 11B39, 52C20 1 Introduction In the hyperbolic plane there exist infinite types of regular mosaics, they are denoted by Schlafli's symbol {p, q}, where the positive integers p and q have the property (p - 2)(q -2) > 4, see [5]. If p = 4 they are the regular square mosaics and each vertex of the mosaic is surrounded by q squares. Note that if p = q = 4 we obtain the Euclidean square mosaic. Now we define the (2 x n)-board on mosaic {4, q}, where q > 4. First we take a square Si with vertices A0, A1, B1,B0 according to Figure 1, and later to Figures 2 and 3. As the second step we consider the square S2, which has a common edge A1B1 with S1. The two new vertices are A2,B2. Similarly, we define the squares S3,... ,Sn, their newly constructed vertices are Aj and Bj (3 < i < n), respectively. The union of Sj (1 < i < n) E-mail addresses: komatsu@whu.edu.cn (Takao Komatsu), nemeth.laszlo@uni-sopron.hu (Laszlo Nemeth), laszlo.szalay.sopron@gmail.com (Laszlo Szalay) Abstract ©® This work is licensed under https://creativecommons.Org/licenses/by/3.0/ 338 Ars Math. Contemp. 15 (2018) 441-466 forms the first level of the board. It is depicted with yellow colors in Figures 1-3. (On the left-hand side of Figure 2 the mosaic {4,5} and the (2 x 4)-board are illustrated in Poincare disk model and on the right-hand side there is a "schematic" (2 x 4)-board from the mosaic.) The second level of the board is formed by the squares of the mosaic having at least one vertex from the set {Ai, A2,..., An} and not from {B\, B2,..., Bn, An+1}, where the last point is the appropriate point of the virtually joined square Sn+1 (A0 is not in the first set, see Figure 3). These are the light blue squares in the figures. In the first level, independently from q there are n squares, while the second level contains n(q - 3) squares (see Figure 3). Let rn be the number of the different tilings with (1 x 1)-squares and (1 x 2)-dominoes (two squares with a common edge) of a (2 x n)-board of mosaic {4, q}. It is known that the tilings of a (1 x n)-board on the Euclidean square mosaic can be counted by the Fibonacci numbers [2, 4]. In fact, rn = fn, where {fn}^=0 is the shifted Fibonacci sequence (Fn = fn-1, where Fn is the n-th Fibonacci number, A000045 in OEIS [12]), so that fn = fn-1 + fn-2 (n > 2) holds with initial values f0 = f1 = 1 (and f-1 = 0). 5 ! ^ 2 5 3 S 4 A4 A 5 B0 B1 B0 B1 B2 B0 B1 B2 B3 B0 B1 B2 B3 B4 Figure 1: (2 x 4)-board on Euclidean mosaic {4,4}. Figure 2: (2 x 4)-board on hyperbolic mosaic {4,5}. McQuistan and Lichtman [9] (generalizations in [6]) studied the tilings in case of the Euclidean square mosaic {4,4} and they proved that rn satisfies the identity rn = 3rn-1 + rn-2 - rn-3 (1.1) for n > 3 with initial values r0 = 1, r1 = 2 and r2 = 7 (A030186 in [12]). T. Komatsu et al.: Tilings of hyperbolic (2 x n)-board with colored squares and dominoes 339 Figure 3: (2 x 1)-board and (2 x 4)-board on hyperbolic mosaic {4, q} (q > 5). In the work [3], the generalized Fibonacci number un, where Un = aUn-1 + bun-2, (n > 2) (1.2) with initial values u0 = 1, ui = a (and u-i = 0), is interpreted as the number of ways to tile a (1 x n)-board using a colors of squares and b colors of dominoes. Obviously, if a = b =1 then un = fn. Belbachir and Belkhir proved a couple of general combinatorial identities related to un in [1]. Let Rn be the number of tilings of (2 x n)-board of mosaic {4, q} using a colors of squares and b colors of dominoes. When q = 4 Katz and Stenson [7] showed the recurrence rule Rn = (a2 + 2b)Rn-i + a2b Rn-2 - b3Rn-3, (n > 3) (1.3) with initial values R0 = 1, R1 = a2 + b and R2 = a4 + 4a2 b + 2b2. In this article, we examine the tilings of (2 x n)-board on mosaic {4, q} (q > 4) with colored squares and dominoes in a general way and we obtain the following main theorem. Theorem 1.1. Assume q > 4. The sequence {Rn}^=0 can be described by the fourth order linear homogeneous recurrence relation Rn = «q Rn-1 + Pq Rn-2 + Yq Rn-3 - b2(q-2)Rn-4, (n > 4) (1.4) where (explicit formulas later) aq+2 = aaq+i + baq, (1.5) Pq+3 = (a2 + b)Pq+2 + b(a2 + b)Pq+1 - b3Pq, (1.6) Yq+2 = -abYq+1 + b3Yq (1.7) with initial values «4 = a2 + b, «5 = a(a2 + 3b), P4 = 2b(a2 + b), P5 = b(a2 + b)(a2 + 2b), P6 = b(a6 + 6a4b + 10a2b2 +2b3), Y4 = b2(a2 - b), y5 = — ab3(a2 + b), moreover Ro = 1, R1 = uq-2, R2 = u^-2 + abuq-4uq-3 + bu^-3 + b2u^-4, R3 = (u2 2 + 2abuq-4uq-3 + 2bu^-3 + 2b2u;j-4 )uq-2 + b2(uq-3 uq-4 + (a2 + b)uq-4uq-5 + auq-4)uq-3 + ab3u2-4uq-5. If a = b =1, then Theorem 1.1 leads to the following corollary. Recall that fn = Fn+1 (shifted Fibonacci numbers). 340 Ars Math. Contemp. 15 (2018) 441-466 Corollary 1.2. The sequence |r„}™=0 can be given by the fourth order linear homogeneous recurrence relation rn = 2fq-3 rn-1 + (5/2-4 + (-1)q-1) fn-2 + 2(-1)qfq-5 rn-3 - r„-4, (n > 4) (1.8) with initial values ro = 1, ri = fq-2, r2 = 7fq2-4 + 7fq-4fq-5 + 2/2-5 and r3 = 22fq3-4 + 36fq2-4fq-5 + 19fq-4fq2-5 + 3fq3-5. Observe, that if q = 4, then (1.4) returns with (1.3) (compute the sum of Rn and bRn-1). Similarly, the extension of (1.1) is (1.8). 2 Tilings on mosaic {4, q} We can see that our tiling exercise of the hyperbolic (2 x 1)-board on the mosaic {4, q} (q > 5) is the same as the tiling exercise of the Euclidean (1 x (q - 2)) -board. So R1 = Uq-2 and r1 = fq-2 (Figure 3). Before the discussion of the main result, we define the break-ability of a tiling. A tiling of a (2 x n)-board is breakable in position i fo( 1 < i < n - 1, if this tiling is a concatenation of the tilings of a (2 x i)-subboard and a (2 x (n - i)) -subboard. Clearly, the number of colored tilings of such a board is RiRn-i. A tiling is unbreakable in position i in three different ways: if a domino covers the last square of the first subboard and the first square of the second subboard either in the first or the second level, or on both levels (see Figure 4). a r^ i & \ c 01 i n 01 i n 01 i n 01 i n Figure 4: Breakable and unbreakable tilings in position i when q = 7. Now, we define three subboards. Let Ai, Bi and Ci be the subboards of (2 x i)-board (1 < i < n), respectively, where the last square from second level, the last square from first level and the last squares from both levels are deleted from (2 x i)-board. In Figure 4 these subboards are illustrated. Let Ai, Bi and Ci denote the number of different colored tilings of Ai, Bi and Ci, respectively. 2.1 Proof of Theorem 1.1 and Corollary 1.2 Our proof is based on the connections among (2 x n)-board, An, Bn and Cn subboards. We can easily give the number of tilings if n =1. They are R1 = uq-2, A1 = uq-4, B1 = uq-3 and C1 = uq-4. Moreover let R0 = 1, A0 = B0 = C0 = 0. Generally, if n > 2, then Figure 5 shows the recurrence connections of the subboards. For example, let us see the first )ow. We can build a full (2 x n)-board by four different ways from the full (2 x (n - 1))-board or from the subboards An-1, Bn-1 and Cn-1. If we join a suitable (2 x 1)-board to a (2 x (n - 1))-board, then the coefficient uq-2 is obvious in case of the breakable tilings in position n - 1. When we complete An-1 to a full (2 x n)-board, we have a domino in the second level with b different colors, and we put a square onto the first level with a colors. (If we replace the laid down domino in the second level with two squares, then these tilings would be a part of the first case when we T. Komatsu et al.: Tilings of hyperbolic (2 x n)-board with colored squares and dominoes 341 completed the (2 x (n — 1))-board.) The rest part can be tiled freely. Consequently, the coefficient of An-1 is abuq-4 and these are unbreakable tilings in position n — 1. Now, let us complete Bn-1 and Cn-1 to be full (2 x n)-board with a domino in the first level or with two dominoes, one is in the first level and the other in the second level, respectively. The rest parts can be tiled freely. We obtain buq-3 and b2uq-4 new (unbreakable in position n — 1) tilings. Summarising the result of the first row of Figure 5 we have the first equation of the system of recurrence equations (2.1). The determinations of the other rows can be explained similarly. We mention, that, for example, in the fourth row Bn-1 does not appear, because when we complete it to Cn we do not have new tiling type, the tilings are in the first tiling types in the same row. (The yellow square would be in the grey (2 x (n — 1)) -board - see the last row in Figure 5.) Hence the recurrence equations for n > 1 satisfy the system Figure 5: Base of recurrence connections of the subboards. Rn = Uq-2Rn-l + abUq-^An-l + bUq-^Bn-l + b Uq-4 Cn-l A n = Uq-^Rn-l + abUq-5An-1 + bUq-^Bn-l + b Uq-5 Cn-l (2.1) Bn = Uq-sRn-l + bUq-^An-l Cn = Uq-^Rn-l + bUq-^An-l. coefficients of (2.1) is M are Ro = 1, Ao = Bo = Co Uq- 2 ab Uq-4 b Uq -3 b2 Uq- 4\ Uq- 3 ab Uq-5 b Uq -4 b2 Uq- 5 Uq- 3 b Uq-4 0 0 Uq- 4 b Uq-5 0 0 ) 0. The matrix of the As usual, the characteristic equation of M provides the recurrence relation for {Rn} (and {An}, {Bn}, {Cn}; see the proof in [10]. The computation was made by the help of software Maple.) Thus we have Rn '■q Rn-l + Pq Rn-2 + Yq Rn-3 + ÔqRn-4 > 4) (2.2) 342 Ars Math. Contemp. 15 (2018) 441-466 where (with some calculation using (1.2)) aq = abuq-5 + uq-2, ftq = b(b2u2q_5 - aUq-5Uq-2 + 2bu2q_4 + aUq-4Uq-3 + u2q_3), Yq = -bq (buq_5uq-q - 2uq-Au2q_3 + auq-5uq_3 + u2q_4uq-q), Sq = -bA(u2q_zu2q_3 - 2uq_5u2q_4uq_3 + u^4). Moreover, we obtain the initial values of the recurrence for n = 1,2, 3 from system (2.1). They are R1 = uq_2, R2 = u2q_2 + abuq_4uq_3 + bu2q_3 + b2u2q_4 and R3 = (u2q_2 + abuq_4uq_3 + buq_3 + b2 u2q_4)uq_2 + (abuq_2 uq_4 + a2b2uq_Auq_5 + b2V,q_3V,q_4 + b3 uq_4uq_5)uq_3 + (buq_2uq_3 + ab2u2q_4)uq_3 + (b2uq_2V,q_4 + ab3uq_iuq_5)uq_4:. In the next part, we prove that relations (1.5)-(1.7) hold. Firstly, we insert aq+2, aq+1 and aq into (1.5) to have abuq_3 + uq = a(abuq_4 + uq_l) + b(abuq_5 + uq_2 ). (2.3) Apply (1.2) consecutively with n = q,q - 1,... as follows. First plug uq into the equation (2.3), then substitute uq_1 in the new equation, and so an. Finally, when n = q - 3, we find that (2.3) is an identity, so (1.5) holds. If q = 4 and q = 5, then aq provides the initial values. The proofs of (1.6) and (1.7) go similarly. Finally, we show that Sq = -b2(q_2). For q = 4 we immediately obtain S4 = -b4(u2_5u2_3 - 2u4_5u2_4u4_3 + uj_4) = -b22. Then we consider the recurrence relation (q > 4) xq+1 = b2xq. (2.4) Some calculations show that both expressions (Sq and -b2(q_2)) satisfies recursion (2.4), which implies the equality. We express the values by uq_4 and uq_5 by using relation (1.2). Thus we have aq = (a2 + b)uq_4 + 2abuq_5, Pq = (2a2 + 2b)bu2q_4 + (-a3 + 2ab)buq_4uq_5 + (-a2b + 2b2)bu2q_5, Yq = (a2 - b)b2u3_4 - (a3 - 3ab)b2u^_4uq_5 - (3a2b - b2)b2uq_4u^_5 - 2ab4u3q_z, Sq = -b2(q_2). As F2 - FnFn_i - F2_1 = (-l)^1, if a = b = 1, then we obtain aq — 2fq-4 + 2fq-5 — 2fq-3 ftq — + fq-fq-5 + fq-5 — Bf2- + (-\)q-1, Yq — 2f2-4fq-5 - 2fq-4f2-5 - 2f\_5 — 2(-l)q fq-5, 5q — -1. Now the initial values Ri lead to the initial values ri (i — 1,2,3). T. Komatsu et al.: Tilings of hyperbolic (2 x n)-board with colored squares and dominoes 343 2.2 Unbreakable tilings In this subsection we determine the number of unbreakable tilings. Let rn (and Rn) be the number of different unbreakable tilings with (colored) squares and dominoes of (2 x n)-boardof {4, q}. Moreover, let Ai, Bi and Ci denote the number of the different unbreakable colored tilings of Ai, Bi and Ci, respectively. Theorem 2.1. The sequence {Rn} can be described by the binary recurrence relation Rn = abuq-sRn-i + b2 {uq-4 + buq-5) Rn-2, (n > 3) where the initial values are R\ = uq-q and Rq = abuq-3uq-4 + bUq-3 + b2u^-4. Proof. The proof is similar to the proof of the first theorem. By deleting the breakable tilings from Figure 5 (the second column) we gain the system of recurrence sequences (n > 2) Rn = abuq-4An-1 + buq-0,Bri-l + b uq-4 3) with coefficients linked to Fibonacci numbers, where the initial values are rl = fq-q and C = 2fq-4fq-q + (-1)q-\ 3 Some identities In the sequel, we give certain identities related to the sequences {Rn} and {Rn}. The proofs are based on the tilings, not on the recursive formulae. Identity 3.1. If n > 1, then nl Rn ^ ^ RiRrn-i- i=0 344 Ars Math. Contemp. 15 (2018) 441-466 Proof. Let us consider the breakable colored tilings in position i (0 < i < n) of (2 x n)-board, where the tilings on the right (2 x (n - i)) -subboard are unbreakable (see Figure 6). The number of this tilings is RiRn-i. If i = 0, then the tilings are unbreakable on the whole (2 x n)-board. Clearly, when i goes from 1 to n - 1, we have different tilings and we consider all of them exhaustedly. □ Figure 6: Breakable tilings in position i in case of Identity 3.1. An equivalent form of Identity 3.1 is Identity 3.2. If n > 1, then n Rn ^ ^ Rn- i-^i-i=l The next statement gives another rule of summation. Identity 3.3. If m > 1 and n > 1, then n m Rn+m RnRm + ^ ^ ^ ^ Rn-iRm-jRi+j • i=1 j = 1 Proof. Let us consider a (2 x (n+m)) -board as the concatenation of (2 x n)-board and (2 x m)-board (in other words, tilings are breakable in position n). First we take the breakable tilings in position n, their cardinality is Rn Rm. Then we examine the unbreakable tilings in this position. We cover the position n by i + j long unbreakable tilings from position n - i to n + j. They give the rest tilings. Figure 7 illustrates these two cases. □ 0 n R Rm 0 n n+m 0 n-i n+j n+m Figure 7: Tilings in case of Identity 3.3. Identity 3.3 admits the following remarkable specific cases by the choice of m = 1, m = (k — 1)n and n = n — k, m = n + k, respectively. Identity 3.4. If n > 1, then Rn+l = RnRl + ^^ Rn-iRi+1- Identity 3.5. If n > 1 and k > 2, then (k-l)n Rkn = RnR(k-1)n + ^^ ^^ Rn-iR n-iR(k- 1)n-j Ri+j i= 1 j = 1 T. Komatsu et al.: Tilings of hyperbolic (2 x n)-board with colored squares and dominoes 345 Identity 3.6. If n > k > 0 then n — kn+k R2n = Rn—k Rn+k + ^^ ^^ Rn—k—iRn+k—j Hi+j . i=1 j = 1 Finally, we give an identity about the product of two arbitrary terms of the sequence {Rn}. Identity 3.7. If n, m > 1, then n— 1 m— 1 RnRm ^ ^ ^ ^ RiRj Rn—i^^m—j . i=0 j=0 Proof. Consider a (2 x (n + m)) -board as a concatenation of (2 x n)-board and (2 x m)-board. The result is derived in a direct manner from the number of the breakable tilings in position n. See Figure 8. □ 0 in n+j n+m Figure 8: Tilings in case of Identity 3.7. 4 Conclusion and future work In this article, we introduced a generalization of the square boards on the hyperbolic regular square mosaics and examined the combinatorial properties of tilings on these mosaics with colored squares and dominoes. As there are the infinite number of regular mosaics in the hyperbolic plane we hope that the examinations of the combinatorial properties of other tilings give some useful results. Moreover, we are informed on two additional timely articles about hyperbolic space tilings [8, 11]. References [1] H. Belbachir and A. Belkhir, Tiling approach to obtain identities for generalized Fibonacci and Lucas numbers, Ann. Math. Inform. 41 (2013), 13-17, http://ami.ektf.hu/uploads/ papers/finalpdf/AMI_41_from13to17.pdf. [2] A. T. Benjamin, S. S. Plott and J. A. Sellers, Tiling proofs of recent sum identities involving Pell numbers, Ann. Comb. 12 (2008), 271-278, doi:10.1007/s00026-008-0350-5. [3] A. T. Benjamin and J. J. Quinn, The Fibonacci numbers—exposed more discretely, Math. Mag. 76 (2003), 182-192, doi:10.2307/3219319. [4] A. T. Benjamin and J. J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, volume 27 of The Dolciani Mathematical Expositions, Mathematical Association of America, Washington, DC, 2003, http://www.jstor.org/stable/10.4169/j. ctt6wpwjh. 346 Ars Math. Contemp. 15 (2018) 441-466 [5] H. S. M. Coxeter, Regular honeycombs in hyperbolic space, in: J. C. H. Gerretsen and J. de Groot (eds.), Proceedings of the International Congress of Mathematicians 1954, Volume III, North-Holland, Amsterdam, 1956 pp. 155-169, proceedings of the International Congress of Mathematicians 1954 held at Amsterdam, September 2-9, 1954. [6] R. Kahkeshani, The tilings of a (2 x n) -board and some new combinatorial identities, J. Integer Seq. 20 (2017), Article 17.5.4, https://cs.uwaterloo.ca/journals/JIS/ VOL20/Kahkeshani/kahk3.html. [7] M. Katz and C. Stenson, Tiling a (2 x n)-board with squares and dominoes, J. Integer Seq. 12 (2009), Article 9.2.2, https://cs.uwaterloo.ca/journals/JIS/VOL12/ Stenson/stenson8.html. [8] Z. Lucic, E. Molnar and N. Vasiljevic, An algorithm for classification of fundamental polygons for a plane discontinuous group, in: M. D. E. Conder, A. Deza, and A. Ivic Weiss (eds.), Discrete Geometry and Symmetry, Springer, Cham, volume 234 of Springer Proceedings in Mathematics & Statistics, pp. 257-278, 2018, doi:10.1007/978-3-319-78434-2_14, dedicated to Karoly Bezdek and Egon Schulte on the occasion of their 60th birthdays. [9] R. B. McQuistan and S. J. Lichtman, Exact recursion relation for 2 x N arrays of dumbbells, J. Math. Phys. 11 (1970), 3095-3099, doi:10.1063/1.1665098. [10] L. Nemeth and L. Szalay, Power sums in hyperbolic Pascal triangles, An. St. Univ. Ovidius Constanta, Ser. Mat. 26 (2018), 189-203, doi:10.2478/auom-2018-0012. [11] I. Prok, On maximal homogeneous 3-geometries—A polyhedron algorithm for space tilings, Universe 4 (2018), Article 49, doi:10.3390/universe4030049. [12] N. J. A. Sloane (ed.), The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org.