I'm stuck with this question

We have eight $1\times 2$ tiles that each one of them has one $1\times 1$ blue square and one $1\times 1$ red square. We want to cover a $4\times 4$ area with these tiles in a way that every row and every column of this area had exactly $2$ blue and $2$ red $1\times 1$ squares. In how many ways we can do this?

First of all, I tried to find out all possible ways which I can cover a $4\times 4$ square by $1\times 2$ dominoes. If I know all such possibilities, then for each such a covering, by obtaining the number of ways that some one can tiles this dominoes in blue-red squares in the manner that described above, we can get the answer. In the article How Many Ways Can We Tile a Rectangular Chessboard With Dominoes? the writer claims that the number of ways which we can tile a $4\times 4$ rectangle is $36$. But he did not described all this $36$ ways.

The above method is very prolix and also, I need to obtain all the possibilities of covering $4\times 4$ square by $1\times 2$ tiles and for each of such covering, all the ways which can satisfied by the conditions of question. Dose any one know a simpler method?

I should point out that the above question is designed for high school students and so I think it must have a simple solution.

  • 1
    $\begingroup$ It seems unlikely that there will be a "simple" method, since the method for finding the number of domino tilings of an n-by-n square is rather difficult. But it's possible that layering on the "extra" condition where the dominoes have colored squares makes things simpler somehow. $\endgroup$ – Michael Lugo Oct 5 '18 at 18:35
  • 1
    $\begingroup$ There are 36 ways to tile a 4x4 square by dominos. 4x4 is small enough, you can generate them using following algorithm. You first index the unit squares using $(x,y)$ with $0 \le x, y < 4$ and order them in lexicographic order. You then generate the 256 horizontal/vertical combinations of 8 dominos. You add the dominos one by one to the big square by placing the lower left part of domino at the "smallest" unoccupied unit square. If you can do that without hitting existing domino or overflow the big square, you get a valid tiling configuration. BTW, by brute force, the number you seek is 760. $\endgroup$ – achille hui Oct 5 '18 at 19:23
  • 1
    $\begingroup$ The question is now posted also on MathOverflow: The ways of covering a 4×4 square by 1×2 colored dominoes You should probably link the two copies to each other, see the advice on cross-posting given in this answer. $\endgroup$ – Martin Sleziak Oct 25 '18 at 18:46

It actually should not be too bad (if a little tedious) to compute case-by-case with judicious use of symmetry.

I'll use a $4 \times 4$ matrix with entries $b$ (for blue), $r$ (for red) and $\cdot$, to denote the number of tilings of the $\cdot$ spaces given the colours of the $b$ and $r$ spaces. By symmetry, the cases where the top left square is either $b$ or $r$ and either in a horizontal or vertical domino have equal tiling counts, thus

$$ \text{answer} = 4 \pmatrix{b & r & \cdot& \cdot\cr \cdot & \cdot& \cdot& \cdot\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr}$$ Now the other two elements in the top row could either be in one domino (which could be in either orientation, or two vertical dominos, of which the second must be the reverse of the first. By symmetry, these cases with vertical dominos have the same counts. Thus $$ \pmatrix{b & r & \cdot& \cdot\cr \cdot & \cdot& \cdot& \cdot\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr} = \pmatrix{b & r & b& r\cr \cdot & \cdot& \cdot& \cdot\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr} + \pmatrix{b & r & r & b\cr \cdot & \cdot& \cdot& \cdot\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr} + 2 \pmatrix{b & r & r & b\cr \cdot & \cdot & b& r\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr} $$

Next, consider the first term on the right above. The (2,1) entry could be $b$ in a horizontal domino (in which case there must be two $(r,b)$ horizontal dominos below it), or $r$ in a horizontal domino (related by symmetry to the last term above), or $b$ or $r$ in a vertical domino (in either case with a $(r,b)$ horizontal domino below it). Thus $$ \pmatrix{b & r & b& r\cr \cdot & \cdot& \cdot& \cdot\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr} = \pmatrix{b & r & b& r\cr b & r & \cdot& \cdot\cr r &b &\cdot &\cdot\cr r & b& \cdot&\cdot\cr} + \pmatrix{b & r & r & b\cr \cdot & \cdot & b& r\cr\cdot &\cdot &\cdot &\cdot\cr\cdot & \cdot& \cdot&\cdot\cr} + \pmatrix{b & r & b& r\cr b & \cdot& \cdot& \cdot\cr r &\cdot &\cdot &\cdot\cr r & b & \cdot&\cdot\cr} + \pmatrix{b & r & b& r\cr r & \cdot& \cdot& \cdot\cr b &\cdot &\cdot &\cdot\cr r & b & \cdot&\cdot\cr} $$

I'll leave the rest to you...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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