Restricted Tilings and Bijections

Barry Balof Department of Mathematics Whitman College 345 Boyer Avenue Walla Walla, WA 99362 USA

               balofba@whitman.edu

Abstract

A classic problem in elementary combinatorics asks in how many ways one can tile a 1 × n chessboard using 1 × 1 and 1 × 2 squares. The number of such tilings is the nth Fibonacci number. In a 2010 paper, Grimaldi generalized this problem by allowing for 1 × 1 tiles to have one of w types and 1 × 2 tiles to have one of t types and found that the solutions, in w and t, satisfied many of the same properties as do the Fibonacci and Lucas numbers. In this paper, we present a variant of this generalization. Namely, we require that no two adjacent 1 × 1 tiles be of the same type. This restriction leads to interesting combinatorial connections with coordination sequences and problems in enumerative set theory. We explore these connections, as well as some formulas for generating functions for the numbers of these types of tilings.

1 The Basic Generalization

In a 2010 paper, Ralph Grimaldi [3] presented the following generalized tiling problem:

In how many ways can one tile a 1 × n chessboard using 1 × 1 tiles that come in w types and 1 × 2 tiles that come in t types?

Grimaldi found a second order recurrence relation, then solved that relation to come up with a set of numbers that satisfied many of the same properties as do the Fibonacci numbers and the Lucas numbers. In this paper, we consider the following variant:

In how many ways can one tile a 1 × n chessboard using 1 × 1 tiles that come in w types and 1 × 2 tiles that come in t types, such that no two adjacent 1 × 1 tiles are of the same type?

With this property, we are insisting that 1 × 1 tiles ‘behave’ like 1 × 1 tiles. That is, they appear as single ‘distinguishable’ tiles in the actual tilings. If, for example, the tiles come in different colors, then we can assign one set of w colors to the 1 × 1 tiles and a different set of t colors to the 1 × 2 tiles. Then, it would not be the case in any of our permissible tilings that two 1 × 1 tiles would be mistaken for a 1 × 2 tile. In the following, we will refer to tilings that follow this rule as restricted tilings.

2 Recurrence Relations

Grimaldi gives the following second-order linear recurrence relation for a_{n}, the number of tilings with no restrictions:

Theorem 1 (Grimaldi 2010). The number of tilings of a 1 × n chessboard with 1 × 1 tiles in w types and 1 × 2 tiles in t types is a_{n}, where a_{0} = 1, a_{1} = w and

a_{n} = wa_{n−1} + ta_{n−2} (n ≥ 2).

Proof. There is one way to tile an empty board and w choices for a tile to cover a 1 × 1 board. To construct a tiling of a 1 × n board, one can either append a 1 × 1 tile to an existing tiling of a 1 × (n − 1) board (in w ways), or a 1 × 2 tile to an existing tiling of a 1 × (n − 2) board (in t ways).

This second order recurrence relation leads to a quadratic characteristic equation whose roots satisfy some interesting combinatorial properties similar to those satisfied by the Fibonacci and Lucas numbers.

The linear recurrence relation for the number of restricted tilings also has a straightforward and constructive proof, but is of third-order:

Theorem 2. The number of restricted tilings of a 1 × n chessboard with 1 × 1 tiles in w types and 1 × 2 tiles in t types is a_{n}^{∗} where a_{−1}^{∗} = 0, a_{0}^{∗} = 1, a_{1}^{∗} = w and

a_{n}^{∗} = (w − 1)a_{n−1}^{∗} + ta_{n−2}^{∗} + ta_{n−3}^{∗} (n ≥ 2).

Proof. We assign a_{−1}^{∗} = 0 by convention, and as before, there are 1 and w ways to tile an empty board and a 1 × 1 board, respectively. We have three possibilities to consider for the tiling of a 1 × n chessboard:

Case (1) Our tiling ends in a 1 × 2 tile.

Case (2) Our tiling ends in exactly one 1 × 1 tile.

Case (3) Our tiling ends in two or more 1 × 1 tiles.

Let a_{n,1}^{∗} (respectively, a_{n,2}^{∗}) denote the number of tilings of a 1 × n board that end with a 1 × 1 (1 × 2) tile. Then a_{n}^{∗} = a_{n,1}^{∗} + a_{n,2}^{∗}. We count the tilings by cases.

• The tilings in case 1 are precisely those counted by a_{n,2}^{∗}. We generate such a tiling by appending any of t types of 1 × 2 tile (without restrictions) to any tiling of a 1 × (n − 2) board. Thus, we have a_{n,2}^{∗} = ta_{n−2}^{∗} tilings in case 1.

