Combinatorial Proofs of Some Formulas for Triangular Tilings

Mark Shattuck Department of Mathematics University of Tennessee Knoxville, TN 37996 USA

                 shattuck@math.utk.edu

Abstract

Bodeen et al. recently considered a new combinatorial tiling problem wherein a “strip” is tiled using triangles of four types and derived various identities for the resulting numbers. Some of the identities were proven combinatorially and others only algebraically, and the question of finding combinatorial interpretations of all of their results was posed. In this note, we provide the requested bijective proofs. To do so, we rephrase the question in an equivalent form in terms of tiling a strip with squares, trominos, and three types of dominos and form bijections or near bijections where the cardinality of various size families of sets gives the correct result.

1 Introduction

It is well known that the Fibonacci numbers given by F (n) = F (n − 1) + F (n − 2) if n ≥ 2 with F (0) = 0 and F (1) = 1 enumerate the tilings of a 2 × (n − 1) rectangular strip using vertical and horizontal dominos. This interpretation has been used to establish many interesting properties of the Fibonacci numbers (see [2]). The Pell numbers P (n) given by P (n) = 2P (n − 1) + P (n − 2) if n ≥ 2 with P (0) = 1 and P (1) = 2 enumerate the tilings of a 2 × n strip in which the vertically oriented dominos are allowed to come in two colors. This interpretation has led to combinatorial proofs of several Pell number identities (see, e.g., [1]).

A new problem of tiling a 2×n triangular strip using triangles was considered by Bodeen et al. [3] and various connections were made with the Fibonacci and Pell sequences. In particular, let Q(n) denote the number of tilings of a parallelogram having bases of length n and legs of length 2, where a leg makes an acute angle of 60^{∘} with a base, using four types of tiles: equilateral triangles having side length either 1 or 2 and oriented either upwards or downwards. Upon considering that tilings end in one of five possible different patterns, it was shown that the numbers Q(n) satisfy a third-order linear recurrence and are given by sequence \underline{A097076} in the On-line Encylopedia of Integer Sequences [4]. A number of relations for the Q(n) were obtained, among them the fact that Q(n − 1) + Q(n) is the n-th Pell number.

The following formulas were shown in Bodeen et al. [3] by algebraic methods using Binet formulas and the question of finding combinatorial proofs was raised.

Proposition 1. [3] The sequence Q(n) can be defined as Q(0) = Q(1) = 1 and for n ≥ 2,

Q(n) = 2Q(n − 1) + Q(n − 2) + (−1)^{n}.

Theorem 2. [3] Let Q(n) count the number of tilings of a 2 × n triangular strip. Then for m ≥ 1,

Q(4m) = (2Q(2m − 1) + 1)(2Q(2m) − 1),
Q(4m + 1) = (2Q(2m) − 1)^{2},
Q(4m + 2) = 2(Q(2m − 1) + Q(2m))(Q(2m) + Q(2m + 1)),
Q(4m + 3) = 2(Q(2m) + Q(2m + 1))^{2}.

It is the purpose of the current note to provide the requested combinatorial proofs of Proposition 1 and Theorem 2.

2 Combinatorial proofs

In this section, we provide bijective proofs of Proposition 1 and Theorem 2. By [3, Theorem 1], we have that the numbers Q(n) satisfy the recurrence

Q(n) = Q(n − 1) + 3Q(n − 2) + Q(n − 3),  n ≥ 3,  (1)

with Q(0) = Q(1) = 1 and Q(2) = 4. By the discussion in [2, Section 3.1], the tilings enumerated by Q(n) are in one-to-one correspondence with tilings of a 1 × n rectangular strip using squares, dominos, and trominos, where dominos come in one of three types. (By a square, domino, or tromino, we mean a 1×1, 1×2, or 1×3 rectangular piece, respectively.)

