In how many ways can you cover a 3xN grid with 2x1 dominoes?

Interesting problems tend to follow a pattern of being very easy to state, and hard to solve. I am sharing one as an example. Do try to solve it before reading through the solution. Enjoy!

Problem

In how many ways can you cover a $3\times n$ grid with $2\times 1$ sized dominoes?

Solution

Approach

We will write the number of solutions recursively, and deduce the general formula based on this.

Recursions

After adding dominoes we get grids that might not be $3\times n$, so let us define these three values:

• $A_n$ : The number of coverings of a $3\times n$ grid with an extra cell in the $n+1$ th column.
• $B_n$ : The number of coverings of a $3\times n$ grid with two extra adjacent cells in the $n+1$ th column.
• $C_n$ : The number of coverings of a $3\times (n+1)$ grid.

With these in mind, we get three key recursions:

$$\{\begin{array}{cc}{A}_n=& B_{n-1}\\ B_n=& C_{n-1}+A_{n-1}\\ C_n=& B_{n-1}+C_{n-2}+A_n\end{array}$$

Using $A_n=B_{n-1}$ to get rid of all the $A_n$ terms we get the system of equations

$$\{\begin{array}{cc}{B}_n=& C_{n-1}+B_{n-2}\\ C_n=& 2B_{n-1}+C_{n-2}\end{array}$$

In order to get similar recursions, we can define $C_n^{\prime }=\sqrt{2}{C}_n$ to get the system of equations.

$$\{\begin{array}{cc}{B}_n=& \sqrt{2}{C}_{n-1}^{\prime }+B_{n-2}\\ C_n^{\prime }=& \sqrt{2}{B}_{n-1}+C_{n-2}^{\prime }\end{array}$$

Due to $B_n$ and $C_n^{\prime }$ ‘s similarity, we can work out this system in terms of their average value and difference, by setting

$$\{\begin{array}{cc}{\alpha }_n=& \frac{B_n+C_n^{\prime }}{2}\\ {\beta }_n=& \frac{B_n-C_n^{\prime }}{2}\end{array}⟺\{\begin{array}{cc}{B}_n=& {\alpha }_n+{\beta }_n\\ C_n^{\prime }=& {\alpha }_n-{\beta }_n\end{array}$$

Substituting back in the original equations we get

$$\begin{array}{rl}& \{\begin{array}{cc}{B}_n=& \sqrt{2}{C}_{n-1}^{\prime }+B_{n-2}\\ C_n^{\prime }=& \sqrt{2}{B}_{n-1}+C_{n-2}^{\prime }\end{array}\\ & \\ & \{\begin{array}{cc}{\alpha }_n+{\beta }_n=& \sqrt{2}\left({\alpha }_{n-1}-{\beta }_{n-1}\right)+\left({\alpha }_{n-2}+{\beta }_{n-2}\right)\\ {\alpha }_n-{\beta }_n=& \sqrt{2}\left({\alpha }_{n-1}+{\beta }_{n-1}\right)+\left({\alpha }_{n-2}-{\beta }_{n-2}\right)\end{array}\\ & \\ & \{\begin{array}{cc}{\alpha }_n=& \sqrt{2}{\alpha }_{n-1}+{\alpha }_{n-2}\\ {\beta }_n=-& \sqrt{2}{\beta }_{n-1}+{\beta }_{n-2}\end{array}\end{array}$$

These 2 equations are independent of each other and simple to solve using the Difference Equations methodology

• ${\alpha }_n$: Solving ${\alpha }^2=\sqrt{2}\alpha +1$ we get $\alpha =\frac{1\pm \sqrt{3}}{\sqrt{2}}$, which leads to the general solution ${\alpha }_n=r{\left(\frac{1+\sqrt{3}}{\sqrt{2}}\right)}^n+s{\left(\frac{1-\sqrt{3}}{\sqrt{2}}\right)}^n$.
• ${\beta }_n$: Solving ${\beta }^2=-\sqrt{2}\beta +1$ we get $\beta =\frac{-1\pm \sqrt{3}}{\sqrt{2}}$, which leads to the general solution ${\beta }_n=t{\left(\frac{-1+\sqrt{3}}{\sqrt{2}}\right)}^n+u{\left(\frac{-1-\sqrt{3}}{\sqrt{2}}\right)}^n$.

With these general formulas, we can get

$$\begin{array}{rl}{B}_n& ={\alpha }_n+{\beta }_n=\\ & =r{\left(\frac{1+\sqrt{3}}{\sqrt{2}}\right)}^n+s{\left(\frac{1-\sqrt{3}}{\sqrt{2}}\right)}^n+t{\left(\frac{-1+\sqrt{3}}{\sqrt{2}}\right)}^n+u{\left(\frac{-1-\sqrt{3}}{\sqrt{2}}\right)}^n\\ C_n& =\sqrt{2}{C}_n^{\prime }=\\ & =\sqrt{2}\left({\alpha }_n-{\beta }_n\right)=\\ & =\sqrt{2}\left(r{\left(\frac{1+\sqrt{3}}{\sqrt{2}}\right)}^n+s{\left(\frac{1-\sqrt{3}}{\sqrt{2}}\right)}^n-t{\left(\frac{-1+\sqrt{3}}{\sqrt{2}}\right)}^n-u{\left(\frac{-1-\sqrt{3}}{\sqrt{2}}\right)}^n\right)\end{array}$$

The final step is to find the values of $r$, $s$, $t$ and $u$. For that we need to figure out basecases, namely:

$$\{\begin{array}{ccc}{B}_0& =& 1\\ C_0& =& 0\\ B_1& =& 1\\ C_1& =& 3\end{array}$$ $$\{\begin{array}{ccc}r+s+t+u& =& 1\\ \sqrt{2}\left(r+s-t-u\right)& =& 0\\ r\frac{1+\sqrt{3}}{\sqrt{2}}+s\frac{1-\sqrt{3}}{\sqrt{2}}+t\frac{-1+\sqrt{3}}{\sqrt{2}}+u\frac{-1-\sqrt{3}}{\sqrt{2}}& =& 1\\ \sqrt{2}\left(r\frac{1+\sqrt{3}}{\sqrt{2}}+s\frac{1-\sqrt{3}}{\sqrt{2}}-t\frac{-1+\sqrt{3}}{\sqrt{2}}-u\frac{-1-\sqrt{3}}{\sqrt{2}}\right)& =& 3\end{array}$$ $$\{\begin{array}{ccc}r+s& =& \frac{1}{2}\\ t+u& =& \frac{1}{2}\\ (r+s)\frac{1}{\sqrt{2}}+(r-s)\frac{\sqrt{3}}{\sqrt{2}}+(t+u)\frac{-1}{\sqrt{2}}+(t-u)\frac{\sqrt{3}}{\sqrt{2}}& =& 1\\ (r+s)-(r-s)\sqrt{3}+(t+u)-(t-u)\sqrt{3}& =& 3\end{array}$$ $$\{\begin{array}{ccc}r+s& =& \frac{1}{2}\\ t+u& =& \frac{1}{2}\\ \frac{1}{2}\frac{1}{\sqrt{2}}+(r-s)\frac{\sqrt{3}}{\sqrt{2}}+\frac{1}{2}\frac{-1}{\sqrt{2}}+(t-u)\frac{\sqrt{3}}{\sqrt{2}}& =& 1\\ 1+((r-s)-(t-u))\sqrt{3}& =& 3\end{array}$$ $$\{\begin{array}{ccc}r+s& =& \frac{1}{2}\\ t+u& =& \frac{1}{2}\\ (r-s)\frac{\sqrt{3}}{\sqrt{2}}+(t-u)\frac{\sqrt{3}}{\sqrt{2}}& =& 1\\ ((r-s)-(t-u))\sqrt{3}& =& 2\end{array}$$ $$\{\begin{array}{ccc}r+s& =& \frac{1}{2}\\ t+u& =& \frac{1}{2}\\ (r-s)\frac{\sqrt{3}}{\sqrt{2}}+(t-u)\frac{\sqrt{3}}{\sqrt{2}}& =& 1\\ (r-s)-(t-u)& =& \frac{2}{\sqrt{3}}\end{array}$$ $$\{\begin{array}{ccc}r+s& =& \frac{1}{2}\\ t+u& =& \frac{1}{2}\\ (r-s)+(t-u)& =& \frac{\sqrt{2}}{\sqrt{3}}\\ (r-s)-(t-u)& =& \frac{2}{\sqrt{3}}\end{array}$$ $$\{\begin{array}{ccc}r+s& =& \frac{1}{2}\\ t+u& =& \frac{1}{2}\\ r-s& =& \frac{1}{\sqrt{6}}+\frac{1}{\sqrt{3}}\\ t-u& =& \frac{1}{\sqrt{6}}-\frac{1}{\sqrt{3}}\end{array}$$ $$\{\begin{array}{ccc}r& =& \frac{1}{4}+\frac{1}{2\sqrt{6}}+\frac{1}{2\sqrt{3}}\\ s& =& \frac{1}{4}-\frac{1}{2\sqrt{6}}-\frac{1}{2\sqrt{3}}\\ t& =& \frac{1}{4}+\frac{1}{2\sqrt{6}}-\frac{1}{2\sqrt{3}}\\ u& =& \frac{1}{4}-\frac{1}{2\sqrt{6}}+\frac{1}{2\sqrt{3}}\end{array}$$

Assembling all of this together we get that $C_n$ equals the sum of the four terms

$$\begin{gathered} C_n=\sqrt{2}\left(\left(\frac{1}{4}+\frac{1}{2\sqrt{6}}+\frac{1}{2\sqrt{3}}\right){\left(\frac{1+\sqrt{3}}{\sqrt{2}}\right)}^n \\ +\sqrt{2}\left(\frac{1}{4}-\frac{1}{2\sqrt{6}}-\frac{1}{2\sqrt{3}}\right){\left(\frac{1-\sqrt{3}}{\sqrt{2}}\right)}^n \\ -\sqrt{2}\left(\frac{1}{4}+\frac{1}{2\sqrt{6}}-\frac{1}{2\sqrt{3}}\right){\left(\frac{-1+\sqrt{3}}{\sqrt{2}}\right)}^n \\ -\sqrt{2}\left(\frac{1}{4}-\frac{1}{2\sqrt{6}}+\frac{1}{2\sqrt{3}}\right){\left(\frac{-1-\sqrt{3}}{\sqrt{2}}\right)}^n\right) \end{gathered}$$

Since $C_n$ is the number of solutions of a $3\times (n+1)$ grid, our answer is

Answer

$$\begin{gathered} \sqrt{2}\left(\left(\frac{1}{4}+\frac{1}{2\sqrt{6}}+\frac{1}{2\sqrt{3}}\right){\left(\frac{1+\sqrt{3}}{\sqrt{2}}\right)}^{n-1} \\ +\left(\frac{1}{4}-\frac{1}{2\sqrt{6}}-\frac{1}{2\sqrt{3}}\right){\left(\frac{1-\sqrt{3}}{\sqrt{2}}\right)}^{n-1} \\ -\left(\frac{1}{4}+\frac{1}{2\sqrt{6}}-\frac{1}{2\sqrt{3}}\right){\left(\frac{-1+\sqrt{3}}{\sqrt{2}}\right)}^{n-1} \\ -\left(\frac{1}{4}-\frac{1}{2\sqrt{6}}+\frac{1}{2\sqrt{3}}\right){\left(\frac{-1-\sqrt{3}}{\sqrt{2}}\right)}^{n-1}\right) \end{gathered}$$