Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
3  
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
1  
Complete tilings amount to partial tilings by $2\times 2$ and $3\times 3$ blocks only. –  Wlodzimierz Holsztynski 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
add comment

1 Answer

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

share|improve this answer
    
The "transfer matrix method" is a useful search term for more information. See, for example, Chapter 4 in Stanley's Enumerative Combinatorics (vol. 1). –  Henry Cohn Jul 3 '13 at 0:43
    
Thank you @Henry for (implicitly or extra politely) correcting my wrong terminology. I'll edit my answer to have "transfer" (in place of the misterm "transition"). In general, due to my circumstances, I rarely provide a reference, and I may use a wrong word (however I rather define them in my posts just like Alice in Wonderland). –  Wlodzimierz Holsztynski Jul 3 '13 at 1:05
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.