Colorful Tilings and Permutations

Jonathan Beagley and Lara Pudwell Department of Mathematics and Statistics Valparaiso University Valparaiso, IN 46383 USA

                     jon.beagley@valpo.edu
                    lara.pudwell@valpo.edu

Abstract We study tilings of rectangular and circular arrays with specified sets of colored rectangular tiles. In particular, we consider rectangular tiles of arbitrarily large size, but where the number of colors available to use on a particular tile is determined by its position on the array. While tiling enumeration is often used to prove identities involving Fibonacci and Lucas numbers, the tilings we examine yield natural connections with sets of permutations.

1 Introduction

We consider tilings of rectangular and circular arrays with colored tiles. It is well known that the number of ways to tile an n×1 rectangle with dominoes and squares is given by the nth Fibonacci number, and the number of ways to tile an n-cell circular array with dominoes and squares is given by the nth Lucas number. These types of tilings have been generalized in a number of ways, and an excellent survey of enumerative and bijective results resulting from tilings is given by Benjamin and Quinn [1].

A recent paper of Dresden and Xiao [2] considers tilings of n × 1 rectangles and n-cell circular arrays with tiles of any size i × 1, where 1 ≤ i ≤ n and where i × 1 tiles come in i different colors. They use these colored tilings to prove identities involving weighted sums of Fibonacci numbers. In any Fibonacci or Lucas-type tiling, a tile is uniquely described by its size and position. While Dresden and Xiao determined the number of colors of a tile by the size, in this paper we ask the analogous enumeration questions when the number of colors

\begin{matrix}1 \\ 2 \\ … \\ n \end{matrix}  \begin{matrix}1 \\ 2 \\ … \\ n \end{matrix}

Figure 1: An n-cell rectangular board and an n-cell circular array.

available to a tile is determined by its position. In particular, we number the cells of an n × 1 rectangle consecutively from left to right, and we number the cells of an n-cell circular array consecutively in a clockwise fashion as shown in Figure 1. We consider a family of six enumeration questions, determined by the following parameters:

• What board is to be tiled? (n × 1 rectangle or n-cell circular array)

• What is the number of possible colors of a tile? (determined by the biggest cell that is covered, the smallest cell that is covered, the last value cell that is covered, or the first value cell that is covered)

In a circular array, the first and last valued cells are determined by reading the cells in clockwise order. In a rectangle tiling, “first” and “smallest” are equivalent, as are “last” and “biggest”. The same is true for many tiles on a circular array; however, in a circular array, tiles of size 2 or more may cover both cell n and cell 1 simultaneously, and these conventions differ for these “straddling tiles”.

We explore each of these questions in turn and analyze the resulting enumeration sequences. In particular, rather than having connections to Fibonacci and Lucas numbers, this new family of tilings results in connections with various families of permutations. Throughout this paper, we think of permutations combinatorially, rather than algebraically. That is, a permutation π of size n is a list of the numbers 1, 2, …, n where order matters. In particular, it will be useful to think about the inversions of the permutations in question. An inversion in a permutation π = π_{1} ⋯ π_{n} is a pair of entries π_{i} and π_{j} such that i < j but π_{i} > π_{j}.

In Section 2 we consider tilings of an n×1 rectangle according to two different conventions for the number of colors available to each tile, and in Section 3 we consider tilings of an n-cell circular array according to four different conventions for the number of colors available to each tile. For each tiling problem, we give both an enumeration of the possible tilings and a bijective connection with a specific family of permutations.

2 Rectangle tilings

Let r_{n} be the number of tilings of an n×1 rectangular board with i×1 tiles where 1 ≤ i ≤ n. Clearly r_{0} = r_{1} = 1. In general, we can divide the tilings into cases by conditioning on the size of the last tile. If the last tile is of size i, then the rest of the board is an (n − i) × 1 board with the same tiling rules, so we have

r_{n} = ∑_{i=1}^{n} r_{n−i}.

This recurrence yields r_{n} = 2^{n−1}; this is sequence \underline{A000079} in the On-Line Encyclopedia of Integer Sequences (OEIS). We can see this result more directly, since any tiling of an n × 1 rectangle corresponds to a composition of n, i.e., an ordered list of positive integers whose sum is n. We really must decide whether each of the n − 1 boundaries between cells is a boundary between two distinct tiles or not, yielding 2^{n−1} possible uncolored tilings.

Now that we understand the monochromatic tiling case, we consider colored tilings where each tile is assigned a color and the number of colors available to a tile is determined by the tile’s position.

