Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a grid of size $3n$, each tile is $1$ unit long and $1$ unit wide. There are bulbs beneath the tiles. Each bulb is responsible for lighting exactly two tiles. No tile should be lighted by more than $1$ bulb and no tiles should be left unlighted. Find the total number of ways of arranging these bulbs.In other words how many ways can two tiles be grouped together in the grid?

For $n=2$, the total number of ways is 3.

For $n=4$, the total number of ways is 11.

What is the general solution?

share|improve this question

1 Answer 1

This is the same as the number of ways to tile a $3\times n$ board ($3$ rows, $n$ columns) $B_n$ with dominos, i.e., $1\times 2$ and $2\times 1$ tiles. Let $t_n$ be the number of such tilings, and let $s_n$ be the number of tilings of $B_n^-$ with dominos, where $B_n^-$ is a $3\times n$ board with the upper lefthand corner cell missing. Clearly $t_n=0$ when $n$ is odd, and $s_n=0$ when $n$ is even.

A tiling of $B_n^-$ must have one of two forms: either the short first column is completely filled by a single vertical domino, in which case the rest of the tiling is a tiling of $B_{n-1}$, or the leftmost three dominos look like this:

$$\begin{array}{|c|c|c|} \hline 0&3&3\\ \hline 1&1\\ \hline 2&2\\ \hline \end{array}$$

Here $0$ is the missing cell, and two cells with the same number are covered by a single domino. In this second case the remaining dominos tile $B_{n-2}^-$. It follows that

$$s_n=t_{n-1}+s_{n-2}\;.\tag{1}$$

A tiling of $B_n$ must have one of three forms: either there is a vertical domino in the first column, in which case it can occupy either the top two or the bottom two cells, or the first two columns must be filled with three horizontal dominos. In the first two cases the remaining dominos tile $B_{n-1}^-$ or an upside-down $B_{n-1}^-$, and in the last case the remaining dominos tile $B_{n-2}$, so $$t_n=2s_{n-1}+t_{n-2}\;.\tag{2}$$

From $(2)$ we get $$s_{n-1}=\frac12(t_n-t_{n-2})$$ and hence $$s_{n-2}=\frac12(t_{n-1}-t_{n-3})\;;$$ substituting this into $(1)$ yields $$s_n=t_{n-1}+\frac12(t_{n-1}-t_{n-3})=\frac32t_{n-1}-\frac12t_{n-3}\;,$$ whence $2s_{n-1}=3t_{n-2}-t_{n-4}$. Substitute this into $(2)$ to find that

$$t_n=4t_{n-2}-t_{n-4}\;.\tag{3}$$

We know that $t_2=3$ and $t_4=11$, so if we set $t_0=1$, $(3)$ is valid for $n\ge 4$.

Since $t_{2n+1}=0$ for all $n\ge 0$, it’s a little more convenient to look at $u_n=t_{2n}$; then $u_0=1$, $u_1=3$, $u_2=11$, and $(3)$ becomes

$$u_n=4u_{n-1}-u_{n-2}\tag{4}$$

for $n\ge 2$. You can now use any of the usual methods to solve $(4)$ for a closed form for $u_n$; one elementary approach starts by finding the roots $\alpha$ and $\beta$ of the characteristic polynomial $x^2=4x-1$. In this case $\alpha\ne\beta$, so you know that $$u_n=A\alpha^n+B\beta^n\tag{5}$$ for some constants $A$ and $B$. You can use $(5)$ and the known values of $u_0$ and $u_1$ to get a system of two linear equations in the unknowns $A$ and $B$. This system will have a unique solution, which you can plug back into $(5)$ to get the desired closed form for $u_n$.

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.