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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a rectangle $X × Y$ for $X = 2, Y = 2$:


This is $2^{XY}$ of its varieties:

00 00 00 00 01 01 01 01 10 10 10 10 11 11 11 11
00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11
+  -  -  +  -  +  -  -  -  -  +  -  +  -  -  +

How to find the number of rectangles that can be covered completely?

$X \in [3, 6]$; $Y \in [1, 1000]; X, Y \in \mathbb{N}$

Covering domino means replacing two adjacent horizontally or vertically 0 by 1. Example:

00 => 11
01    01


00 => 10
01    11

The rectangle covered with a dominoes if in the end it will only consist of 1.

Barry Cipra gave the correct answer, but it is not complete.

share|cite|improve this question
Your question is not very clear, could you define "covered with a domino"? In my intuitive understading, the 7th case and 10th case (diagonal 1s) are covered with dominoes. But unless you define it explicitly one can't be sure about it. – rewritten Jan 9 '14 at 10:59
Covering domino means replacing two adjacent 0 horizontally or vertically by 1. – user3164559 Jan 9 '14 at 11:03
Ok so you have a partially occupied area, and you want to complete the occupancy using 2x1 rectangles. The confusion arises because usually when one talks about bi-valued boards and domino pieces, it's normally related to coloring and to cover the board matching the colors. You should edit your question by explaining it better. – rewritten Jan 9 '14 at 11:06
Look here: – Christian Blatter Jan 9 '14 at 11:08
The OP is interested in whether there is any covering, not in the number of them. In any case, from the wikipedia article, it seems a very hard problem. – rewritten Jan 9 '14 at 11:10

This is more of a long comment than an answer, but I hope it helps. If I understand the OP's question correctly, the problem can be described this way: Cover the squares of an $m\times n$ chessboard completely with coins and dominoes. Then remove the dominoes and consider only the pattern of coins. As a function of $m$ and $n$, how many different such patterns are possible?

Call this function $P(m,n)$. The OP's example shows that $P(2,2)=6$. It's easy to see that the sequence $P(1,n)$ is the Fibonacci sequence $1,2,3,5,8,\dots$. For $m=2$, I get $P(2,n)=2\cdot3^{n-1}$ in general, from the following recursion:

$$\begin{align} P(2,n)&=2P(2,n-1)+2Q(2,n-1)\\ Q(2,n)&=P(2,n-1)+Q(2,n-1)\\ \end{align}$$

with $P(2,1)=2$ and $Q(2,1)=1$. The sequence $Q(2,n)$ counts the number of patterns with a coin in the lower right hand corner. I hope someone will doublecheck this.

share|cite|improve this answer
That's right! I came to this earlier, but I can not continue for $m = 3, 4, 5, 6 $ – user3164559 Jan 9 '14 at 13:25
For $m=3$, may be a sequence is 3, 18, 98, ... My methods are based on intuition, for the correct solution I can not find ideas. – user3164559 Jan 9 '14 at 17:02

Your Answer


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.