We may then view tilings enumerated by Q(n) as words in the alphabet {s, d^{1}, d^{2}, d^{3}, t}, where s and t denote square and tromino, respectively, and d^{i} denotes one of three types of dominos. Equivalently, such words may be viewed as compositions in {1, 2, 3} of a positive integer n, where the 2’s are marked in one of three ways. Note that the five types of letters in these words correspond to the five types of sections that the tilings enumerated by Q(n) are divided into by lines parallel to the legs of the parallelogram and not dissecting any of the pieces used.

We now adapt to the current problem a concept discussed in Benjamin and Quinn [2, Section 1.2] for rectangular tilings enumerated by the Fibonacci numbers. Let A_{n} denote the set of tilings of a 1 × n strip with squares, dominos, and trominos, where dominos come in one of three types. If 1 ≤ m ≤ n − 1, then we will say that λ ∈ A_{n} is breakable at m if it may be expressed as λ = λ′ + λ′′, where λ′ and λ′′ have respective lengths of m and n − m, that is, if there is no piece covering the boundary between the m-th and (m + 1)-st cells. Otherwise, we will say that λ is unbreakable at m. Note that if λ is unbreakable at m, then either cells m − 1, m, and m + 1 or m, m + 1, and m + 2 are covered by a tromino or cells m and m + 1 are covered by one of three kinds of dominos.

2.1 Proof of Proposition 1

We will define a near bijection f between the sets A_{n} and R = A_{n−1}^{(1)} ∪ A_{n−1}^{(2)} ∪ A_{n−2}, where A_{n−1}^{(i)}, i = 1, 2, denotes two copies of the set A_{n−1}. Note that |R| = 2Q(n−1)+Q(n−2). Let λ ∈ A_{n}. We consider cases on the right-most piece of λ that is not a d^{3}. If λ = λ′ + s + (d^{3})^{j} for some j ≥ 0, then let

f(λ) = \begin{cases}λ′ ∈ A_{n−1}^{(1)}, & if j = 0; \\ λ′ + d^{1} + (d^{3})^{j−1} ∈ A_{n−1}^{(2)}, & if j > 0, \end{cases}  (2)

where “+” denotes concatenation. If λ = λ′ + d^{1} + (d^{3})^{j}, then let

f(λ) = \begin{cases}λ′ ∈ A_{n−2}, & if j = 0; \\ λ′ + t + (d^{3})^{j−1} ∈ A_{n−1}^{(2)}, & if j > 0. \end{cases}  (3)

For the remaining cases, we let

f(λ) = \begin{cases}λ′ + s + (d^{3})^{j} ∈ A_{n−1}^{(2)}, & if λ = λ′ + d^{2} + (d^{3})^{j}; \\ λ′ + d^{2} + (d^{3})^{j} ∈ A_{n−1}^{(2)}, & if λ = λ′ + t + (d^{3})^{j}, \end{cases}  (4)

where j ≥ 0. Note that f is one-to-one and its inverse may be obtained by considering the component of R to which a member of this set belongs, and if it belongs to A_{n−1}^{(2)}, the right-most piece that is not a d^{3}.

If n is even, then the mapping f is not defined for λ = (d^{3})^{\frac{n}{2}} , but its inverse is defined for all members of R. Thus, |A_{n}| = |R| + 1, which implies the desired formula when n is even. Similarly, when n is odd, then f is defined on all of A_{n} but misses λ′ = (d^{3})^{\frac{n−1}{2}} ∈ A_{n−1}^{(2)}, whence |A_{n}| = |R| − 1, which completes the proof of Proposition 1.

2.2 The n = 4m case of Theorem 2

By the previous proposition, the n = 4m case of Theorem 2 above is equivalent to showing

Q(4m) = (Q(2m) − Q(2m − 2))(Q(2m + 1) − Q(2m − 1)).

Note that by recurrence (1), we have Q(2m) − Q(2m − 2) = |U|, where

U = A_{2m−1} ∪ A_{2m−2}^{(1)} ∪ A_{2m−2}^{(2)} ∪ A_{2m−3},

with A_{2m−2}^{(i)} denoting two identical copies of the set A_{2m−2}. Similarly, we have Q(2m + 1) − Q(2m − 1) = |V|, where

