What exact number of domino tilings cannot be realizable?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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