# Tile 1x2 dominoes in a 2x10 space

How many ways are there to tile unmarked 1x2 dominoes in a 2x10 space?

Bonus: What if the dominoes were identical and had pips on their front (face-up), so they could be distinguished by 180 degree rotation?

• How many different types of dominoes are we allowed to use? Aug 29, 2023 at 21:16
• @DanDan0101 which question? Assume the dominoes are indistinguishable.
– qwr
Aug 29, 2023 at 21:19
• Bonus. For instance, I can assume every domino has, say, a 1 and a 2 as the two halves? Aug 29, 2023 at 21:20
• @DanDan0101 yes. You could also consider dominoes that are painted one one side and can be flipped over.
– qwr
Aug 29, 2023 at 21:22
• Amazingly there is closed solution for counting the number of 1x2 domino tilings of any 2D rectangular grid. It has some very deep and complex connections to statistical mechanics: en.wikipedia.org/wiki/Domino_tiling#Counting_tilings_of_regions Sep 1, 2023 at 13:07

$$89$$ ways

Solution:

Suppose that a $$2\times N$$ space can be tiled in $$f(N)$$ ways.

Clearly, $$f(1)=1$$ and $$f(2)=2$$. For $$N>2$$, we can condition on the state of the leftmost domino. If the leftmost domino is vertical, we are left with a $$2\times(N-1)$$ space to tile, and if the leftmost dominoes are horizontal, we are left with a $$2\times(N-2)$$ space to tile. Hence, our recurrence relation is $$f(N)=f(N-1)+f(N-2)$$. From the initial conditions, we see $$\boxed{f(N)=F_{N+1}}$$, where $$F_i$$ is the $$i^{\text{th}}$$ Fibonacci number.

Bonus:

There are $$N$$ dominoes, and each has two configurations. Accounting for flips, the total arrangements is $$2^Nf(N)=2^NF_{N+1}$$. In the case $$N=10$$, this is $$91136$$ ways.

Bonus, alternate solution:

Suppose that a $$2\times N$$ space can be tiled in $$g(N)$$ ways with identical painted dominoes. We proceed as before.

Clearly, $$g(1)=2$$ and $$g(2)=8$$. Condition on the state of the leftmost domino. If it is vertical, it could be in state $$\uparrow$$ or $$\downarrow$$. If it is horizontal, the two leftmost dominoes could be in state $$\uparrow\uparrow$$, $$\uparrow\downarrow$$, $$\downarrow\uparrow$$, and $$\downarrow\downarrow$$. Our new recurrence is $$g(N)=2g(N-1)+4g(N-2)$$. A simple proof by strong induction suffices to show that $$g(N)=2^Nf(N)$$.

Proof:

The base cases are trivial, $$g(1)=2=2^1f(1)$$ and $$g(2)=8=2^2f(2)$$. Make the inductive hypothesis that $$g(N)=2^Nf(N)$$. Now, \begin{align}g(N+1)&=2g(N)+4g(N-1)\\&=2\cdot2^Nf(N)+4\cdot2^{N-1}f(N-1)\\&=2^{N+1}(f(N)+f(N-1))\\&=2^{N+1}f(N+1)\end{align} $$\blacksquare$$

• Well done! I'll have to make my counting problems harder.
– qwr
Aug 29, 2023 at 21:25
• The idea of the bonus was to find a different recurrence, but your method works as well.
– qwr
Aug 29, 2023 at 21:29
• @qwr I've added the recurrence! Aug 29, 2023 at 21:37