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!

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.