V = A_{2m} ∪ A_{2m−1}^{(1)} ∪ A_{2m−1}^{(2)} ∪ A_{2m−2},

with similar notation for A_{2m−1}^{(i)}, i = 1, 2.

To prove Theorem 2 when n = 4m, we first define a partial mapping g between U × V and A_{4m}. Let γ = (α, β) ∈ U × V. In defining g, we will consider cases on α. First, if α ∈ A_{2m−1}, then let

g(γ) = \begin{cases}α + s + β, & if β ∈ A_{2m}; \\ α + d^{1} + β, & if β ∈ A_{2m−1}^{(1)}; \\ α + d^{2} + β, & if β ∈ A_{2m−1}^{(2)}; \\ α + t + β, & if β ∈ A_{2m−2}, \end{cases}  (5)

where “+” denotes concatenation. Next, if α ∈ A_{2m−2}^{(1)}, then let

g(γ) = \begin{cases}α + d^{1} + β, & if β ∈ A_{2m}; \\ α + d^{3} + s + β, & if β ∈ A_{2m−1}^{(1)}; \\ α + t + β, & if β ∈ A_{2m−1}^{(2)}; \\ α + d^{3} + d^{1} + β, & if β ∈ A_{2m−2}. \end{cases}  (6)

If α ∈ A_{2m−3}, then let

g(γ) = \begin{cases}α + t + β, & if β ∈ A_{2m}; \\ α + d^{1} + d^{3} + β, & if β ∈ A_{2m−1}^{(1)}; \\ α + d^{2} + d^{3} + β, & if β ∈ A_{2m−1}^{(2)}; \\ β + d^{3} + t + α, & if β ∈ A_{2m−2}. \end{cases}  (7)

If α ∈ A_{2m−2}^{(2)}, then let

g(γ) = \begin{cases}α + d^{2} + β, & if β ∈ A_{2m}; \\ α + s + d^{3} + β, & if β ∈ A_{2m−1}^{(1)}; \\ α + d^{3} + d^{2} + β, & if β ∈ A_{2m−2}. \end{cases}  (8)

Finally, if γ = (α, β), where α ∈ A_{2m−2}^{(2)} and β ∈ A_{2m−1}^{(2)} starts with a square, then let

g(γ) = α + d^{3} + d^{3} + β′,

where β′ is obtained from β by removing the initial square.

The function g is not defined for those ordered pairs (α, β) such that α ∈ A_{2m−2}^{(2)} and β ∈ A_{2m−1}^{(2)}, not starting with a square. Note that (5) covers all cases in which a member of A_{4m} is breakable at the boundary 2m − 1 except for those tilings in which the piece directly to the right of this boundary is a d^{3}. Two of the cases for breakable members of A_{4m} at 2m − 1 of this last type are covered in (7) and an additional case is covered in (8). Using (5)-(8), one may verify that g is one-to-one where it is defined and that g misses exactly those ρ ∈ A_{4m} of the following form: ρ is breakable at 2m − 1, with the piece directly to the right of this boundary being d^{3} and the piece to the left of this boundary being either d^{3} or t.

Thus, to complete the proof, it suffices to define a bijection between the sets C_{m} = A_{2m−1} × (A_{2m−3} ∪ A_{2m−4}) and D_{m} = A_{2m−2} × A_{2m−1}^{∗}, where A_{2m−1}^{∗} denotes the subset of A_{2m−1} not starting with a square. Let (λ, σ) ∈ C_{m}. We will construct an ordered pair (λ′, σ′) belonging to D_{m}. To do so, let us express λ as the word λ_{1}λ_{2} ⋯ in the alphabet {s, t, d^{1}, d^{2}, d^{3}} such that the i-th letter of the word represents the i-th piece of λ from the left, and, likewise, we express σ as σ_{1}σ_{2} · · ·. Let i_{0} denote the smallest index i ≥ 1 such that one (possibly both) of the following conditions fails to hold: (a) λ_{2i−1} = λ_{2i} = s, or (b) σ_{i} = d^{3} or t, with σ_{j} = d^{3} for all 1 ≤ j < i. In condition (b), we also require that σ ∈ A_{2m−3} or else this condition fai! ls with index one. Since 2m − 3 is odd, note that the index i_{0} always exists.

