Tiling Problem

If your computer is broken and you're really good at arithmetic, you can do the following:

Let $f(n)$ be the number of ways to tile a $2 \times n$ rectangular board in the desired way. Let $g(n)$ be the number of ways to tile a $2 \times n$ rectangular board that is missing a corner.

Note the base cases $f(1)=2$ and $g(1)=1$ .

For brevity, denote a $2 \times 1$ tile as a domino.

We now find a recursive relation for $f(n)$ . We take a bunch of cases. Assume $n>1$ .

• If the topleft cell is covered by a $1 \times 1$ tile, there are $g(n)$ ways to tile the rest of the board.

• If the topleft cell is covered by a vertical domino, there are $f(n-1)$ ways to tile the rest of the board.

• If the topleft cell is covered by a horizontal domino, then...

  • If the bottomleft cell is covered by a $1 \times 1$ tile, there are $g(n-1)$ ways to tile the rest of the board.

  • If the bottomleft cell is covered by a horizontal domino, then there are $f(n-2)$ ways to tile the rest of the board.

We now find a recursive relation for $g(n)$ . Assume WLOG that it is the bottomleft cell that is missing.

• If the topleft cell is covered by a $1 \times 1$ tile, there are $f(n-1)$ ways to tile the rest of the board.

• If the topleft cell is covered by a horizontal domino, there are $g(n-1)$ ways to tile the rest of the board.

We deduce that $f(n)=f(n-1)+f(n-2)+g(n-1)+g(n)$ , and $g(n)=f(n-1)+g(n-1)$ . By substitution, $f(n)=f(n-2)+2g(n)$ .

Note that: $g(n)=f(n-1)+g(n-1)=f(n-1) + f(n-2) + g(n-2) = f(n-1)+f(n-2)+f(n-3)+\cdots+f(1)+g(1)$ But $g(1)=1$ , so: $g(n)=1+\displaystyle\sum_{i=1}^{n-1}f(i)$

We can now substitute $g(n)$ to get: $f(n)=f(n-2)+2\left(1+\displaystyle\sum_{i=1}^{n-1}f(i)\right)$ And: $f(n-1)=f(n-3)+2\left(1+\displaystyle\sum_{i=1}^{n-2}f(i)\right)$

Subtracting these two equations and rearranging terms gets us: $f(n)=3f(n-1)+f(n-2)-f(n-3)$

Unfortunately, the characteristic polynomial for the recurrence has no obvious roots, so finding the general form isn't really an option. We now have to proceed by hand. We'll need three base cases. It is easiest to use $f(0)=1, f(1)=2, f(2)=7$ if you trust the reasoning "there is exactly one way to tile nothing". If not, it is not too hard to derive $f(3)=22$ . Taking your preferred bases and using the recurrence gets us $f(10)=\boxed{78243}$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <stdio.h>

int grid[20];

int recurs(int x) {
    while (x < 20 && grid[x]) x++;
    if (x >= 20) return 1;

    grid[x] = 1;
    int N = recurs(x+1);    // single tile

    if (x%2 < 1 && !grid[x+1]) {
        grid[x+1] = 1;      // vertical tile
        N += recurs(x+2);
        grid[x+1] = 0;
    }

    if (x < 18 && !grid[x+2]) {
        grid[x+2] = 1;      // horizontal tile
        N += recurs(x+1);
        grid[x+2] = 0;
    }

    grid[x] = 0;
    return N;
}

int main() {
    for (int x = 0; x < 20; x++) grid[x] = 0;

    printf("%d\n",recurs(0));
}

Explanation: grid[x*2+y] keeps track of whether a tile has been placed or not.

The recursive function recurs begins at position x and skips to the next empty spot. If there is no such spot, a solution has been found and we return 1.

Otherwise, a single tile is placed at position x , and the search continues starting at position x+1 .

If position x+1 next immediately below is available, the tile is extended downward and the search continues from there; the number of solutions is added to the number already found.

Likewise, if position x+2 immediately to the right is available, the tile is extended to the right and another set of solutions is added.

At the end, the new tile is removed.

Here is an alternative approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <stdio.h>

#define N 20

int main() {
    long f[N+1];

    f[0] = 1;
    for (int n = 1; n <= N; n++) {
        f[n] = 0;
        for (int k = 1; k <= n; k++)
            f[n] += f[n-k] * (k == 2 ? 3 : 2);

        printf("f(%d) = %ld\n",n,f[n]);
    }
}

