Given a $3\times3$ board, how many ways are there to tile it with $1\times1$ and $2\times1$ tiles such that rotation is allowed?

Question

Given a $3\times3$ board, how many ways are there to tile it with $1\times1$ and $2\times1$ tiles such that rotation is allowed.

The $1\times1$ tiles are colored red and the $2\times1$ tiles are colored blue. Note that the two tilings are identical.

Although the left one is made of two horizontal $2\times1$ tiles the right one is made of $2\times1$ vertical tiles and are identical. I managed to calculate a possible upper bound as $121$ and counted $118$ different possible tiling's manually however I feel like I've missed some. I've already tried searching for an answer through the internet but most of the things I've found are variations of this one. I thought about making a code that prints all combinations but unfortunately I have no idea on how id be able to code that.

Any help on this would be very appreciated.

Answer 1

You've mentioned that the two tilings are identical if they give the same color pattern. Essentially you're asking the number of colorings of a $3\times3$ board with blue and red such that the blue part can be tiled with $2\times1$ or $1\times2$ tiles without overlap.

From the $2\times1$ and $1\times2$ condition therefore you must satisfy the following

• An even number of cells are colored blue
• If we have a checkboard coloring of the board, exactly half of the blue cells land on blacks, and half of them land on whites
• There are no isolated blue cells

I have a quick script that checks the above conditions for all possible colorings and you can eyeball that all the resulting matrices are indeed proper.

Python Code

#Transforms a number to 0-1 list
def toBin(n, l):
    asd = [int(x) for x in bin(n)[2:]]
    return [0]*(l-len(asd)) + asd

#Transforms a list to a 3x3 list
def toM(lt):
    return [lt[0:3], lt[3:6], lt[6:9]]

#Quickly checks if the number is even and
#the checkboard condition is satisfied
#1 represents a blue cell
def quickC(m):
    tot = sum(sum(x) for x in m)
    if tot%2 != 0:
        return False
    bls = m[0][1] + m[1][0] + m[1][2] + m[2][1]
    if bls != tot/2:
        return False
    return True

#Helps the isolated vertex checking, if we reference
#an index outside the range, then returns false.
def gInd(m, i, j):
    if i<0 or j<0 or i>2 or j>2:
        return 0
    return m[i][j]

#Checks if i,j vertex is isolated
def checkIso(m, i, j):
    if m[i][j]==1:
        val = gInd(m, i+1, j)==0 and gInd(m, i-1, j)==0 and \
        gInd(m, i, j+1)==0 and gInd(m, i, j-1)==0
        if(val):
            return True
    return False

#Checks if there are no isolated vertices
def checkIsoAll(m):
    for i in range(3):
        for j in range(3):
            if checkIso(m, i, j):
                return False
    return True

#Prints out a matrix in a nice and easy to understand form
def prM(m):
    s = ""
    for asd in m:
        sr = ""
        for dsa in asd:
            if dsa==1:
                sr += "#"
            else:
                sr += "-"
        s += sr
        s += "\n"
    return s

#Main code
total = 0
for n in range(2**9):
    m = toM(toBin(n, 9))
    if(quickC(m) and checkIsoAll(m)):
        total +=1
        print(prM(m)+"\n\n")
print("total number {}".format(total))

There are $98$ such tilings (colorings)