On the Enumeration of Chequered Tilings in Polygons

Year: 2017 Authors: Hiroaki Hamanaka; Takashi Horiyama; Ryuhei Uehara

Core claim

Rhombus tilings of a dodecagon with a hole are bijective with special pseudoline arrangements and special Amidakujies, enabling dynamic-programming enumeration.

Topics

polygon tilings, pseudoline arrangements, Amidakuji enumeration, Tokyo 2020 emblems

Domains

combinatorics, discrete geometry, enumerative algorithms, bijections, graphic design, logo design, visual patterning, ornamental tilings

Methods

bijection proof, dynamic programming, enumeration, combinatorial modeling

Media

rhombus tilings, dodecagon with hole, Amidakuji diagrams, conference figures

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2017 Conference Proceedings

On the Enumeration of Chequered Tilings in Polygons

Hiroaki Hamanaka Hyogo University of Teacher Education 942-1 Shimokume Kato-city, Hyogo 673-1494, Japan hammer@hyogo-u.ac.jp

Takashi Horiyama Saitama University 255 Shimo-Okubo, Sakura, Saitama 338-8570, Japan horiyama@al.ics.saitama-u.ac.jp

Ryuhei Uehara Japan Advanced Institute of Science and Technology 1-1 Asahidai, Nomi, Ishikawa 923-1292, Japan uehara@jaist.ac.jp

Abstract

The Tokyo 2020 Olympic and Paralympic games emblems, called ‘harmonized chequered emblems,’ are designed with three kinds of rectangles. We enumerate all such tilings in a dodecagon with a hole.

1 Introduction

Figure 1 illustrates the Tokyo 2020 Olympic and Paralympic games emblems, which are called ‘harmonized chequered emblems.’ They are designed with three kinds of rectangles, where the rectangles are derived from three kinds of rhombuses of unit edge length. As shown in Figure 2, the rectangles are obtained by joining the midpoints of the four sides of each rhombus. The rhombuses in Figure 2 respectively have the angles of (a) 30 and 150 degrees, (b) 60 and 120 degrees, and (c) 90 degree. As illustrated in Figure 3, the emblems can be seen as tilings with the rhombuses of a regular dodecagon with edge length two. We enumerate all tilings of the three rhombuses in a dodecagon, where the dodecagon has a hole in the top or center of the shape.

Figure 1: Tokyo 2020 Olympic and Paralympic Games Emblems.

2 Tiling of Rhombuses

While the dodecagons in Figure 3 have holes, we at first consider the case when a dodecagon has no holes. A rhombus tiling of a $2n$ -gon corresponds to a pseudoline arrangement, where two pseudolines cross in at most

Hamanaka, Horiyama and Uehara

Figure 2: Three rectangles and their surrounding rhombuses of the same edge length.

Figure 3: Tilings of three kinds of rhombuses in a dodecagon.

Figure 4: Pseudoline arrangement corresponding to a rhombus tiling.

one point [1]. For example, suppose that we have a rhombus tiling given by the black lines in Figure 4. By connecting the midpoints of parallel sides of all rhombuses, we can obtain the red pseudolines in the figure, where the labels $i_L$ and $i_R$ ( $i=1,2,\dots ,6$ ) indicate the end points of the pseudolines. We can see that (1) two pseudolines $i_L$ and $i_R$ in the arrangement do not cross for any $i=1,2,\dots ,6$ , (2) two pseudolines $i_{{\ell }_i}$ and $j_{{\ell }_j}$ cross exactly once for $i\ne j$ and ${\ell }_i,{\ell }_j\in \{L,R\}$ , (3) there is no point where three (or more) pseudolines cross, and (4) each crossing of two pseudolines corresponds to a rhombus in the tiling.

In our case, we have a hole in the top or center of the dodecagon. We can regard the hole as a special piece, and a rhombus tiling with the hole as a tiling with rhombuses and the special piece in the specified position (i.e., in the top or center of the dodecagon). As shown in Figure 5, the pseudolines may be split into two segments by the special piece. We call such an arrangement as a pseudoline arrangement with a hole. In Figure 5 (a), the dodecagon and the hole share two sides $1_L$ and $6_L$ . In this case, we say pseudolines $1_L$ and $6_L$ are split into two segments although the segments $1_L$ and $6_L$ above the hole have length 0. Also

(a) Figure 5: Pseudoline arrangements with holes.

(b)

On the Enumeration of Chequered Tilings in Polygons

Figure 6: Amidakuji corresponding to the pseudoline arrangement in Figure 4.