Theorem 1. Let rb_{n} be the number of tilings of an n × 1 rectangle where the number of possible colors of a tile t is determined by the biggest cell t covers. Then for n ≥ 1 we have

rb_{n} = n · n!. (OEIS \underline{A094258})

Proof. Notice that for n ≥ 1, n · n! is the number of permutations of [n + 1] = {1, …, n + 1} whose final digit is not n + 1.

Now consider a tiling of an n × 1 rectangle where the number of colors available to a tile is determined by the largest cell it covers and name the tiles t_{1}, t_{2}, …, t_{m} from left to right. Given tile t_{i} of length ℓ_{i} and color c_{i} let f̂(t_{i}) be the sequence 0^{ℓ_{i}−1}, c_{i}. Now, for any tiling t_{1}t_{2} ⋯ t_{m} of an n × 1 rectangle, we may associate a sequence s = s_{1} ⋯ s_{n+1} formed by concatenating 0f̂(t_{1})f̂(t_{2}) ⋯ f̂(t_{m}). To find the permutation f(t_{1}t_{2} ⋯ t_{m}) that corresponds to the entire tiling, begin with the permutation 12 ⋯ (n + 1). Then, for 1 ≤ i ≤ n + 1, move the digit i to the left s_{i} positions. Since s_{n+1} ≥ 1, this generates a permutation of [n + 1] that does not end in n+1. In the resulting permutation, j is the larger digit in s_{j} inversions.

This construction is invertible. Consider a permutation π of length n+1. The position of n + 1 determines the color of the last tile. Also, after deleting the digit n + 1, the longest run of digits where π_{i} = i at the end of the permutation (possibly of length 0) is one less than the length of the last tile. We can then delete these final digits and recursively determine the size and length of each successive tile from right to left.

As an example, consider the tiling t_{1}t_{2}t_{3}t_{4} in Figure 2. We have f̂(t_{1}) = 02, f̂(t_{2}) = 004, f̂(t_{3}) = 6, and f̂(t_{4}) = 5. Together this tells us that s = 00200465. Reading this sequence from left to right, we begin with 12345678. Since s_{1} = s_{2} = 0, we see that 1 and 2 are involved in 0 inversions, but since s_{3} = 2, the digit 3 appears ahead of 1 and 2, and alters our permutation to 31245678. Similarly, 4 and 5 are involved in no inversions, but s_{6} = 4 tells us that 6 is involved in 4 inversions so our permutation becomes 36124578. Since s_{7} = 6, we move 7 to the left by 6 positions to obtain 73612458. Since s_{8} = 5 we move 8 to the left by 5 positions to obtain π = f(t_{1}t_{2}t_{3}t_{4}) = 73861245. Similarly, the permutation π = 3216475 corresponds to the tiling shown in Figure 3. In general, the colors of tiles correspond to the number of inversions involving a specified digit, so these tilings are an alternate representation of inversion sequences. In Section 3 we will use variations of this bijection to understand tilings of circular arrays.

2 4 6 5

Figure 2: A 7-cell biggest-color rectangle tiling, where each tile is labeled with its color, corresponding to 73861245.

1 2 2 1

Figure 3: A 6-cell biggest-color rectangular board, where each tile is labeled with its color, corresponding to 3216475.

Next, we consider an alternate coloring rule that is related to a different family of permutations.

Theorem 2. Let rs_{n} be the number of tilings of an n × 1 rectangle where the number of possible colors of a tile t is determined by the smallest cell t covers. Then

rs_{n} = \frac{(n + 1)!}{2}. (OEIS \underline{A001710})

Proof. We prove this inductively.

When n = 1, there is one tiling, as expected.

Now suppose rs_{n} = \frac{(n+1)!}{2} and consider a tiling of an (n + 1) × 1 board. Either the last tile is a square with one of n + 1 colors, and the rest of the tiling is a tiling of an n × 1 board, or the last tile is a k × 1 tile (k > 1) with the number of colors determined by its first cell. We can shrink this last tile to be a (k − 1) × 1 tile with the same color to obtain a tiling of an n × 1 board. Either way, each n × 1 tiling corresponds to n + 2 different tilings of an (n + 1) × 1 board; n + 1 that end in squares, and one that results from stretching the size of

the final tile. This tells us rs_{n+1} = (n + 2) rs_{n} = \frac{(n + 2)!}{2}, as desired.

An even (resp. odd) permutation is a permutation with an even (resp. odd) number of inversions. Among the n! permutations of length n (where n ≥ 2), exactly half of them are