• The tilings in case 2 are generated by appending any of t types of 1 × 2 tile followed by any of w types of 1 × 1 tile (again, with no restrictions) to the end of any tiling of a 1 × (n − 3) board. Thus, we have wta_{n−3}^{∗} tiling of boards in case 2.

• If our tiling ends with two or more 1 × 1 tiles (case 3), we can generate it by appending a 1 × 1 tile to a 1 × (n − 1) tiling that itself ends in a 1 × 1 tile. This can be done in (w − 1) ways for any such tiling, as the types of the last two tiles must be distinct. Thus, the tilings in case 3 are counted by (w − 1)a_{n−1,1}^{∗}. By our earlier count of all of a_{n}^{∗}, we have that

(w − 1)a_{n−1,1}^{∗} = (w − 1)[a_{n−1}^{∗} − a_{n−1,2}^{∗}] = (w − 1)a_{n−1}^{∗} − (w − 1)ta_{n−3}^{∗}

We now combine the three cases to get our recursion formula for a_{n}^{∗}.

a_{n}^{∗} = ta_{n−2}^{∗} + wta_{n−3}^{∗} + (w − 1)a_{n−1}^{∗} − (w − 1)ta_{n−3}^{∗}
= (w − 1)a_{n−1}^{∗} + ta_{n−2}^{∗} + (wt − (w − 1)t)a_{n−3}^{∗}
= (w − 1)a_{n−1}^{∗} + ta_{n−2}^{∗} + ta_{n−3}^{∗}.

Where necessary, we will use the notation a_{n}^{∗}(w, t) in place of a_{n}^{∗}, as we now have that for each n, a_{n}^{∗} is a polynomial in w and t. This notation will prove useful later when we examine some specific cases, especially those where we need a value for w or for t but not for both.

We pause here to note a similarity between our recursion formula and one for a non-restricted tiling involving squares in (w − 1) types, dominos in t types, and triominos (1 × 3 tiles) in t types. Though the recursion portions of the formulas are the same, the initial conditions are different (the number of tilings on a 1 × 1 board in the restricted case is w, whereas the number in the non-restricted case is w − 1, which leads to different numbers of these tilings for different sized boards). Benjamin and Quinn [2] interpret this recursion with these initial conditions in terms of ‘phased’ tilings (where an initial square has one of w phases and all other squares coming in w − 1 types, while dominos and triominos each coming in t types).

The recursion proven in Theorem 2 gives rise to the following cubic characteristic equation:

r^{3} − (w − 1)r^{2} − tr − t = 0

which gives rise to three roots, α, β and γ which satisfy the following equations:

α + β + γ = (w − 1)
αβ + αγ + βγ = −t
αβγ = t,

which, when combined, yield:

α + β + γ + αβ + αγ + βγ + αβγ = w − 1
(α + 1)(β + 1)(γ + 1) − 1 = w − 1,

or,

(α + 1)(β + 1)(γ + 1) = w.

Though we can use computational software to lay hands on explicit formulas for α, β and γ, we may be better served at this point to explore the combinatorics of some specific cases.

3 Some Specific Values of t and w

When we allow ourselves only one type of 1 × 1 tile, the number of tilings is quite restricted. Notice that we are not allowed consecutive 1 × 1 tiles in any tilings. To form new tilings from existing tilings, we must append either a 1×2 tile to any tiling of a 1 × (n − 2) board, or append a 1 × 2 tile followed by a 1 × 1 tile to any tiling of a 1 × (n − 3) board. These constructions play out in the recursion formula.

Example 3. For w = 1 and t = 1, we have a_{0}^{∗} = a_{1}^{∗} = a_{2}^{∗} = 1, and, for n ≥ 3

a_{n}^{∗} = a_{n−2}^{∗} + a_{n−3}^{∗}.

The sequence of values for a_{n}^{∗} in this case is the Padovan sequence \underline{A000931}

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28 …

.

We find that the term a_{n}^{∗} counts the number of ordered partitions of (n + 4) into parts that are congruent to 2 modulo 3. (For example, a_{6}^{∗} = 4, with the partitions of 10 being 8+2, 2+8, 5+5, and 2+2+2+2+2.) The term a_{n}^{∗} also counts the number of ordered partitions of (n + 5) into parts that are odd and greater than 3. (For example, again, a_{6}^{∗} = 4, with the partitions of 11 being 5+3+3, 3+5+3, 3+3+5, and 11.) The reader is invited to come up with the appropriate bijections for these cases. Our characteristic equation for this recurrence is r^{3} − r − 1 = 0. It has, as its roots, the so called plastic constant

