Ways to fill a $n\times n$ square with $1\times 1$ squares and $1\times 2$ rectangles 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!
 A: 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.
A: 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).
A: 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.
A: 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
