Uncategorized

Solutions to Tiling 2

The problems asked how to count infinite sets of various physical objects. Justifications of the answers, or solutions, would usually be based on those descriptions or on formulas that themselves are based on those descriptions. The original statement of the problems provided a suggestion for how to do it for Problem 1.

  1. 1. In how many ways {fN} can a 1 x N rectangle (called an N-board) be tiled by dominoes and squares? All N-boards either begin with a square or a domino. Since we are looking at just one end, we have a partition of N-boards into two sets*. The size of the set that begins with a square is fN-1. The size of the set that begins with a domino is fN–2. So fN = fN–1 + fN–2. To completely determine where this equation holds, we need to check the starting values. Combinatorists usually say that the size of a set containing the empty set is 1, so we’ll say that f0 = 1. Clearly f1 = 1 and f2 = 2. Thus fN = fN–1 + fN–2 holds for N=2 and above.

*If we look at the other end of the N-boards, the partition will be different but the counts will be the same.

  1. 2. In how many ways {gN} can an N-board be symmetrically tiled by dominoes and squares? There are two ways to look at this.
  2. a) Imitating the solution to problem 1 we can partition symmetric N-boards into those which end in squares and in dominoes. Since they are symmetric, they will have to have the same type of tile at both ends and the board between the two end tiles must be symmetric. Thus, the number that end in squares = gN–2 and the number that end in dominoes = gN–4. So gN = gN–2 + gN–-4. Given that g0 = g1 = g3 = 1, g2 = g5 = 2, and g4 = 3, then gN = gN–2 + gN–4 holds for N=4 and above.
  3. b) Alternatively, we can observe that a board of odd length, say 2N+1, must have a central square with two arms of equal length N that are mirror images of each other. Thus g2N+1 = fN for N ≥ 0. A board of even length, say 2N, has, either a central domino or a central empty set with two arms of equal length N-1 or N respectively that are mirror images of each other. Thus g2N = fN–1 + fN = fN+1 for N > 0. For N = 0, g2N = g0 = 1 = f1 = fN+1, so g2N = fN+1 for N ≥ 0.

By the way, the two arguments above have proved that the formula in a) produces the same sequence as the formulas in b).

  1. 3. In how many ways {hN} can an N-board be tiled by dominoes and squares where two tilings, which are the same when turned 180°, are now considered the same?

The best way is to attack this problem seems to do alternative b) first. Observe that the non-symmetric N-boards come in pairs, one a reflection of the other, so we only want to count half of them. On the other hand, we want to count all the symmetric N-boards. In Problem 2 we said there are gN symmetric N-boards. The count of the remaining non-symmetric N-boards is thus fNgN.. So hN = (fNgN)/2 + gN = (fN + gN)/2 for N ≥ 0.

  1. a) If you looked at the answer you can see that the recursive formula is complicated. However, it can be derived from the formula in alternative a). If the board is of even length, then h2N = (f2N + g2N)/2 = (f2N + fN+1)/2 = (f2N–-1 + f2N-2+ fN + fN–1)/2 = (f2N–1 + fN–1)/2 + (f2N–2+ fN)/2 = h2N–1 + h2N–2. However, if we apply the same equations for a board of odd length we get h2N+1 = h2N + h2N–1fN–1. To get rid of the pesky f-term, we move it to the left side of the equation while moving the h-term on the left to the right, giving us a formula for f as a function of h. Now we apply the identity fN–-1 + fN–2 fN = 0 to get a recursive identity which can be written h2N+1 = h2N + 2h2N–1h2N–2h2N–4h2N–5 for N > 2. All the initial values can be determined from the formula in part a) or directly. (The recursive identity can be written in alternative but equivalent ways. I don’t have a story proof for it. You are welcome to try your hand.)
  2. 4. How many ways {cN} can an N-circle be tiled by dominoes and squares where tilings, which are the same when rotated or flipped 180°, are considered different?

 

5 (extra credit). How many ways can a bracelet of length N be beaded by beads of lengths 1 and 2? There are 4 variations. i) This variation is problem 4.

  1. ii) This variation identifies bracelets that can be rotated into each other {dN}.

iii) This variation identifies flips {eN}.

  1. iv) The final variation identifies rotations and flips. Since every rotation can be implemented by two flips, this is the same as variation iii.
Print Article
Next article Necessity Is the Mother of (Re)invention
Previous article A Long Stroll Through Avoca Cemetery—An actuarial study … and a few meditations and meanderings

Related posts