Domino problem

I have found the generating formula of $A_n$ = $A_{n-1}$+$2A_{n-2}$+$2A_{n-3}$+$2A_{n-4}$+$2A_{n-5}$ and I have found $B_n$=$A_{n-2}$+$2A_{n-3}$+$2A_{n-4}$+$2A_{n-5}$ (I think my formula for $B_n$ is probably wrong) I'm wondering if anyone can show me how to get to the formula $A_n$=$2A_{n-1}$+$A_{n-3}$ because I am quite lost. Any help would be appreciated

  • $\begingroup$ Please explain how you get your formulas for $A_n$ and $B_n$. I don't see how these can be true. The formula for $A_n$ suggests that we always have a $2\times m$ rectangle on the left or right, but this isn't so. I can start with an L-shaped piece on the left, then put straight pieces in like bricks in a wall for as long as I like, and finish off with the opposite L-shaped piece. There is no tiled sub-rectangle. Am I overlooking something? $\endgroup$
    – saulspatz
    May 12, 2020 at 14:10
  • $\begingroup$ I have taken the liberty to change your title into a more significant one in order to convey the main ideas (the former word "domino" was misleading, especialy because there is anotheer L shape wich has definitely not the shape of a domino). $\endgroup$
    – Jean Marie
    May 12, 2020 at 15:23

1 Answer 1


Let $n\geq 2$. For any division of the $2\times n$ rectangle or the $n+(n+1)$ blocks, removing the leftmost pieces (either a vertical domino, and L shape, or two horizontal dominos) gives another shape whose number of divisions is known. More specifically, I got $$A_n=A_{n-1}+2B_{n-2}+A_{n-2},\\ B_n=B_{n-1}+A_{n-1}.$$ Here are the details:

For a $2\times n$ rectangle: if the leftmost piece is a vertical domino, then removing it gives a $2\times(n-1)$ rectangle; if the leftmost piece is an L shape then it can either be L or $\Gamma$, and removing it gives a $(n-2)+(n-1)$ shape; and if the leftmost pieces are two horizontal dominos, then removing them gives a $2\times (n-2)$ rectangle.

For a $n+(n+1)$ shape: if the leftmost piece is a domino (half of it is sticking out), then removing it gives a $n+(n-1)$ shape; if the leftmost piece is an L shape (but backwards), then removing it gives a $2\times (n-1)$ rectangle.

Using these two formulae and basic arithmetic on generating functions, we can obtain $A(t)=2tA(t)+t^3A(t)$, which gives us the desired relation. If you want, I can explicit these calculations as well.

Calculating $A(t)$

We will be using the fact that two sequences $(x_n)_n$ and $(y_n)_n$ are equal iff the formal generating series $\sum x_nt^n$ and $\sum y_nt^n$ are equal, and that $t\sum x_nt^n$ corresponds to the sequence $(x_{n-1})_n$, with $x_{-1}=0$.

First, $B(t)=tB(t)+tA(t)+B_0$ and $B_0=0$, so $B(t)=\frac{t}{1-t}A(t)$. Therefore $$\begin{aligned} A(t)&=tA(t)+t^2A(t)+2t^2B(t)+A_0\\ &=\left(t+t^2+2t^2\frac t{1-t}\right)A(t)+A_0\\ &=\frac{t+t^3}{1-t}A(t)+A_0, \end{aligned}$$ so $$(1-t)A(t)=(t+t^3)A(t)+(1-t)A_0,$$ so $$A(t)=2tA(t)+t^3A(t)+(1-t)A_0,$$ so for all $n\geq 3$, $A_n=2A_{n-1}+A_{n-3}$.

  • $\begingroup$ Please indicate how to get $A(t)$. I got the formulas for $A_n$ and $B_n$ myself, but haven't been able to get any further. $\endgroup$
    – saulspatz
    May 12, 2020 at 14:22
  • $\begingroup$ @saulspatz I added my calculations. I'm don't do generating series that often, so maybe I made a mistake. $\endgroup$
    – Isaac Ren
    May 12, 2020 at 14:38
  • 1
    $\begingroup$ Looks right to me. Thanks. $\endgroup$
    – saulspatz
    May 12, 2020 at 15:01
  • 1
    $\begingroup$ A very good text on enumerative combinatorics addressing as well this kind of issues : arxiv.org/pdf/1409.2562.pdf $\endgroup$
    – Jean Marie
    May 12, 2020 at 15:19
  • 1
    $\begingroup$ see the same question here and here. $\endgroup$
    – Jean Marie
    May 12, 2020 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy