Ways to fill a $n\times n$ square with $1\times 1$ squares and $1\times 2$ rectangles

Question

I came up with this question when I'm actually starring at the wall of my dorm hall. I'm not sure if I'm asking it correctly, but that's what I roughly have:

So, how many ways (pattern) that there are to fill a $n\times n:n\in\mathbb{Z}_{n>0}$ square with only $1\times 1$ squares and $1\times 2$ rectangles?

For example, for a $2\times 2$ square:

• Four $1\times 1$ squares; 1 way.

• Two $1\times 1$ squares and one $1\times 2$ rectangle; $4$ ways total since we can rotate it to get different pattern.

• Two $1\times 2$ rectangles; 2 ways total: placed horizontally or vertically.

$\therefore$ There's a total of $1+4+2=\boxed{7}$ ways to fill a $2\times 2$ square.

So, I'm just wondering if there's a general formula for calculating the ways to fill a $n\times n$ square.

Thanks!

Answer 1

A hand count for $n=3$ yields $131$ ways, and a search for $1,7,131$ yields OEIS sequence A028420, the "number of monomer-dimer tilings of an $n\times n$ chessboard". The entry doesn't provide a formula (so it's likely that none is known), but some references.

Answer 2

We can probably give some upper and lower bounds though. Let $t_n$ be the possible ways to tile an $n\times n$ in the manner you described. At each square, we may have $5$ possibilities: either a $1\times 1$ square, or $4$ kinds of $1\times 2$ rectangles going up, right, down, or left. This gives you the upper bound $t_n \leq 5^{n^2}$.

For the lower bound, consider a $2n\times 2n$ rectangle, and divide it to $n^2$ $2\times 2$ blocks, starting from the top left and putting a $2\times 2$ square, putting another $2\times 2$ square to its right and so on... For each of these $2\times 2$ squares, we have $5$ possible distinct ways of tiling. This gives the lower bound $t_{2n} \geq 7^{n^2}$. Obviously, $t_{2n+1} \geq t_{2n},\,n \geq 1$, and therefore $t_n \geq 7^{\lfloor \frac{n}{2}\rfloor ^2}$.

Hence, \begin{align} 7^{\lfloor \frac{n}{2}\rfloor ^2} \leq t_n \leq 5^{n^2}, \end{align} or roughly (if $n$ is even), \begin{align} (7^{1/4})^{n^2} \leq t_n \leq 5^{n^2}. \end{align} BTW, $7^{1/4} \geq 1.6$. So, at least we know $\log t_n \in \Theta(n^2)$.

Note: Doing the $3\times 3 $ case for the lower bound, we get $(131)^{1/9} \geq 1.7$ which is slightly better.

Answer 3

Two comments:

1 If you only allow for the 1x2 rectangles, the problem is known as the domino tiling problem. You can find the answer here: http://en.wikipedia.org/wiki/Domino_tiling#Counting_tilings_of_regions

2 In the case of a cheseboard (and I think it can be generalized to squares of even side length), there are few things known about the case with 2 1x1 squares and dominoes.

If the two squares are placed on two board squares of same color, it is impossible to complete the tiling, while if the 2 squares are placed on opposite colors Gomory's theorem says that it is always possible to complete the tiling (but I think it doesn't say in how many ways).

Answer 4

If you just used $1\times2$ rectangles, then this is same as finding the number of matchings in the $m \times n$ rectangle graph, and a formula for that has been given by Kastelyn:

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

This was done, by mapping the number to the square root of the determinant of a weighted adjacency matrix of the graph.

If you include $1 \times 1$ squares, you essentially need to find the sum over all subgraphs (think of placing a $1\times 1$ square as deleting that vertex) of the $m \times n$ graph, and for each subgraph, the determinant approach still works, I believe, but might not have a nice closed form.

You can find a nice exposition for the $1\times 2$ case in the first chapter here: http://users.ictp.it/~pub_off/lectures/lns017/Kenyon/Kenyon.pdf