Placing $t$ horizontal dominoes in a $2 \times n$ table with some restrictions

Question

Given positive integers $n$ and $t$ find the number of ways to place $t$ horizontal dominoes in a $2\times n$ table so that no two dominoes form a $2\times 2$ square and no $2\times 3$ rectangle contains two dominoes such that the one in the upper row has occupied the middle and the rightmost cell and the one in the lower row has occupied the middle and the leftmost cell.

Apart from $A(n,1) = 2(n-1)$ and $A(n,t) = 0$ for $t\geq n$ I have no further good ideas. Perhaps some recursion (hopefully with not too many equations to manipulate)?

Any help appreciated!

Answer 1

For convenience, let's say that Rule 1 is that there are no 2 dominoes forming a 2x2 square and Rule 2 is that there are no two dominoes forming the upper right and lower left corners of a 2x3 square.

Let us consider an arbitrary acceptable arrangement of a $2\times n$ square with $t$ horizontal dominoes. As I see it, there are four distinct possibilities:

• The rightmost column has no dominoes in it. There are $A(n-1,t)$ of these.
• There is a domino in the rightmost two squares of the top row. There is no domino in the rightmost square of the bottom row (by Rule 1) or the second right-most square (by Rule 2), so there are $A(n-2,t-1)$ of these.
• There is a domino in the rightmost two squares of the bottom row. There is no domino in the rightmost square of the top row (by Rule 1).
  • There are $A(n-2,t-1)$ arrangements where there is no domino in the second rightmost square of the top row.
  • There could be a domino in the second and third rightmost squares of the top row without violating Rule 2. However, there could not be a domino in the third rightmost square of the bottom row, because that domino and the second one would violate Rule 2. Therefore, there are $A(n-3,t-2)$ of these.

In all, our recursion formula is $$A(n,t)=A(n-1,t)+2A(n-2,t-1)+A(n-3,t-2)$$

As for the base cases, I think that all you would need are $A(0,0)=1$ and $A(0,t)=A(1,t)=0$ for all $t>0$, but I could be missing something.

Answer 2

We can prove the recurrence:

$$ A(n,t) = A(n-1,t) + 2A(n-2,t-1) + A(n-3,t-2),\\\tag{$n\ge 1\text{ or }t\ge 1$} A(0,0)=1.\hspace{3.25in} $$

by considering all possibilities for what the left end of a tiling looks like, and the number of ways to complete each to a legal tiling, as shown below:

To solve this recurrence, let $F(x,y)=\sum_{n,t\ge 0}A(n,t)x^ny^t$ be the two variable generating function for $A(n,t)$. The recurrence relation implies the generating function equation $$ F(x,y) = 1+xF(x,y) + 2x^2yF(x,y) + x^3y^2F(x,y) $$ which implies $$ F(x,y) = \frac1{1-(x+2x^2y+x^3y^2)}=\frac1{1-x(1+xy)^2}=\sum_{m\ge 0}\big(x(1+xy)^2\big)^m=\sum_{m\ge 0}\sum_{k=0}^{2m} \binom{2m}kx^{m+k}y^k $$ Finally, the coefficient of $x^ny^t$ in $F(x,y)$ is obtained by setting $k=t$ and $m=n-t$ in the last summation, for which the accompanying coefficient is $$\boxed{A(n,t)=\binom{2(n-t)}t.}$$

---

With this hindsight, we can now derive a combinatorial proof of this formula. To choose a tiling of a $2\times n$ board with $t$ dominos, label the first $n-t$ columns of the board from $1$ to $2(n-t)$ as shown below. Then, select $t$ squares from the first $2(n-t)$ columns, which can be done in $\binom{2(n-t)}{t}$ ways. Next, for each $k=1,2,\dots,t$, take the selected square with the $k^{th}$ smallest label, and move it $k-1$ squares to the right. Finally, place the left end of a domino covering each of the selected squares.

$$ \begin{array}{|c|c|c|c} \hline 1&3&5&\dots\\\hline 2&4&6&\dots \\\hline \end{array} $$

Here is an example with $n=8$ and $t=4$. The first picture shows the squares selected arbitrarily from the first $n-t=4$ columns, and the second picture shows the resulting tiling.

Answer 3

Here's a combinatorial proof that $A(n,t)=\binom{2(n-t)}{t}$. Let $X = \{1,\dots,n−t\}$ and $Y = \{H,L\}$. Then $|X \times Y| = 2(n−t)$. Choose a $t$-subset $\{(x_i,y_i): i = 1,\dots,t\}$, listed lexicographically for convenience. The corresponding domino arrangement has domino $i$ starting in column $x_i + i − 1$ in either the High or Low position, according to $y_i$. The $+i−1$ ensures that the dominoes don’t overlap. Also, if $x_i = x_{i+1}$, we must have $y_i = H$ and $y_{i+1} = L$, by the lexicographic convention. In that case, we get two dominoes in columns $x_i + i−1$ through $x_i + i + 1$. The inverse mapping is clear: to recover $x_i$, just subtract $i−1$ from the starting column of domino $i$, and $y_i$ is $H$ or $L$, according to whether domino $i$ is High or Low.