P = \frac{\sqrt[3]{108 + 12 \sqrt{69}}}{6} + \frac{2}{\sqrt[3]{108 + 12 \sqrt{69}}} ≈ 1.324717958,

as well as the conjugate imaginary roots

\frac{−1}{12} ( \sqrt[3]{108+12 \sqrt{69}} − _{\frac{1}{3 \sqrt{108+12 \sqrt{69}}}} )± \frac{i\sqrt{3}}{2} ( ^{\frac{3 \sqrt{108+12 \sqrt{69}}}{6}} − _{\frac{2}{3 \sqrt{108+12 \sqrt{69}}}} ).

The plastic constant, together with the Golden Ratio (ϕ = \frac{1+\sqrt{5}}{2}) are the only morphic numbers [1].

When we have two types of 1 × 1 tile and one type of 1 × 2 tile, our recursion is of another semi-famous sequence:

Example 4. For w = 2 and t = 1, we have a_{0}^{∗} = 1, a_{1}^{∗} = 2, a_{2}^{∗} = 3, and, for n ≥ 3,

a_{n}^{∗} = a_{n−1}^{∗} + a_{n−2}^{∗} + a_{n−3}^{∗}.

The sequence of values in this case is a Tribonacci sequence \underline{A001590}:

1, 2, 3, 6, 11, 20, 37, 68, ….

4 The Specific Value w = 2

When we allow for two types of 1×1 tile, and an arbitrary number t of types of 1×2 tiles, we have the following recursion:

Example 5. For w = 2 and t arbitrary, we have a_{0}^{∗} = 1, a_{1}^{∗} = 2, a_{2}^{∗} = 2 + t, and, for n ≥ 3,

a_{n}^{∗} = a_{n−1}^{∗} + ta_{n−2}^{∗} + ta_{n−3}^{∗}.

Following this recursion formula, we get the following polynomials P_{n}(t), which each give the number of restricted tilings of a 1 × n chessboard where the 1 × 1 tiles come in two types. (Note: P_{n}(t) = a_{n}^{∗}(2, t), that is, a_{n}^{∗} evaluated when w = 2.)

\begin{matrix}P_{0}(t) & 1 \\ P_{1}(t) & 2 \\ P_{2}(t) & 2 + t \\ P_{3}(t) & 2 + 4t \\ P_{4}(t) & 2 + 8t + t^{2} \\ P_{5}(t) & 2 + 12t + 6t^{2} \\ P_{6}(t) & 2 + 16t + 18t^{2} + t^{3} \\ P_{7}(t) & 2 + 20t + 38t^{2} + 8t^{3} \\ P_{8}(t) & 2 + 24t + 66t^{2} + 32t^{3} + t^{4} \\ P_{9}(t) & 2 + 28t + 102t^{2} + 88t^{3} + 10t^{4} \end{matrix}

The patterns in the coefficients on t^{k} merit combinatorial explanations. The constant term in each polynomial after the trivial case is 2, owing to the fact that a 1 × n chessboard tiled entirely with 1 × 1 squares must necessarily alternate types of square. Thus, when one chooses the type of the first square (in 2 ways), the remainder of the tiling is determined.

We notice that the coefficients on t in each of the polynomials are all multiples of 4 (with the exception of P_{2}(t)), a fact which has a straightforward counting justification:

Proposition 6. The coefficient of t in P_{n}(t), which counts the number of tilings of a 1 × n board that use exactly one 1 × 2 tile, is 1 for n = 2 and 4(n − 2) for n ≥ 3.

Proof. The case for n = 2 is trivial (there is only one tiling, up to tile types, of a 1 × 2 board with one 1 × 2 tile). For n ≥ 3, we look for possible placements of the one 1 × 2 tile. It may be on either end, in which case there is one string of 1 × 1 tiles. There are two such strings (as the 1×1 tiles must necessarily alternate), giving a total of 4 tilings in which the 1 × 2 tile is on either end. If that tile is not on either end, there are n − 3 possible placements for it (the left-most square of the 1 × 2 tile may not be in the first square or either of the last two squares). In these cases, there are two strings of 1 × 1 tiles which come in two types each, for a total of 4(n − 3) tilings where our 1 × 2 tile is not on an end. Our total count of tilings is thus 4 + 4(n − 3) = 4(n − 2).

