# Сovering a rectangle

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

00
00


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

or

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.

-
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: en.wikipedia.org/wiki/Dimer_model. – 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.
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