Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
+1 for coming up with your own math question. – Sammy Black Apr 11 '13 at 20:58
For $1\times n$ boards, you get the Fibonacci numbers. For $2\times n$ boards it's already a bit harder. You get the recurrence relation $a_n = 3a_{n-1} + a_{n-2} - a_{n-3}$, see – azimut Apr 11 '13 at 21:49
up vote 15 down vote accepted

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.

share|cite|improve this answer
so it's like a program? – user67258 Apr 11 '13 at 21:18
See also which gives all the rectangles, not just the squares. – Charles Apr 11 '13 at 21:32
@herderp: Sorry, I don't understand that question. What's like a program? – joriki Apr 11 '13 at 22:12
I thought the sequence is computed by a computer program – user67258 Apr 11 '13 at 22:24

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:

share|cite|improve this answer

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.

share|cite|improve this answer

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:

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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.