tiling T permutation g(T) tiling T permutation g(T)
1  1234  1 1 1  2143
11  2314  1 1 2  2431
12  3124  1 1 3  4213
11  1342  1 2 1  3241
12  1423  1 2 2  3412
13  4132  1 2 3  4321

Table 1: All smallest-color tilings of a 3 × 1 rectangular board and their corresponding even permutations of length 4.

even. (To see this, notice that transposing the final two digits of a permutation provides a bijection between odd permutations and even permutations of the same length.) Although the proof of Theorem 2 is relatively succinct, we may also give a bijection g(T) between the tilings counted by rs_{n} and the even permutations of length n + 1.

As a base case, when n = 1, there is one tiling, and there is one even permutation of length 2, namely 12.

Now, for n ≥ 2, we show that if there is a bijection between tilings counted by rs_{n−1} and even permutations of length n, then this extends to a bijection between tilings counted by rs_{n} and even permutations of length n + 1.

Consider a tiling counted by rs_{n}. If the last tile has length 2 or greater, find the permutation that corresponds to shrinking the last tile by 1 square and append n + 1 on the end of the permutation. This is guaranteed to be an even permutation because there are still an even number of inversions among the digits 1, 2, …, n, and n+1 is involved in no inversions.

Otherwise, the last tile has size 1 and color c where 1 ≤ c ≤ n. Consider the permutation π′ that corresponds to the tiling where this final tile is removed. π′ is necessarily even. Now, if c is even, insert n+1 in position n+1−c, which involves n+1 in c inversions and produces an even permutation. On the other hand if c is odd, then transpose the last two digits of π′ to get an odd permutation of length n and then insert n + 1 in position n + 1 − c to involve n + 1 in an odd number of inversions and produce an even permutation.

This procedure is invertible. The position of the largest digit in an even permutation uniquely determines whether the last tile has length 1 or is longer. If the last tile is square, the position of n+1 also determines its color. We may delete digit n+1 from the permutation and recursively determine the unique tiling that goes with this new permutation of length n and then either extend the last tile or add an appropriately-colored square to complete the tiling.

As an example, Table 1 gives the twelve possible smallest-color tilings of a 3×1 rectangle along with their corresponding even permutations of length 4.

3 Circular array tilings

Next we consider tilings of an n-cell circular array. As in the rectangular case, it is instructive to first count uncolored tilings. Consider the tile covering 1 to be the “first” tile. This tile has size i where 1 ≤ i ≤ n, and there are i positions this tile could have (depending on whether cell 1 is the first, second, …, or ith cell covered by the tile). Then there are n − i remaining cells, which can be covered in 2^{n−i−1} ways if i < n (or 1 way if i = n), since tiling this portion of the circle is equivalent to covering an (n − i) × 1 rectangle. Therefore, there are n + ∑_{i=1}^{n−1} i2^{n−i−1} = 2^{n} − 1 (OEIS \underline{A000225}) ways to tile an n-cell circular array. We can also see this enumeration more directly; we either choose to include or omit each of the n boundaries between adjacent cells as a boundary between distinct tiles, and the only invalid choice is to select 0 such boundaries.

Now, consider the situation where the number of colors available to a tile is determined by its position. Just as the number of uncolored tilings of a circular array is a weighted sum of tilings of rectangles, the same general idea holds when we introduce colored tiles to circular arrays. In this section, we consider four conventions: the number of colors available to a tile is given by the first, smallest, last, or biggest cell covered. For many tiles the first two conventions will be the same and the last two conventions will be the same, but circular arrays may have tiles that simultaneously cover both cell n and cell 1, and these cells will be treated differently by the various conventions. For example, a 4 × 1 tile that covers cells n − 1, n, 1, and 2 has n − 1 as its first cell, 1 as its smallest cell, 2 as its last cell, and n as its biggest cell. Similar to the enumerations in Section 2, in this section we find sequences connected with specific families of permutations. While two of these enumerations are equal and the resulting sequence is in the On-Line Encyclopedia of Integer Sequences [3], the other two appear to be new to the literature.

Theorem 3. Let cl_{n} be the number of tilings of an n-cell circular array where the number of possible colors of a tile t is determined by the last cell t covers, and let cf_{n} be the number of tilings of an an n-cell circular array where the number of possible colors of a tile t is determined by the first cell t covers. Then

cl_{n} = cf_{n} = (n + 1)! − 1. (OEIS \underline{A033312})