The idea is that every pattern of width $n$ begins with an "indivisible" section of with $k$ , which cannot be cut vertically without dividing a tile.

• For $k = 1$ , there are two inseparable patterns, namely a single vertical tile or two tiles stacked on top of each other.

• For $k = 2$ , there are three inseparable patterns: two horizontal tiles on top of each other; a horizontal tile on top and two individual tiles underneath; or a horizontal tile on bottom and two individual tiles above it.

• For $k \geq 3$ , there are two inseparable patterns: start with an individual tile in the top-left and bottom-right corner, and fill up with horizontal tiles in an alternating pattern; or start with individual tiles bottom-left and top-right.

Each indivisible section of width $k$ is now followed by any pattern of width $n - k$ to generate the patterns of with $n$ . Thus, the number of patterns $f(n)$ of width $n$ satisfies the recursive equation $f(n) = \sum_{k=1}^n a_k f(n-k),$ with $a_k = 3$ for $k = 2$ , and $= 2$ for all other $k$ .

Output:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

f(1) = 2
f(2) = 7
f(3) = 22
f(4) = 71
f(5) = 228
f(6) = 733
f(7) = 2356
f(8) = 7573
f(9) = 24342
f(10) = 78243
f(11) = 251498
f(12) = 808395
f(13) = 2598440
f(14) = 8352217
f(15) = 26846696
f(16) = 86293865
f(17) = 277376074
f(18) = 891575391
f(19) = 2865808382
f(20) = 9211624463

The code looks pretty if you use pair recursion:

def f(n):
if n == 0:
    return 1
if n == 1:
    return 2
return 2*f(n-1) + f(n-2) + 2*g(n-1)

def g(n):
if n == 0:
    return 1
if n == 1:
    return 1
return f(n-1) + g(n-1)

print(f(10))
>78243

Here f(n) counts the ways to tile a $2 \times n$ , and g(n) counts the ways to tile a $2 \times n$ with a missing corner.

This is a regular dynamic programming problem. Let f return the number of ways of filling a rectangle of size $n \times 2$ . If poke is true, one corner is covered.

def f(n, poke):
    if n < 0:
        return 0
    if n == 0:
        return 0 if poke else 1
    if poke:
        return f(n - 1, poke) + f(n - 1, not poke)
    return 2 * (f(n - 1, poke) + f(n - 1, not poke)) + f(n - 2, False)
print(f(10, False))

With memoization, this would be a linear time solution. (Search for "memoization decorator" in Google to easily modify this Python code to be linear time.)

The problem can be simplifed by looking at the free spaces between various vertical tile placements. This has two benefits: it simplifies the problem to a one dimensional array, and it is just a matter of counting how many ways horizontal tiles can be placed between the verticals tiles. There are exactly 2^10 combinations of vertical tiles. For a gap of 2x1 spaces, the horizontal tiles can be arranged in just two combinations (tile or not tile). The various spaces are tabulated below:

1
2
3
4
5
6

1x2 spaces -> 2 combinations of horizontal tiles
1x3 spaces -> 3 combinations of horizontal tiles
1x4 spaces -> 5 combinations of horizontal tiles
1x5 spaces -> 8 combinations of horizontal tiles
1x6 spaces -> 13 combinations of horizontal tiles
1x7 spaces -> 21 combinations of horizontal tiles

Anyone seeing a FIBONACCI series arrising from this will be just as pleased as I was to see these useful set of numbers popping up yet again. To recap, each gap between the vertical tiles of size gapSize allows fib[ gapSize ] possible combinations of horizontal tiles. All the rest of the unused tiles are filled with 1x1 tiles by default. To get an total number of possibilities, just multiply each fibonacci number for each appearance (line 18). The code is simply:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#Tiling Problem (using Python)

MAX=21
fibonacci=[1] * int(MAX+1)
for f in range(2,MAX+1):
  fibonacci[f]=fibonacci[f-1]+fibonacci[f-2]

for SIZE in range(2,MAX):                      #all rectangles sizes 2 to 20
  total=0
  F='{:0'+str(SIZE)+'b}'                          #using binary for a combinatorial iterator
  for r in range(0,2**SIZE): 
    binary=F.format(r) + "E"                      #e.g. 1000000001 means one vertical 1x2 block at each end
    gapSize=0
    combinations=1
    for bit in list(binary):
      if (bit=='0'): gapSize=gapSize+1
      else:
        combinations=combinations*fibonacci[gapSize]**2
        gapSize=0
    total=total+combinations 
  print(SIZE, total)

