There is a board of size (m x n).
We are offered square blocks in 3 size (1x1, 2x2, 3x3).
How many different ways to place blocks on the board. (We don't have to fill the board, some cell on the board may be empty)?
There is a board of size (m x n). We are offered square blocks in 3 size (1x1, 2x2, 3x3). How many different ways to place blocks on the board. (We don't have to fill the board, some cell on the board may be empty)? 


This question is related to lattice systems of the Classical Statistical Mechanics, there are sharp results, see Ising models and related. The problem is completely solved when there are two domino blocks $2\times 1$ and $1\times 2$. Then it's just a little simpler that the solution of the classical 2dimensional Ising model. Going back to the given question, if one side of the board, let's say $m$, is relatively smalllet's consider it fixed, then we may consider the other one, $n$, to be variable, and we can get recursion with respect to $n$ known from the solution of the $1$dimensional lattice systems (special cases were considered also outside the Statistical Mechanics). The solution is in terms of a matrix which gets large when $m$ is large (thus true passing to $2$dim is hard). Instead of simply rectangular boards you may consider all such boards with the right columns partially eroded in every possible way. You keep track of all erosions recursively, instead of just one uneroded edge; i.e. you solve your problem not just for the uneroded board but also for all eroded boards (and you get that one in particular). For each $n\ge 2$ one gets the vector $v_n$, which has the set $A$ of all subsets of the $m\times 2$ (sub)board for the indices (indices don't have to be $1\ldots s$), and the vector value for a given index is the number of configurations which leave the index or rather the respective subset of the two last right columns alone. Then one gets an integer (transfer) matrix $X: A\times A\rightarrow\mathbb Z$ (independent on $n$) such that $X\cdot v_n=v_{n+1}$ for every $n=2\ 3\ \ldots$. 

