1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ How many different types of dominoes are we allowed to use? $\endgroup$
    – DanDan面
    Commented Aug 29, 2023 at 21:16
  • $\begingroup$ @DanDan0101 which question? Assume the dominoes are indistinguishable. $\endgroup$
    – qwr
    Commented Aug 29, 2023 at 21:19
  • $\begingroup$ Bonus. For instance, I can assume every domino has, say, a 1 and a 2 as the two halves? $\endgroup$
    – DanDan面
    Commented Aug 29, 2023 at 21:20
  • 1
    $\begingroup$ @DanDan0101 yes. You could also consider dominoes that are painted one one side and can be flipped over. $\endgroup$
    – qwr
    Commented Aug 29, 2023 at 21:22
  • $\begingroup$ 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 $\endgroup$ Commented Sep 1, 2023 at 13:07

1 Answer 1

3
$\begingroup$

Answer:

$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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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