The sequence of coefficients on t^{2} is a little bit less straightforward to deal with directly. A count similar to the one given above (where one counts possibilities for the two tiles to be together or separate, and on the ends or not) will justify the following formula.

Proposition 7. The coefficient of t^{2} in P_{n}(t), which counts the number of tilings that use exactly two 1 × 2 tiles, is 1 for n = 4 and

6 + 12(n − 5) + 4(n − 5)(n − 6) = 4(n − 4)^{2} + 2

for n ≥ 5.

The sequence of terms

1, 6, 18, 38, 66, 102 …

appears as \underline{A005899} in [7], where it appears as the coordination sequence for the cubic lattice. A coordination sequence in an atomic framework is a sequence in which the kth term counts the number of atoms in the kth shell that are bonded to atoms in the (k − 1)st shell [5]. As mathematicians, we can view this in terms of distances and metrics.

Definition 8. In a coordination sequence {a_{i}}_{i=0}^{∞}, a_{k} counts the number of lattice points in a fixed number of dimensions that are at a distance k from the origin under the taxicab metric (i.e., the number of lattice points whose coordinates, in absolute value, sum to k).

We now present a natural bijection between our tilings and these lattice points, which we generalize:

Proposition 9. The coefficient on t^{k} in the polynomial P_{n}(t) is the (n − 2k)th term in the coordination sequence for the cubic^{1} lattice in (k + 1)-dimensional space.

Proof. We give our proof by establishing a bijection between

• Restricted tilings of a 1 × n chessboard with k 1 × 2 tiles and (n − 2k) 1 × 1 tiles in two types, and

• Lattice points in (k + 1)-dimensional space that are distance n − 2k from the origin under the taxicab metric.

Start with a tiling of the 1×n chessboard. This tiling has k 1×2 tiles, thus n−2k 1 × 1 tiles. The k 1 × 2 tiles break the remaining tiles into k + 1 (possibly empty) strings of consecutive 1 × 1 tiles that alternate types of tile, and whose total length must be n − 2k. We assign this tiling to the point (a_{1}, a_{2}, …, a_{k}, a_{k+1}), where |a_{i}| is the length of the ith string of 1 × 1 tiles, and a_{i} is positive or negative depending on whether the string starts with a tile of type 1 or of type 2, respectively. Note that an empty string does not start with either type of tile, nor do we need to choose a sign for the coordinate (0) in that case. The map is well-defined in that any given tiling leads to a unique lattice point.

If we start with the lattice point (b_{1}, b_{2}, …, b_{k}, b_{k+1}), where ∑_{i} |b_{i}| = (n−2k), we construct a tiling consisting of (k +1) strings of alternating 1×1 tiles. The ith string is of length |b_{i}|, and starts with a tile of type 1 (type 2) if b_{i} is positive (negative). Each of these strings are separated by a 1 × 2 tile (of which there are k in all), thus giving a restricted tiling of a 1 × n chessboard with k 1 × 2 tiles and (n − 2k) 1 × 1 tiles in two types.

We have thus generalized our result for coordination sequences to all coefficients on the P_{n}(t), that is:

• The coefficients on t^{3} are the coordination sequence for the 4-dimensional cubic lattice: 1, 8, 32, 88, 192, 360, …

• The coefficients on t^{4} are the coordination sequence for the 5-dimensional cubic lattice: 1, 10, 50, 170, 450, 1002^{2}, … • The coefficients on t^{5} are the coordination sequence for the 6-dimensional cubic

1The term ‘cubic’ here refers to the arrangement of the points within the lattice, and applies to all dimensions, including those other than 3.

2Curiously, while all other terms are multiples of 10, every fifth term of this sequence is of the form 1000m + 2.

lattice: 1, 12, 72, 292, 912, 2364, …

We give a few examples to illustrate our bijection. In the following, we use a and b to denote 1 × 1 tiles of the first and second type, and a 2 to denote a 1 × 2 tile. Each tiling is of a 1 × 14 board.

ababa2aba2ab ↔ (5, 3, 2)
ababa2bab2ab ↔ (5, −3, 2)
bab2bab2a2b ↔ (−3, −3, 1, −1)
a22bab2a2b ↔ (1, 0, −3, 1, −1)

5 Tilings and Subsets

In the description of \underline{A005899}, we have the following explanation of the aforementioned sequence of coefficients on t^{2} in the polynomials P_{n}(t) due to Milan Janjic [4].