Proof. Consider an uncolored tiling T of an n-cell circular array whose tiles have last cells c_{1}, …, c_{m}. Rotating this tiling counterclockwise by one position yields tiling T′ whose tiles have first cells c_{1}, …, c_{m}. Therefore the number of colorings of T counted by cl_{n} equals the number of colorings of T′ counted by cf_{n}.

Now, we focus on cl_{n} and show that cl_{n} = rb_{n} + cl_{n−1}. Consider a tiling counted by cl_{n}. Either the colored tile covering position n also covers position 1 or not. If not, by cutting the circular array between cells 1 and n, we have a tiling equivalent to one of the rb_{n} tilings counted by Theorem 1. Alternatively, if the colored tile covering position n also covers position 1, then we may shrink the tile by 1 square and remove position n from the circular array to obtain a colored tiling counted by cl_{n−1}, provided n > 1.

Assuming that cl_{n} = (n + 1)! − 1, consider cl_{n+1} = rb_{n+1} + cl_{n}. Using Theorem 1, rb_{n} = n · n! and by our inductive hypothesis we conclude that cl_{n+1} = (n + 1) · (n + 1)! + (n + 1)! − 1 = (n + 2)! − 1, as desired.

While Theorem 3 enumerates the relevant circular array tilings, we can also find a bijection between the tilings counted by cl_{n} and the permutations of n + 1 that are not the identity permutation. Consider a tiling where cell n and cell 1 are covered by different tiles. Since this tiling is equivalent to a tiling counted by rb_{n}, then via bijection f in the proof of Theorem 1 it can be mapped to a unique permutation of length n + 1 where n + 1 is not last. On the other hand, if cells n and 1 are covered by the same tile, suppose that there are i cells covered by this tile to the left of 1. Delete these i cells and shrink this tile by size i to obtain a tiling counted by cl_{n−i} where cells 1 and n − i are covered by different tiles. We can find the unique permutation of length n + 1 − i corresponding to this tiling via bijection f and then append the digits n − i + 2, …, n + 1 in order to complete the non-identity permutation of length n + 1.

Theorem 4. Let cb_{n} be the number of tilings of an n-cell circular array where the number of possible colors of a tile t is determined by the biggest cell t covers. Then

cb_{n} = n ∑_{k=1}^{n} \frac{n!}{k!}. (OEIS \underline{A345887})

Proof. Let rb_{k}^{i} be the number of tilings of an k × 1 rectangle where the number of possible colors of a tile t is determined by the biggest cell t covers, starting at position i+1. With this notation, Theorem 1 addresses the case where i = 0. When i > 0, we understand positions 1, …, i to be all covered by the first tile, whose size is at least i + 1.

Consider a tiling counted by cb_{n}. Then the tile covering position n covers i positions to the right of n where i ≥ 0. If i = 0, by cutting the circular array between cells n and 1, we obtain one of the rb_{n} = n · n! tilings of a rectangular array. Alternatively, if i > 0, we can remove the positions 1, 2, …, i from the tiling without changing the number of tilings. There are exactly rb_{n−i}^{i} such tilings. These can be counted in a manner similar to Theorem 1, where the ordering of 1, …, i + 1 in the corresponding permutation does not matter, and thus rb_{n−i}^{i} = n\frac{n!}{(i+1)!}. We sum over all relevant values of i to determine

cb_{n} = ∑_{i=0}^{n−1} rb_{n−i}^{i} = ∑_{i=0}^{n−1} n\frac{n!}{(i + 1)!} = n ∑_{k=1}^{n} \frac{n!}{k!}.

While cb_{n} is new to OEIS, \frac{cb_{n}}{n} is given by \underline{A002627}, which is known to be the number of permutations of proper subsets of a set of n objects. We can see this by modifying bijection f from the proof of Theorem 1. Consider a tiling and focus on the tile covering cell n. Suppose this tile covers i cells to the right of n. Necessarily, 0 ≤ i ≤ n − 1. Delete cells

2 4 5  2 4 5

Figure 4: A 6-cell biggest-color circular array tiling and its corresponding partial rectangular board tiling, which map to the ordered arrangement 316 of the subset {1, 3, 6}.

1, …, i from the tiling (and shrink this tile by i cells) to obtain a tiling of cells i + 1, …, n of the circular array. Now, to generate a (partial) permutation, begin with i + 1 blanks, and then proceed similarly to bijection f, reading tiles from left to right. When a tile has color c and covers cells j, …, j + a, append the digits j − i, …, j + a − i − 1 to the end of the partial permutation, and then place digit j + a − i in the (c + 1)st position from the end. This produces a permutation consisting of i + 1 blanks along with the digits 1, …, n − i. Since there are always n choices for the color of the last tile, there are always n possible positions of the digit n + 1 relative to the other digits in any underlying partial permutation. If digit n + 1 is removed, then we produce all ways to generate a permutation of i + 1 blanks and n − i − 1 digits. Now, if there is a digit in position p, consider p to be in our chosen subset, and if there is a blank in position p, p is not in the subset. The digits 1, …, n − i in the non-blank positions produce a permutation of our chosen elements. Since there is always at least one blank, we always have a proper (possibly empty) subset of {1, …, n} that has been chosen.

