Chessboard Tilings

We will attempt to find a recursive relationship between tiling a board of size $4 \times n$ and tiling a board of size $4 \times (n-1)$ .

Consider a tiling of a $4 \times n$ board using enough $2 \times 1$ dominoes. There are five possible ways the dominoes in the last column of the board can be arranged. There can be (1) two vertical dominoes, (2) one horizontal above one vertical above one horizontal (each of the horizontals extends into the previous column, but we only care about the half of the horizontal domino in the last column), (3) one vertical above two horizontals, (4) two horizontals above one vertical, or (5) four horizontals.

Let's examine what the possible ways to add a column are given the current last column has each of these orientations. In other words, how can we change the contents of the last column to help make another column without affecting the contents of the second to last column?

Last column has form (1): Because none of the dominoes in the last column touch the second to last column, we can change the dominoes in the last column freely to create a new column in any of the five possible forms.

Last column has form (2): Without affecting the second to last column, we can only change the orientation of the vertical domino, which will cause a square to be "trapped" either in the bottom or the top of the new column. Therefore, we can't change the orientation of any of the dominoes in the last column and can only add a new column which is of form (1).

Last column has form (3): We can only change the orientation of the vertical domino, which means we must also place a horizontal domino to fill the spot which is no longer filled by the vertical one. A vertical domino must then be placed in the remaining two open spots in the new column, producing (4). Also, the vertical domino can be left in place, and a new column of form (1) can be added.

Last column has form (4): Essentially the same as in the previous case, except we can have a new column with either form (1) or (3).

Last column has form (5): We can't change the orientation of any of the dominoes in the last column without affecting those in the second to last column, and so the new column can only be of form (1).

Now we let $f_i(n), i \in \{1,2,3,4,5\}$ represent the number of tilings of a $4 \times n$ board which have a last column of form $i$ and let $f(n)$ be the sum of these five functions for a given $n$ . What we did above was essentially establish the following recursive relationship for the $f_i$ : $\begin{array}{c}\\ f_1(n+1) = f_1(n) + f_2(n) + f_3(n) + f_4(n) + f_5(n) \\ f_2(n+1) = f_1(n) \\ f_3(n+1) = f_1(n) + f_4(n) \\ f_4(n+1) = f_1(n) + f_3(n) \\ f_5(n+1) = f_1(n) \end{array}$

Using the fact that $f_1(1) = 1$ and $f_i(1) = 0, i \neq 1$ , we can find $f(7) = f_1(7) + f_2(7) + f_3(7) + f_4(7) + f_5(7)$ , which is $747$ , which should be the total number of tilings of a $4 \times 7$ board using $2 \times 1$ dominoes.

However, we have excluded some possibilities by only looking at the last column: we can have $4 \times 4$ blocks with columns of form (2)(5)(5)(2) (this arrangement looks like a brick wall pattern) or $4 \times 6$ blocks with columns of form (2)(5)(5)(5)(5)(2). In a $4 \times 7$ board, we can only have one of either of these two blocks. If we have a $4 \times 4$ block, it can be placed on an edge of the board, in which case the remaining three columns can be constructed in $f(3) = 11$ ways or have a column of form (1) followed by the block followed by two more columns, which can be constructed in $f(2) = 5$ ways. This gives $2 \cdot (11 + 5) = 32$ extra tilings (since there are two edge positions and two non-edge positions). Also, if we have a $4 \times 6$ block, we can place a column of form (1) on either side of it to complete the $4 \times 7$ board, which gives $2$ extra tilings.

Thus, our final answer is $747 + 32 + 2 = \fbox{781}$ .