If X is an n-set and Y_{i} (i=1,2,3) are mutually disjoint 2-subsets of X then a_{n−5}^{∗} is equal to the number of 5-subsets of X intersecting each Y_{i} (i=1,2,3).

We will establish, and generalize, a natural bijection between these subsets and our tilings, through the following investigation. Suppose our set X consists of the first n integers, our sets Y_{i} are the subsets {1, 2}, {3, 4} and {5, 6}. Suppose also that we have a tiling of a 1 × (n − 1) board with two 1 × 2 tiles and (n − 5) 1 × 1 tiles in two types, with no two adjacent 1 × 1 tiles of the same type. Our two 1 × 2 tiles split the remaining (n − 5) tiles into three (possibly empty) strings of 1 × 1 tiles. We wish to use the tiling to construct a subset of size 5 which intersects each of the sets Y_{i}, which we do as follows:

• If the ith string begins with a 1 × 1 tile of type a, we take the first element in Y_{i}.

• If the ith string begins with a 1 × 1 tile of type b, we take the second element in Y_{i}.

• If the ith string is empty, we take both elements in Y_{i}.

For any tiling with at least one 1 × 1 tile, we have either zero, one, or two empty substrings of 1 × 1 tiles, which means that we have taken either three, four, or five elements, respectively, from the Y_{i} into our subset. If we have all five elements (and hence, only one non-empty string), we’re done. Otherwise, our non-zero strings give an ordered partition of n − 5 into two or three non-zero parts. We choose our first elements using the method above. Our n set has n − 6 elements which are not part of any of the Y_{i}. We must choose some of these elements to complete our subset of five elements. This can be done in a natural way. If we think of our n − 5 tiles as ‘stars’, then there are n − 6 places between consecutive stars to place ‘bars’. Our placement of these bars will determine which elements from the last n − 6 elements in X will complete our subset. Note that

• If we have one empty string of 1 × 1 tiles, then the Y_{i} have contributed 4 elements to our subset. Thus, we need one element to complete our subset. Our two non-empty strings divide the (n − 5) 1 × 1 tiles into two parts, which requires 1 ‘bar’. We take the position of that bar as our extra element.

• If we have no empty strings of 1 × 1 tiles (hence, three elements from the Y_{i}), we need two elements to complete our subset. Our three non-empty strings divide the (n − 5) 1 × 1 tiles into three parts, which requires 2 ‘bars’. We take the positions of these bars as our extra elements.

We illustrate our bijection with a few examples. In the following, as above, we use a and b to denote 1 × 1 tiles of the first and second parts, respectively, and a 2 to denote a 1 × 2 tile. Our tilings are of a 1 × 11 board, which we are placing in correspondence with 5-subsets of the set X = {1, 2, … 12}

22abababa ↔ {1, 2, 3, 4, 5}
22bababab ↔ {1, 2, 3, 4, 6}
ab2babab2 ↔ {1, 4, 5, 6, 8}
aba22baba ↔ {1, 3, 4, 6, 9}
baba2a2ab ↔ {2, 3, 5, 10, 11}

This construction of the correspondence between certain subsets of a ground set and our restricted tilings of a 1 × n chessboard has a natural generalization, which we give here.

Proposition 10. There is a bijection between the following sets:

• The set of tilings of a 1 × (j + 2k) chessboard using j 1 × 1 tiles in two types and k 1 × 2 tiles, such that no two consecutive 1 × 1 tiles are of the same type.

• The set of 2k + 1-subsets of a (j + 2k + 1) set X, which intersect each of k + 1 mutually disjoint 2-subsets Y_{i} (i = 1, 2, …, k, k + 1).

Proof. We generalize our construction from above. The k 1×2 tiles break our j 1×1 tiles into k + 1 (possibly empty) strings of tiles, which must necessarily alternate. As before, we use our strings to build our subset of the set X = {1, 2, 3, …, 2k + j + 1}. We first choose those elements from our sets Y_{i} = {2i − 1, 2i} (that is, as before, Y_{1} = {1, 2}, Y_{2} = {3, 4}, etc.).

• If the ith string begins with a 1 × 1 tile of the first type, we take the first element in Y_{i}.

• If the ith string begins with a 1 × 1 tile of the second type, we take the second element in Y_{i}.

• If the ith string is empty, we take both elements in Y_{i}.

