This is a classical question:

How many pavements of an $m\times n$ board (such that $mn$ is even) with $1\times 2$ and $2\times 1$ tiles?

There are several beautiful results and articles related to this. If you aren't familiar with the problem, read this and this (there are many results and refferences and proofs). The main thing I want to focus on is the formula for the number of such tilings:

For an $m\times n$ board with $m$ even (WLOG), we have $$\prod_{k=1}^{\frac{1}{2}m}\prod_{l=1}^{n}2\sqrt{\cos^2{\frac{k\pi}{m+1}}+\cos^2{\frac{l\pi}{n+1}}}$$

$\text{My question}$

However, I want to ask this:

Suppose we place one $1\times 2$ tile (or $2\times 1$ tile) on an $m\times n$ board (such that $mn$ is even) and call it $\mathcal{T}$. How many pavements with $1\times2$ and $2\times1$ tiles are there, which contain $\mathcal{T}$. Lets call this number $f(\mathcal{T})$

This seems very hard. To begin with, analysing some small cases, like $2\times 3$ and $4\times 4$ boards, different $\mathcal{T}$s lead to different $f(\mathcal{T})$s. However, on the plus side, Using complex numbers mathematicians have developed some pretty powerful methods of controlling tilings and configurations.

Of course this can be both generalized to more $\mathcal{T}$s (which is very unlikely however) and reduced to special cases such as $2n\times 2n$ boards or $2\times n$ boards (well, this $2\times n$ case is actually really simple using induction) . Any progress upon the problem is appreciated! I highly belive that a beautiful result awaits in the $2n\times 2n$ case, as for the general case.

I am not a specialist in combinatorics or pavements and sincerely apologize for not providing more context. However, will continue to try to solve this and post updates if I find anything.

Thank you!

P.S. If anyone can code a program to find the number of such tilings for a constant tile $\mathcal{T}$ which we can input, it would help a lot and I count it as an accepted answer, unless someone shows up with a proof.

  • 1
    $\begingroup$ I would suggest to generate some numbers here and use that to get ideas. For example, does the answer depend on T or is it independent? Next, try putting some sequences into OEIS to get an idea for a possible formula. Both is not guaranteed to get results, but would be steps to take when you don't have an idea yet of how the structure of these numbers might look like. $\endgroup$ – Dirk Oct 7 '20 at 11:40
  • $\begingroup$ It is pretty hard to count configuartions by hand. I indeed stated that $f(\mathcal{T})$ depends on $\mathcal{T}$. Maybe someone with some programming knowledge might help. $\endgroup$ – user799688 Oct 7 '20 at 16:31

Here are some sample tilings of $2\times3$ and $4\times4$ tilings. Beside each, is a suggestion of the variations of that figure with counts. At this point, I believe there is an error and that the rotation counts for the top and bottom $4\times4$ figures should be $4$ since there are $2$ variations for each shift indicated. This would mean, for example that the total variations of the $4\times4$ figure are $4^4 + 2 + 4^4=514$ tilings.

Update: A few minutes after posting, I see clarification needed for the shifting statement. For these shifts, only $4$ of the $8$ tiles may be shifted at once and, for the upper right board, a shift of the middle tiles may be accompanied by a rotation making the total $1028$ or $2056$

enter image description here

  • $\begingroup$ Thank you for providing me with some models. However, I know how many tilings there are in total for an $m\times n$ rectangle. I was asking how many are there that include a ceratin domino. Let me explain it once more: You place down a domino and the count all the other tilings of the board that include that specific domino. Thank you again for the model. I will make a sample for $2\times 3$ to showcase my question more clearly. $\endgroup$ – user799688 Oct 12 '20 at 18:55
  • $\begingroup$ You believe there is an error? Why did you post it then? $\endgroup$ – TonyK Oct 12 '20 at 18:58
  • $\begingroup$ @TonyK I posted because I had stupidly quit the spreadsheet I was using to make the drawing without saving. It would have taken me 15-20 minutes to re-do. Sorry. $\endgroup$ – poetasis Oct 12 '20 at 19:05
  • $\begingroup$ No worries. Thank you for the ehlp anyways $\endgroup$ – user799688 Oct 15 '20 at 16:18

Your Answer

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