As an example, consider the coloring of a 6-cell circular array shown in the left of Figure 4. In this diagram, the tile covering cell 6 also covers cells 1 and 2 so, i = 2, and if we ignore the first two cells, we have a rectangular tiling of cells 3, 4, 5, and 6 of the form shown on the right of Figure 4. Since i = 2, we begin with three blanks. Now, the tile covering cell 3 is of size 1 and has color 2, so we place the digit 1 in the third position from the right to obtain 1 . Next, the tile covering cell 4 is of size 1 and has color 4, so we place the digit 2 in the fifth position from the right to obtain 2 1 . Finally, the tile covering cells 5 and 6 has size 2 and color 5, so we place 3 at the end of the partial permutation and then place 4 in the sixth position from the end to obtain 2 4 1 3. Disregarding the 4 gives 2 1 3. There are digits in positions 1, 3, and 6, and so this corresponds to a permutation of the subset {1, 3, 6}. Since the 1 is in position 3, the 3 comes first; since the 2 is in position 1, the 1 comes second, and finally 6 comes last. This tiling corresponds to the ordered arrangement 316.

Theorem 5. Let cs_{n} be the number of tilings of an n-cell circular array where the number of possible colors of a tile t is determined by the smallest cell t covers. Then

cs_{n} = ∑_{k=2}^{n+1} \frac{k!}{2}. (OEIS \underline{A345889})

Proof. Consider a tiling counted by cs_{n}. Either the tile covering position n also covers position 1 or it does not. For the first case, since the tile covering position n also covers position 1, we can remove position n from the circular tiling and shrink the tile by size 1 to

obtain one of cs_{n−1} = ∑_{k=2}^{n} \frac{k!}{2} possible colored tilings of an (n − 1)-cell circular array. For the

later case, since the tile covering array position n does not cover position 1, by cutting the array between cells n and 1, we obtain one of the rs_{n} = \frac{(n+1)!}{2} colored tilings of Theorem 2.

Since these cases are mutually exclusive, we conclude that cs_{n} = ∑_{k=2}^{n} \frac{k!}{2} + \frac{(n + 1)!}{2} = ∑_{k=2}^{n+1} \frac{k!}{2}

as desired.

While cs_{n} is new to OEIS, cs_{n} − cs_{n−1} is given by \underline{A001710}, which we saw in Theorem 2 as the number of even permutations of size n + 1. In other words, cs_{n} corresponds to the number of even permutations of size at most n + 1 (and at least 2). We can see this as a corollary to the proof of Theorem 5 since, if we consider the tile covering cell 1 and delete the i cells left of 1 (0 ≤ i ≤ n − 1) that are covered with this tile, we obtain a tiling of an n − i cell circular array where different tiles cover cell 1 and cell n − i. In this situation, the tiling is equivalent via bijection g to a tiling counted by rs_{n−i}, which we know to be in bijection with the even permutations of size n−i+1, so after running over all possible values of i, we have tilings in correspondence with all even permutations of lengths between 2 and n + 1 inclusive.

4 Acknowledgments

We are thankful to an anonymous referee whose suggestions improved the clarity of this paper.

References

[1] A. Benjamin and J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, MAA Press, 2003.

[2] G. Dresden and Y. Xiao, Weighted sums of Fibonacci and Lucas numbers through colorful tilings, preprint, 2021. To appear in Fibonacci Quart.. Available at https://dresden.

   academic.wlu.edu/files/2021/01/WeightedSumsWebsite.pdf.

[3] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2021.

2010 Mathematics Subject Classification: Primary 05B45, Secondary 05A05, 05A10. Keywords: tiling, rectangle, inversion, permutation.

(Concerned with sequences \underline{A000079}, \underline{A000225}, \underline{A001710}, \underline{A002627}, \underline{A033312}, \underline{A094258}, \underline{A345887}, and \underline{A345889}.)

Received June 29 2021; revised version received November 9 2021. Published in Journal of Integer Sequences, November 26 2021.

Return to Journal of Integer Sequences home page.