This process gives us at least k + 1 of our 2k + 1 elements for our subset. For any tiling with at least one 1 × 1 tile, we have anywhere between 0 and k empty strings. As each empty string gives us one extra element from the Y_{i}, we need to choose between k and 0 more elements for our subset from the j − 1 elements in X but not in any Y_{i}. Suppose that we have k − l empty strings, and thus need l elements to complete our subset. Then we have l + 1 non-empty strings in which to partition the j 1 × 1 tiles. If, as above, we view the j 1 × 1 tiles as ‘stars’, we have j − 1 spaces between the tiles in to place ‘bars.’ Thus we assign each space to one of our elements in X but not in any Y_{i}. Creating a partition into l + 1 non-empty strings will require choosing l positions in which to place our ‘bars’. We take the l elements corresponding to those positions to complete our subset.

Given a subset with an odd number of elements (which meets the intersection conditions) and the size of the ground set from which it was taken, we can reconstruct an appropriate tiling. We do this by working backwards through the algorithm used to create the subset. If our subset was of size 2s + 1 and the ground set of size t, our tiling will be of a 1 × (t − 1) board and use s 1 × 2 tiles (and would have to intersect each of the first (s + 1) 2-element subsets.

We present a few examples below, using our notation from above.

Example 11. abab2bab2ab2bab2

For this example, we have four 1 × 2 tiles in a restricted tiling of a 1 × 20 board. Thus, our ground set is X = {1, 2, … 21} and there are five sets Y_{i}, from which we seek a 9-element subset. Based on the types of 1 × 1 tiles, we take the elements 1, 4, 5, 8, 9, 10 (the last two coming from the empty string at the end of the tiling). We need three more elements, and we see that the 1 × 1 tiles are parted in the fourth, seventh, and ninth possible positions. Thus, we add elements 14, 17 and 19 to complete our subset:

abab2bab2ab2bab2 ↔ {1, 4, 5, 8, 9, 10, 14, 17, 19}

Example 12. babab2a2ba2ba

For this example, we have three 1 × 2 tiles in a restricted tiling of a 1 × 16 board. Thus, our ground set is X = {1, 2, …, 17} and there are four sets Y_{i}, from which we seek a seven element subset. Based on the types on 1 × 1 tiles, we take the elements 2, 3, 6 and 8 into our subset. We need three more elements, based on the fact that we have four nonempty strings of 1×1 tiles. These tiles are parted in the fifth, sixth, and eighth possible places. We take the corresponding elements from those not in the Y_{i}, namely 13, 14 and 16, which completes our subset:

babab2a2ba2ba ↔ {2, 3, 6, 8, 13, 14, 16}

Given a subset and the size of the ground set from which it was taken, we can determine a unique restricted tiling, as shown in the next example.

Example 13. {1, 3, 4, 6, 7, 10, 12} as a 7-element subset of {1, 2, …, 15}.

Based on the sizes of our sets, we are seeking a restricted tiling of a 1×(15−1) = 1 × 14 board using \frac{7−1}{2}, or three 1 × 2 tiles and eight 1 × 1 tiles. It is important that we first check that we have a valid subset for our bijection, namely one that intersects each of the sets {1, 2}, {3, 4} {5, 6}, and {7, 8} (which it does).

We next look to our elements outside of these sets, namely 10 and 12. These tell us that there are three nonempty strings (of the four total) of 1 × 1 tiles totaling eight tiles in length, and they are divided in the second and fourth possible place (as 10 and 12 are the second and fourth elements beyond our designated subsets). Thus, our nonempty strings are of lengths two, two, and four. Based on the initial elements of the subset (1,3,4, 6, and 7), we have that the four strings are, in order, of the first type, empty, of the second type, and of the first type. Thus, we have our tiling corresponding to the subset:

{1, 3, 4, 6, 7, 10, 12} ↔ ab22ba2abab

6 Generating Functions for Sequences of Coefficients

In this section, we extend our analysis of the sequences of coefficients on the polynomials P_{n}(t) to values of w other than 2. To that end, we will generalize our polynomials from the previous section. Recall that a_{n}^{∗}, which counts the number of restricted tilings on a 1×n board, is a polynomial in w and t. As we wish to compute for specific values of w, we will let P_{w_{0},n}(t) = a_{n}^{∗}(w_{0}, t) (that is, a_{n}^{∗} evaluated at the value w = w_{0}). Below, we rewrite our polynomials from above using our amended notation, as well as presenting the next three values for w.

\begin{matrix}P_{2,0}(t) & 1 & P_{3,0}(t) & 1 \\ P_{2,1}(t) & 2 & P_{3,1}(t) & 3 \\ P_{2,2}(t) & 2+t & P_{3,2}(t) & 6+t \\ P_{2,3}(t) & 2+4t & P_{3,3}(t) & 12+6t \\ P_{2,4}(t) & 2+8t+t^{2} & P_{3,4}(t) & 24+21t+t^{2} \\ P_{2,5}(t) & 2+12t+6t^{2} & P_{3,5}(t) & 48+60t+9t^{2} \\ P_{2,6}(t) & 2+16t+18t^{2}+t^{3} & P_{3,6}(t) & 96+156t+45t^{2}+t^{3} \\ P_{2,7}(t) & 2+20t+38t^{2}+8t^{3} & P_{3,7}(t) & 192+384t+171t^{2}+12t^{3} \\ P_{2,8}(t) & 2+24t+66t^{2}+32t^{3}+t^{4} & P_{3,8}(t) & 384+912t+558t^{2}+78t^{3}+t^{4} \\ P_{2,9}(t) & 2+28t+102t^{2}+88t^{3}+10t^{4} & P_{3,9}(t) & 768+2112t+1656t^{2}+372t^{3}+15t^{4} \end{matrix}

\begin{matrix}P_{4,0}(t) & 1 & P_{5,0}(t) & 1 \\ P_{4,1}(t) & 4 & P_{5,1}(t) & 5 \\ P_{4,2}(t) & 12+t & P_{5,2}(t) & 20+t \\ P_{4,3}(t) & 36+8t & P_{5,3}(t) & 80+10t \\ P_{4,4}(t) & 108+40t+t^{2} & P_{5,4}(t) & 320+65t+t^{2} \\ P_{4,5}(t) & 324+168t+12t^{2} & P_{5,5}(t) & 1280+360t+15t^{2} \\ P_{4,6}(t) & 972+648t+84t^{2}+t^{3} & P_{5,6}(t) & 5120+1840t+135t^{2}+t^{3} \\ P_{4,7}(t) & 2916+2376t+460t^{2}+16t^{3} & P_{5,7}(t) & 20480+8960t+965t^{2}+20t^{3} \\ P_{4,8}(t) & 8748+8424t+2196t^{2}+144t^{3}+t^{4} & P_{5,8}(t) & 81920+42240+6060t^{2}+230t^{3}+t^{4} \end{matrix}

We now give a generating function relation involving our restricted tilings which will generate the coefficients on the above polynomials in a natural fashion.

Proposition 14. If c_{j}(w) is the number of restricted tilings (up to domino types) of a 1 × (j + 2k) board that use exactly j 1 × 1 tiles in w types, then

(\frac{1 + x}{1 − (w − 1)x})^{k+1} = ∑ c_{j}(w)x^{j}

That is to say, the sequence of coefficients c_{j} is the sequence of positive coefficients on t^{k} in the polynomials P_{w,n}(t).

Proof. We look at an algebraic construction of the given function. We note first that

\frac{1}{1 − (w − 1)x} = 1 + (w − 1)x + (w − 1)^{2}x^{2} + (w − 1)^{3}x^{3} …

as an ordinary geometric series. Continuing with our construction gives

\frac{1 + x}{1 − (w − 1)x} = (1 + x)(1 + (w − 1)x + (w − 1)^{2}x^{2} + (w − 1)^{3}x^{3} …

= 1 + (w − 1)x + (w − 1)^{2}x^{2} + (w − 1)^{3}x^{3} …
+ x + (w − 1)x^{2} + (w − 1)^{2}x^{3} + (w − 1)^{3}x^{4} …

= 1 + (w − 1 + 1)x + ((w − 1)^{2} + (w − 1))x^{2} + ((w − 1)^{3} + (w − 1)^{2})x^{3} + … = 1 + wx + (w − 1)wx^{2} + (w − 1)^{2}wx^{3} + (w − 1)^{3}wx^{4} + …

giving our overall function:

(\frac{1 + x}{1 − (w − 1)x})^{k+1} = (1 + wx + (w − 1)wx^{2} + (w − 1)^{2}wx^{3} + (w − 1)^{3}wx^{4} + …)^{k+1}.

We complete the proof by commenting on the form of the coefficients we’ve generated in terms of our tilings. Note that w(w − 1)^{r−1} is the number of restricted tilings of a string of r 1 × 1 tiles in w types.

Our coefficient c_{j} can thus be justified directly. We partition j into k+1 (possibly empty) ordered parts. Each non-zero part p_{i} will contribute w(w − 1)^{p_{i}−1} towards our coefficient. Thus, our coefficient c_{j} is given by

c_{j} = ∑_{i=1}^{k+1} ∑_{p_{1}+p_{2}+···+p_{i}=j} w(w − 1)^{p_{1}−1}w(w − 1)^{p_{2}−1} … w(w − 1)^{p_{i}−1}.

When we combine the ‘w’ and ‘(w − 1)’ terms in the summation, we find that we have one ‘w’ term for each non-zero part. We also have total of j ‘(w − 1)’ terms, less one (‘w − 1′) term for each non-zero part, simplifying our summation to

∑_{i=1}^{k+1} ∑_{p_{1}+p_{2}+···+p_{i}=j} w^{i}(w − 1)^{j−i}.

As there are \binom{j−1}{i−1} ways to write j as the ordered sum of i positive integers (see, for example, Chapter 13 of Wilson and van Lint [6]), the sum for our coefficient further simplifies to

∑_{i=1}^{k+1} \binom{j − 1}{i − 1}w^{i}(w − 1)^{j−i}.

We also get this count on our tilings, in the same vein as our earlier bijection in the case where w = 2. Our k 1 × 2 tiles break the 1 × (j + 2k) board into k + 1 (possibly empty) strings. Each non-empty string has one first tile (w choices) and possibly more tiles ((w − 1) choices each). Thus, we make our count based on i nonempty strings (which amounts to choosing i − 1 of j − 1 possible places to break up the 1 × 1 tiles, and sum over all i ≤ j).

c_{j} = ∑_{i=1}^{k+1} \binom{j − 1}{i − 1}w^{i}(w − 1)^{j−i}.

We note that the generating function works for all positive values of w, specifically in the case where w = 1, which we enumerated earlier in the specific case of t = 1. The polynomials P_{1,n}(t) = a_{n}^{∗}(1, t) (that is, a_{n}^{∗} evaluated at w = 1) form the following sequence:

1, 1, t, 2t, t + t^{2}, 3t^{2}, 3t^{2} + t^{3}, t^{2} + 4t^{3}, 6t^{3} + t^{4}, 4t^{3} + 5t^{4} …

which gives the following recognizable coefficients:

Powers of t Sequence of Coefficients
t  1,2,1
t^{2}  1,3,3,1
t^{3}  1,4,6,4,1
t^{4}  1,5,10,10,5,1
t^{5}  1,6,15,20,15,6,1

which makes sense given our generating function:

(\frac{1 + x}{1 − (1 − 1)x})^{k+1} = (1 + x)^{k+1}.

7 Future Directions

Many of the questions and properties posed by Grimaldi [3] extend naturally to our restricted tilings, namely that we can analyze the number of rises and levels in these tilings as functions of w and t. We can also look at circular restricted tilings, which may have as straightforward a recursion as do the linear restricted tilings. It may also be feasible to extend our subset example to those cases beyond w = 2.

8 Acknowledgements

The author would like to thank Dominc Klyve who provided useful feedback on an earlier draft of this article. The author would also like to thank the anonymous referee who provided numerous helpful comments that improved the exposition and streamlined the proof of Theorem 2.

References

[1] J. Aarts, R. Fokkink, and G. Kruijtzer, Morphic numbers, Nieuw Arch. Wisk. 5 (2001), 56–58.

[2] A. T. Benjamin and J. J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America, 2003.

[3] R. P. Grimaldi, Tilings, compositions, and generalizations, J. Integer Seq. 13, 2010, Article 10.6.5.

[4] Milan Janjic, Two enumerative functions, preprint, available at

   www.pmfbl.org/janjic/enumfor.pdf.

[5] R. W. Grosse-Kunstleve, G. O. Brunner, and N. J. A. Sloane, Algebraic description of coordination sequences and exact topological densities for zeolites, Acta Cryst. A52 (1996), 879–889. Available at

   http://www2.research.att.com/^{∼}njas/doc/ac96cs/.

[6] J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd edition, Cambridge University Press, 2001.

[7] N. J. A. Sloane, The Online Encyclopedia of Integer Sequences,

   http://oeis.org/.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05B45. Keywords: chessboard tiling, Fibonacci number, Tribonacci number, coordination sequence, combinatorial bijections.

(Concerned with sequences \underline{A000931}, \underline{A001590}, and \underline{A005899}.)

Received April 4 2011; revised versions received November 15 2011; December 29 2011. Published in Journal of Integer Sequences, December 30 2011.

Return to Journal of Integer Sequences home page.