Let us first assume i_{0} = 1 and define a mapping in this instance. To do so, we consider several cases on λ. First, if λ does not start with s, then let σ′ = λ and λ′ be obtained from σ by adding either an s or d^{1} piece to the beginning of σ, depending on whether σ belongs to A_{2m−3} or A_{2m−4}, respectively. If λ starts with s, but not with ss or sd^{1}, then we delete the first square of λ to obtain λ′ and add either d^{1} or t to the beginning of σ to obtain σ′. If λ starts with ss and σ ∈ A_{2m−4}, then let λ′ = σ + d^{2} and σ′ = λ − ss + d^{2}, where the addition and subtraction of the indicated letters happens now at the beginning of words. If λ starts with sd^{1} and σ ∈ A_{2m−3}, then let λ′ = λ − sd^{1} + d^{3} and σ′ = σ + d^{2}. If λ starts w! ith sd^{1} and σ ∈ A_{2m−4}, then let λ′ = λ − sd^{1} + d^{3} and σ′ = σ + d^{3}s. Finally, if λ starts with ss and σ ∈ A_{2m−3}, then we consider the following three further subcases: σ starts with (i) s, (ii) d^{1}, or (iii) d^{2}. For (i), we let λ′ = σ − s + d^{2} and σ′ = λ − ss + d^{3}; for (ii), we let λ′ = σ − d^{1} + t and σ′ = λ − ss + d^{2}; and for (iii), we let λ′ = σ − d^{2} + t and σ′ = λ − ss + d^{3}.

The mapping (λ, σ) ↦ (λ′, σ′) is seen to be one-to-one and is defined for all ordered pairs (λ, σ) for which i_{0} = 1. We now wish to extend it to all ordered pairs (λ, σ) for which i_{0} > 1. Note that if i_{0} > 1, then λ starts with at least 2(i_{0} − 1) s pieces and σ ∈ A_{2m−3} starts with at least i_{0} − 2 d^{3} pieces, with the (i_{0} − 1)-st piece either a d^{3} or a t. In this case, we let (λ′, σ′) be given by

λ′ = (λ − (s)^{2i_{0}−2})′ + (d^{3})^{i_{0}−1}

and either

σ′ = (σ − (d^{3})^{i_{0}−1})′ + (d^{3})^{i_{0}−1} or σ′ = (σ − (d^{3})^{i_{0}−2} − t)′ + (d^{3})^{i_{0}−1},

where the prime operation appearing on the right-hand side of the last two equations is as defined in the case i_{0} = 1 above (now applied to members of C_{m−i_{0}+1} for which the violating index is one). This defines the ′ mapping for all ordered pairs for which i_{0} > 1 and hence for all of C_{m}. One may verify that it is a bijection. Note that in constructing the inverse mapping on D_{m}, one would write λ′ = λ′_{1}λ′_{2} ⋯ and σ′ = σ′_{1}σ′_{2} ⋯ and consider the smallest index j ≥ 1 such that one of the following conditions fails to hold: (i) λ′_{j} = d^{3}, or (ii) σ′_{j} = d^{3}, with σ′_{j+1} ≠ s.

2.3 Proof of remaining cases of Theorem 2

The other cases of Theorem 2 can be proved in a similar manner, which we now discuss. By Proposition 1, the n = 4m + 1 case of Theorem 2 is equivalent to showing

Q(4m + 1) = (Q(2m) + 2Q(2m − 1) + Q(2m − 2))^{2}.

