Ways to L tromino tile a mutilated chessboard

21 Views Asked by At

Suppose we have a 2^n×2^n board. I understand the proof that you can use any rotation of L shaped trominoes and a monomino to fill the board completely, given you can mix different rotations in the same tiling. I am stuck trying to devise a way to count the ways to tile such a board for any given n. I know the base cases, n = 0, 1 have one tiling respectively, but am stuck trying to use that to count for larger boards. I’ve tried breaking a n=2 (4 x 4) boated into n/2 sub problems but run into an issue there because filling the quadrant with the one monimo is possible, and then adding a tromino to the center such the remaining quadrants are sub problems makes me think each board has only 4 ways to tile? Someone please correct my logic/ help me find the proper recurrence please!