Problem

Source: Rioplatense L-2 2022 #6

Tags: combinatorics



Let $N(a,b)$ be the number of ways to cover a table $a \times b$ with domino tiles. Let $M(a,2b+1)$ be the number of ways to cover a table $a \times 2b+1$ with domino tiles, such that there are no vertical tile in the central column. Prove that $$M(2m,2n+1)=2^m \cdot N(2m,n)\cdot N(2m,n-1)$$