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

Inspired by some other questions, (this and this), I wonder what numbers $n$ there are that satisfy

$$p(n)=\text{there is no region that admits exactly } n \text{ domino tilings}.$$ If this is true, $n$ is non-realizable, otherwise, it is realizable.

A region in the plane is a union of squares in the unit square grid, and a domino is of course two adjacent unit squares.

Clearly, if $m$ and $n$ are realizable, then so is $mn$.

Note that all powers of $2$ are easily realizable. $2 \times k$-regions have a Fibonacci-number of tilings, so all Fibonacci-numbers are realizable.

Note that there is no restriction on the subset of the plane (it can be disconnected, or have holes). Will the answer be different if the region is simply connected? In the latter case, there is a theorem stating that we can reach each tiling from any other using "flips".

Update: Let $F_k$ be the number of ways to tile a $2 \times k$-rectangle. This is a Fibonacci number, $F_1=1,F_2=2,F_3=3,\dots$.

Consider the Young diagram given by the partition $(k,k,2)$. We can either choose to have a horizontal domino in the third row, which give $F_k$ tilings of the remaining, or the third row is covered by two vertical dominos. The remaining part can then be tiled in exactly $F_{k-2}$ ways. Hence, all numbers of the form $F_k + F_{k-2}$ are realizable. In particular, $7 = 2+5$, and $11 = 3+8$.

We can do a more general construct on the "other end" of a long $2\times k$-shape, and see that all $F_k + F_{k-2}+F_{k-4}$ are realizable whenever $k\geq 4$.

Thus, we are now incredibly close to applying Zeckendorf's theorem.

share|improve this question

3 Answers 3

up vote 14 down vote accepted

To follow up on the answer of dhy, there is a simple construction that works with simply connected regions:

Take a $k\times k$ square with $k\geq 2$. Remove from the bottom left corner a staircase region with rows of $1,2,3,\ldots k-2$ cells, and from the top right corner a (suitably rotated) staircase region with rows of $1,2,3,\ldots k-3$ cells. The remaining region is some sort of fat diagonal of the square having rows with $3,4,4,\ldots,4,3,2$ cells from top to bottom.

It is easily seen that this region has $2k-2$ domino tilings, while the same region with the $2$ cells of the last row removed has $2k-3$ possible tilings.

share|improve this answer
    
Very pleasing construction! –  Per Alexandersson Aug 8 at 12:50
1  
Let's say you have two integers $m<n$. Can you always find a s.c. region $G$ and a domino $D \subset G$, s.t. $G$ has exactly $n$ tilings, but $G-D$ has only $m$? –  Igor Pak Aug 8 at 22:18
1  
@IgorPak: Maybe that should be asked as a separate question? It is a natural generalization! –  Per Alexandersson Aug 8 at 23:33
3  
Removing a suitable domino from the regions I described actually gives a positive answer to Igor's question. –  Philippe Nadeau Aug 9 at 6:34

Consider a $4\times 2k+1$ rectangle. Label its points by $(x,y)$, with $x$ from $0$ to $3$ and $y$ from $0$ to $2k.$ Remove from the rectangle the points $(1,y)$ and $(2,y)$ for $y$ odd. I claim that the resulting region has $k+1$ tilings.

To see this, look at what happens at $(1,2k)$ and $(2,2k).$ If there is no domino containing both points, then it isn't too hard to see that the rest of the tiling is uniquely determined. On the other hand, if $(1,2k)$ and $(2,2k)$ are contained in the same domino, then we are reduced to the same thing for a $4\times 2k-1$ rectangle, so an induction finishes it.

share|improve this answer
    
Ah, very nice! So, the question has a positive answer in the case of non-simply-connected regions. How about simply connected regions? –  Per Alexandersson Aug 8 at 12:19

http://oeis.org/A099390 gives formulas for mxn rectangles. In particular the 3x4 rectangle has 11 tilings.

share|improve this answer

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.