For this, we can define an explicit bijection between the set of ordered pairs from A_{2m} ∪ A_{2m−1}^{(1)} ∪ A_{2m−1}^{(2)} ∪ A_{2m−2} and the set of tilings A_{4m+1}. The construction of the bijection follows along roughly similar lines to the n = 4m case above, with one needing to define in the end a bijection between the sets C_{m} and D_{m}. The main difference with the n = 4m case is that it is more convenient to consider cases using the criterion of breakability at 2m rather than at 2m − 1 with regard to members of A_{4m+1}.

To show the n = 4m + 2 case, we define a bijection h between the sets U × V = (A_{2m−1}^{(1)} ∪ A_{2m−1}^{(2)} ∪ A_{2m}^{(1)} ∪ A_{2m}^{(2)}) × (A_{2m} ∪ A_{2m+1}) and A_{4m+2}, where A_{j}^{(i)}, i = 1, 2, denotes two identical copies of the set A_{j}. Let γ = (α, β) ∈ U × V. We first construct some members of A_{4m+2} that are breakable at 2m + 1 from ordered pairs (α, β). If β ∈ A_{2m+1}, then let

h(γ) = \begin{cases}α + d^{1} + β, & if α ∈ A_{2m−1}^{(1)}; \\ α + d^{2} + β, & if α ∈ A_{2m−1}^{(2)}; \\ α + s + β, & if α ∈ A_{2m}^{(1)}. \end{cases}  (9)

We next construct members of A_{4m+2} that are not breakable at 2m + 1. If β ∈ A_{2m}, then let

h(γ) = \begin{cases}α + t + β, & if α ∈ A_{2m−1}^{(1)}; \\ β + t + α, & if α ∈ A_{2m−1}^{(2)}; \\ α + d^{1} + β, & if α ∈ A_{2m}^{(1)}; \\ α + d^{2} + β, & if α ∈ A_{2m}^{(2)}. \end{cases}  (10)

Let S denote the members of A_{4m+2} that are missed by the mapping h. Note that the breakable members of S at 2m+1 are those where the piece directly preceding the boundary at 2m+1 is a d^{3} or t, while the unbreakable members of S at 2m+1 are those where a d^{3} piece covers the boundary at 2m+1. Since h is seen to be one-to-one where it is defined, it suffices to define a bijection between S and the set T consisting of ordered pairs (α, β) ∈ U × V such that α ∈ A_{2m}^{(2)} and β ∈ A_{2m+1}.

Clearly, one may identify the unbreakable members of S at 2m+1 with those members of T in which β starts with a square. Thus, we need to define a bijection between the members of S that are breakable at 2m + 1 and the members of T in which β does not start with a square. This amounts to defining a bijection between the sets C_{m+1} and D_{m+1}, which has already been done.

Finally, for the n = 4m + 3 case, we construct a bijection between the set (A_{2m}^{(1)} ∪ A_{2m}^{(2)} ∪ A_{2m+1}^{(1)} ∪A_{2m+1}^{(2)})×(A_{2m} ∪A_{2m+1}) and A_{4m+3}. The proof follows along roughly similar lines to the n = 4m+2 case, except that it is more convenient to consider the criterion of breakability at 2m + 2 rather than at 2m + 1. In the end, it also reduces to finding a bijection between the sets C_{m+1} and D_{m+1}, which is already done.

References

[1] A. T. Benjamin, S. Plott, and J. A. Sellers, Tiling proofs of recent sum identities involving Pell numbers, Ann. Comb. 12 (2008), 271–278.

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

[3] J. Bodeen, S. Butler, T. Kim, X. Sun, and S. Wang, Tiling a strip with triangles, Electron. J. Combin. 21 (2014), #P1.7.

[4] N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, http://oeis.org, 2010.

2010 Mathematics Subject Classification: Primary 05A19; Secondary 05A05. Keywords: triangular tiling, Fibonacci number, combinatorial proof.

(Concerned with sequences \underline{A000045}, \underline{A000129}, and \underline{A097076}.)

Received January 19 2014; revised version received March 20 2014. Published in Journal of Integer Sequences, March 24 2014.

Return to Journal of Integer Sequences home page.