note that the sides of the special piece have labels $1_{{\ell }_1},2_{{\ell }_2},\dots ,6_{{\ell }_6}$ in this order, where ${\ell }_i\in \{L,R\}$ for $i=1,2,\dots ,6$ . More precisely, a pseudoline arrangement with a hole is an arrangement of $2n$ pseudolines, where (1) $n$ pseudolines $1_{{\ell }_1},2_{{\ell }_2},\dots ,n_{{\ell }_n}$ ( ${\ell }_i\in \{L,R\}$ for $i=1,2,\dots ,n$ ) are split into two segments by the hole, (2) the sides of the hole has labels $1_{{\ell }_1},2_{{\ell }_2},\dots ,n_{{\ell }_n},1_{{\ell }_1},2_{{\ell }_2},\dots ,n_{{\ell }_n}$ in this order, (3) no pair of pseudolines $i_L$ and $i_R$ crosses, (4) no pair of pseudolines in $\{1_{{\ell }_1},2_{{\ell }_2},\dots ,n_{{\ell }_n}\}$ crosses, (5) each pair of pseudolines that does not appear in (3) nor (4) crosses exactly once, (6) there is no point where three (or more) pseudolines cross. Note that each arrangement has exactly $3\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ crossings. Now, we have the following theorem.

Theorem 1. Let $S_t$ and $S_{pa}$ be the sets of all tilings of the rhombuses in a 2n-gon with a hole and all arrangements of 2n pseudolines with a hole, respectively. Then, there is a bijection from $S_t$ to $S_{pa}$ .

In [2], Yamanaka et al. gave the correspondence between pseudoline arrangements and Amidakujies (i.e., ladder lotteries, or Ghost Legs). An Amidakuji consists of $m$ vertical lines (lines for short) and some horizontal bars (bars for short), where lines have their labels, each bar connects two consecutive lines. Each bar denotes the exchange of the labels of a pair of lines, which corresponds to a crossing of two pseudolines in an arrangement. We can draw the Amidakuji in Figure 6 corresponding to the pseudoline arrangement in Figure 4. In the Amidakuji, we have 12 lines corresponding to the pseudolines in the arrangement. The labels on the top of the Amidakuji correspond to the labels of the pseudolines in the right half of the dodecagon in Figure 4. The topmost bar exchanges $1_R$ and $2_L$ , and the second bar exchanges $1_L$ and $2_L$ (note that the second line from the left has label $2_L$ because of the topmost bar). By the consecutive exchanges, we can obtain the labels in the bottom of the Amidakuji corresponding to the labels in the left half of the dodecagon.

In our case, we introduce a special bar corresponding to the special piece (i.e., the hole) in the tiling, that reverses the labels of pseudoline segments. For example, Figure 7 illustrates Amidakujies corresponding to the pseudoline arrangements in Figure 5. The bars, except for the blue bars, exchange the labels as in the usual Amidakujies. The blue bold bars connecting 6 lines represent the special bars. The special bar in Figure 7(a) exchange the labels from $1_L,2_L,3_L,4_L,5_L,6_L$ to $6_L,5_L,4_L,3_L,2_L,1_L$ . The special bar in Figure 7(b) exchange the labels from $1_R,2_R,3_L,4_L,5_R,6_R$ to $6_R,5_R,4_L,3_L,2_R,1_R$ . We define special Amidakujies as follows: A special Amidakuji is an Amidakuji with $2n$ lines and a special bar and $3\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ (usual) bars, where the $2n$ lines have labels $1_L,1_R,2_L,2_R,\dots ,n_L,n_R$ , a special bar exchange the labels from $1_{{\ell }_1},2_{{\ell }_2},\dots ,n_{{\ell }_n}$ to $n_{{\ell }_n},(n-1{)}_{{\ell }_{n-1}},\dots ,1_{{\ell }_1}$ ( ${\ell }_i\in \{L,R\}$ for $i=1,2,\dots ,n$ ), and bars do not exchange the same pair of labels twice, and do not exchange the pairs of $i_L$ and $i_R$ ( $i=1,2,\dots ,n$ ). Now, we have the following theorem.

Theorem 2. Let $S_{pa}$ and $S_a$ be the sets of all arrangements of $2n$ pseudolines with a hole and all special Amidakujies with $2n$ lines, respectively. Then, there is a bijection from $S_{pa}$ to $S_a$ .

Hamanaka, Horiyama and Uehara

(a)

(b) Figure 7: Amidakujies corresponding to the pseudoline arrangements in Figure 5.

3 Chequered Tiling with a Hole

We have designed a DP (dynamic programming) algorithm for enumerating all special Amidakujies, and then converted them into rhombus tilings with holes. The number of rhombus tilings with a hole in the top and center is 3,357,270 and 539,968, respectively. (We distinguish two tilings even if one is a rotation/reflection of another.) Figure 8 is a partial list of the enumerated chequered tilings with a hole in the center of the dodecagon.

Figure 8: Partial list of enumerated tilings.

References

[1] O. Bodini, T. Fernique, M. Rao, and E. Rémila, Distance on Rhombus Tilings, Theoretical Computer Science, 412 (2011), pp. 4787-4794. [2] K. Yamanaka, S. Nakano, Y. Matsui, R. Uehara, and K. Nakada, Efficient enumeration of all ladder lotteries and its application, Theoretical Computer Science, 411 (2010), pp. 1714-1722.