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

combinatoricstiling

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.

enter image description here

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.

Best Answer

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)

Related Question