the general results are:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

2 7
3 22
4 71
5 228
6 733
7 2356
8 7573
9 24342
10 78243       #our answer for a rectangle of length 10
11 251498
12 808395
13 2598440
14 8352217
15 26846696
16 86293865
17 277376074
18 891575391
19 2865808382
20 9211624463

My implementation, which is equal to some recursive implementations in principle, but different in that it uses a for loop instead.

def combRect(n):
    lstRect = [0]*(n + 1)
    lstSpec = [0]*(n + 1)

    lstRect[n] = 1

    for ind in range(n, 1, -1):
        tVar = lstRect[ind]

        lstRect[ind - 1] += 2*tVar
        lstRect[ind - 2] += tVar
        lstSpec[ind - 1] += 2*tVar

        tVar = lstSpec[ind]

        if tVar > 0:
            lstRect[ind - 1] += tVar
            lstSpec[ind - 1] += tVar

        lstRect[ind] = 0
        lstSpec[ind] = 0

    output = lstRect[0] + lstSpec[0]

    if n >= 1:
        output += 2*lstRect[1] + lstSpec[1]

    return output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import itertools

def tilingsForRow(columns):
  if columns <= 1:
    return 1
  return tilingsForRow(columns-1) + tilingsForRow(columns-2)

def calcTilings(columns):
  indexes = range(columns)
  tilings = 0
  for verticalTiles in range(columns+1):
    for combination in itertools.combinations(indexes, verticalTiles):
      currentTilings = 1
      lastIdx = -1
      for curIdx in combination:
        currentTilings *= tilingsForRow(curIdx - lastIdx - 1)**2
        lastIdx = curIdx
      currentTilings *= tilingsForRow(columns - lastIdx - 1)**2
      tilings += currentTilings
  return tilings

def run():
  for n in range(11):
    print("tilings(%d)=%d" % (n, calcTilings(n)))

if __name__ == '__main__':
  run()

I've fixed the vertical tiles first, these are the possible combinations $columns \choose verticalTiles$ for verticalTiles $\in [0,columns]$ . Then the horizontal tiling is defined by the recursive function tilingsForRow squared on the spaces between vertical tiles (or at the end of the board)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

tilings(0)=1
tilings(1)=2
tilings(2)=7
tilings(3)=22
tilings(4)=71
tilings(5)=228
tilings(6)=733
tilings(7)=2356
tilings(8)=7573
tilings(9)=24342
tilings(10)=78243

First consider the placement of vertical $2$ x $1$ tiles. For each of the $10$ columns, a vertical tile can be there or not there, for $2^{10}$ possibilities. If we represent a present vertical tile as $1$ , and a non-present vertical tile as $0$ , we can use binary numbers to analyze every possibility.

Now between vertical tiles, there may be room for $1$ x $1$ tiles and horizontal $2$ x $1$ tiles in a given row. If $n$ is the number of columns available between vertical tiles (or the length of the string of zeros in the binary representation), then $k$ horizontal $2$ x $1$ tiles can fit in that space in one row in $\sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} {n - k \choose k}$ ways, which happens to be the sum of shallow diagonals in Pascal's triangle, which is equal to the Fibonacci number $F_{n + 1}$ . Since the second row would have the same number of horizontal tilings as the first row, each string of $n$ zeros would have $F_{n + 1}^2$ possible tilings.

We can therefore use binary numbers and the Fibonacci sequence in a computer program (similar to the one below) to find that there are $\boxed{78243}$ ways that a $2$ x $10$ rectangle can be filled with $1$ x $1$ and $2$ x $1$ tiles.

# Tiling Problem
# Python 2.7.3

