# The number of combination of placements of square block in 3 different size (1x1, 2x2, 3x3) on a board

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

-
You're asking for partial tilings of a rectangle with squares. Since you're allowed to use $1 \times 1$ squares, any partial tiling can be filled in with those to a complete tiling. So instead you can find all the complete tilings, a.k.a. tilings, and then count the ways to remove $1 \times 1$ squares from them, which is easy. There is much more literature on complete tilings than partial tilings. – Zack Wolske Jul 2 '13 at 16:54
Complete tilings amount to partial tilings by $2\times 2$ and $3\times 3$ blocks only. – Włodzimierz Holsztyński Jul 2 '13 at 18:29
You could try calculating the answer for small values of $m$ and $n$, and then looking up the resulting numbers in the Online Encyclopedia of Integer Sequences. – Gerry Myerson Jul 3 '13 at 1:28

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 2-dimensional Ising model.
Going back to the given question, if one side of the board, let's say   $m$, is relatively small--let'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$.