This proof will only generate a system of recurrence equations; solving it is simply bruteforce. (To tell the truth, I also used a spreadsheet program after getting the recurrences, but it's just 30 additions of at most three-digit numbers, doable by hand.)

We will fill the board from the left. We categorize the boards according to their left ends:

• Type A: The left end is complete (the board is $4 \times n$ for some $n$ ).
• Type B: The board is missing a vertical domino in a corner.
• Type C: The board is missing a horizontal domino in a corner.
• Type D: The board is missing a single cell in each corner (so two squares are missing).
• Type E: The board is missing a 2x2 square in a corner.

See reference image here .

Let $A(n), B(n), C(n), D(n), E(n)$ be the number of ways to tile a $4 \times n$ board of type A,B,C,D,E respectively.

We begin by giving some initial values.

$A(0) = 1, B(0) = C(0) = D(0) = E(0) = 0$ . A $4 \times 0$ board can be tiled with nothing, thus $A(0) = 1$ . However, there doesn't exist anything to take away, so we cannot form boards B,C,D,E. Of course, if the board cannot be constructed at all, there's no valid tiling, thus $B(0) = C(0) = D(0) = E(0) = 0$ .

$A(1) = B(1) = D(1) = 1, C(1) = E(1) = 0$ . There obviously exists a $4 \times 1$ board for A, and we can take either two squares nearest to some corner to form B or both corner squares to form D. A,B,D obviously have one way of tiling each, thus $A(1) = B(1) = D(1) = 1$ . However, to form C or E, we need to have two incomplete columns; impossible with just $4 \times 1$ aka 1-column board. So $C(1) = E(1) = 0$ .

Now we will generate the system of recurrences. We will do this by putting a domino on the leftmost square, and if there are several, the topmost one; call this square the "hot square". Due to how we choose the hot square, there are only two ways to tile the hot square, either vertically (downward) or horizontally (rightward). You might want to see the reference image for the following section; yellow dominoes are dominoes covering the hot square and olive/light olive dominoes are forced dominoes.

From a board of type A, we can take either a vertical domino containing the hot square to form a board of type B, or a horizontal domino containing the hot square to form a board of type C. This is the first column of the image.

From a board of type B, we can take either a vertical domino containing the hot square to form a board of type A with one less length, or a horizontal domino containing the hot square. The latter will force a horizontal domino at the bottom-left corner, making a board of type B of one less length. This is the second column of the image.

From a board of type C, we can take either a vertical domino containing the hot square, or a horizontal domino containing the hot square to form a board of type E. The former forces a horizontal domino at the bottom, forming a board of type D with one less length. This is the third column of the image.

From a board of type D, we can take either a vertical domino containing the hot square to form a board of type A with one less length, or a horizontal domino containing the hot square. The latter forces three more dominoes to form a board of type D with two less length. This is the fourth column of the image; the light olive domino is forced after putting the olive dominoes.

From a board of type E, we can take either a vertical domino containing the hot square to form a board of type B with one less length, or a horizontal domino containing the hot square. The latter forces a horizontal domino at the bottom, forming a board of type A with two less length. This is the fifth column of the image.

The above five paragraphs cover all possibilities, so we can construct the system of equations:

• $A(n) = B(n) + C(n)$
• $B(n) = A(n-1) + B(n-1)$
• $C(n) = D(n-1) + E(n)$
• $D(n) = A(n-1) + D(n-2)$
• $E(n) = B(n-1) + A(n-2)$

Together with the ten initial values given above, we can find the value of $A(7)$ , which is what we're looking for. This value is equal to $\boxed{781}$ .

Consider the positions of dominoes cut by each vertical line segment. Since the number of black squares equals the number of white squares on each side, the dominoes cut by a vertical line segment must have as many black squares on the left as white squares on the left. So, the possible patterns are (0,0,0,0) (nothing cut, seen on the leftmost and rightmost vertical segments), (1,1,0,0), (0,1,1,0), (0,0,1,1), (1,0,0,1), and (1,1,1,1). The following matrix shows how many ways to go from the ith state to the jth state on the next vertical line to the right:

$T = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 1 \newline 1 & 0 & 0 & 1 & 0 & 0 \newline 0 & 0& 0& 0 & 1 & 0 \newline 1 & 1 & 0 & 0 & 0 & 0 \newline 1 & 0 & 1 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

The top left corner of $T^n$ tells us the number of ways to tile a $4 \times n$ chessboard with dominoes. For $T^7$ this is 781. See also http://oeis.org/A005178.

We will describe the coordinates of a board of dimension $4 \times n$ by the coordinates $(i,j)$ where $i \in \{1,2,3,4\}$ and $j \in \{1,2, \ldots, n\}$ . We define three different sequences. Let $f(n)$ be the number of ways to tile a $4 \times n$ board with $2n$ of the tiles. We wish to compute $f(7)$ . Let $g(n)$ be the number of ways to tile a $4 \times n$ with $2n-1$ tiles such that positions $(1,n)$ and $(2,n)$ are uncovered, and let $h(n)$ be the number of ways to tile a $4 \times n$ board with $2n-1$ tiles such that positions $(1,n)$ and $(4,n)$ are uncovered.

Suppose that for some $n \ge 3$ we wish to calculate $f(n)$ . The $n$ th column of a valid tiling of the $4 \times n$ board has 5 possibilities. Drawing them out, it becomes apparent that $f(n) = f(n-1) + f(n-2) + 2g(n-1) + h(n-1)$ . Similarly, examining the possibilities for the $n$ th row for tilings satisfying the definitions of $g(n)$ and $h(n)$ it is easy to see that $g(n) = f(n-1) + g(n-1)$ and $h(n) = f(n-1) + h(n-2)$ . Looking at base cases we can easily check that $f(1) = g(1) = h(1)=1$ and $f(2) = 5$ , $g(2) = 2$ , $h(2) = 1$ .

Writing out a table for all the values $f(n), g(n), h(n)$ and calculating each new row from the previous two, we find that $f(7) = f(6) + f(5) + 2g(6) + h(6)$ $= 281+95+2*149+107 = \boxed{781}$ .

This is a simple application of the Temperly & Fisher relation for dominoes tiling. The number of ways to cover an $m\times n$ grid with dominoes is given by:

$\prod_{j=1}^m \prod_{k=1}^n \left ( 4\cos^2 \frac{\pi j}{m + 1} + 4\cos^2 \frac{\pi k}{n + 1} \right )^\frac{1}{4},$

Substituting $m = 4, n =7$ leads an answer of 781 .