def TilingPossibilities(columns):
    # generate a Fibonacci list
    Fibonacci = [1, 1]
    for a in range(2, columns + 1):
        Fibonacci.append(Fibonacci[a - 2] + Fibonacci[a - 1])

    # go through all possibilities (binary patterns) of vertical tile  
    #  placements in the first and second row, where 1 represents a  
    #  vertical tile and 0 represents no vertical tile
    totalpossibilities = 0
    for a in range(0, 2 ** columns):
        binarypattern = "{0:b}".format(a).zfill(columns)

        # go through each binary pattern and find strings of zeros
        zerostring = 1
        binaryproduct = 1
        for b, c in enumerate(binarypattern[:-1]):
            if c == "0" and c == binarypattern[b + 1]:
                # the string of zeros continues, so increase its counter
                zerostring += 1
            elif c == "0" and c != binarypattern[b + 1]:
                # the string of zeros is broken, so calculate the number of
                #  tiling possibilities (binaryproduct) in that string using 
                #  the Fibonacci pattern
                binaryproduct *= (Fibonacci[zerostring] ** 2)
                zerostring = 1

        # if the binary pattern ends in zero, calculate the number of tiling
        #  possibilities (binaryproduct) using the Fibonacci pattern
        if binarypattern[-1] == "0":
            binaryproduct *= (Fibonacci[zerostring] ** 2)

        # add the number of tiling possibilities (binaryproduct) for each 
        #  binary pattern to the total possibilities
        totalpossibilities += binaryproduct
    return totalpossibilities

print TilingPossibilities(10)

Let $f[n]$ denotes the way of tiling for $2 \times n$ with a vertical $2 \times 1$ tile at the end. Therefore we are looking for $f[11]$ .

Now, let's enumerate the possible last but one vertical $2 \times 1$ tile, and since there are no vertical $2 \times 1$ tiles between them, it reduces to a simple question of filling two $1 \times n$ with $1 \times 1$ and $2 \times 1$ tiles, the answer to which is the Fibonacci sequence.

Therefore we have the following formula:

$f[n] = \sum_{i=0}^{n-1}f[i]F[n-i]^2$

where $F[k]$ is the $k$ -th element of the Fibonacci sequence, starting $F[0]=1$ and $F[1]=1$ .

F = [1,1,2,3,5,8,13,21,34,55,89]    
f = [1]
for i in range(11):
    f.append(0)
    for j in range(i+1):
        f[i+1]+=f[j]*F[i-j]*F[i-j]
print(f[11])

By using the solutions for a board of size $2 \times (n-1)$ , it is possible to fill the board of size $2 \times n$ from one end, up until but not including the two tile spaces at the opposite end. (For the purpose of clarity, I will be filling from the left end of the board in my explanation, with the two free spaces remaining on the right end.)

By filling the board in this manner, we can work out the total number of solutions for a board of size $2 \times n$ using the following methods:

1. For every permutation of board size $2 \times (n-1)$ , there are two ways to solve the extra two tiles on the size $2 \times n$ board: two $1 \times 1$ tiles, or one $2 \times 1$ tile.
2. For every permutation of board size $2 \times (n-1)$ where the lower right space is a single $1 \times 1$ tile, a horizontal $2 \times 1$ tile can be placed from this space to the free tile to the right of it on the $2 \times n$ size board.
3. The same is true for all permutations where the top right space is a single $1 \times 1$ tile.
4. For every permutation of board size $2 \times (n-1)$ where both the right end spaces are $1 \times 1$ tiles, two horizontal $2 \times 1$ tiles can be placed there.

There are some more things we can consider to make working this out much simpler:

• Any solution with a single $1 \times 1$ tile in a right end corner can be mirrored vertically to produce a similar solution for the other corner. This means that for methods 2 & 3, only one set needs to be counted, and the result doubled to find the full set of permutations for both methods.
• Every solution for a $2 \times n$ size board using method 2 will have a single $1 \times 1$ tile in the upper right space, meaning it can be used to provide solutions for a $2 \times (n+1)$ board using method 3 (and vice versa).
• Methods 2 & 3 do not produce solutions where both right end spaces are single $1 \times 1$ tiles, but these are all already found using method 4.
• For the method from point 4, we can simply use the results for a board of size $2 \times (n-2)$ to find this set of solutions.

We can now count the number of solutions for a board, by adding these sets together:

Let $f(n)$ be the number of solutions for a board of size $2 \times n$ . Let $g(n)$ be the number of solutions for a board with a $1 \times 1$ tile in a specific right-end corner.

$f(n)=f(n-1)\times2+(g(n-1)+f(n-2))\times2+f(n-2)$

To Simplify:

$f(n)=(f(n-1)+g(n-1))\times2+f(n-2))\times3$

By counting the solutions of smaller boards, we know that $f(1)=2$ , $f(2)=7$ , and $g(2)=1$ .

We can now work out the number of solutions for larger boards, eventually getting us to $f(10)=\boxed{78243}$ (If you're lazy like me, you can just use a spreadsheet to quickly calculate the number of solutions for larger boards).