Number of possible matrices according to given rule? You want to create a matrix of size MxN using only 0 & 1.
But there is rule-
There must not be any submatrix with its (rows>1 & columns>1) and filled with same number.
For example- 
for a 3x3 matrix- 
0 1 1
1 0 0
1 1 0

is allowed but- 
1 0 0      1 0 1
0 0 0  or  0 1 1
1 1 1      1 1 1

are not allowed. 
How many such matrices of size MxN are possible?
 A: Here's an approach to get recursive formulas for the $n \times 2$ matrix. We use joriki's remark that we only need avoid $2 \times 2$ constant submatrices. For each $n \ge 1$ we define four functions:
$M(n,0)$ is the number of acceptable $n \times 2$ matrices with last row $[0,0],$
$M(n,1)$ is the number of acceptable with last row $[0,1],$
$M(n,2)$ is the number of acceptable with last row $[1,0],$
$M(n,3)$ is the number of acceptable with last row $[1,1].$
Then we have for initial values $M(1,k)=1, 0 \le k \le 3,$ and the recursions
$M(n+1,0)=M(n,1)+M(n,2)+M(n,3),$
$M(n+1,1)=M(n,0)+...+M(n,3),$
$M(n+1,2)=M(n,0)+...+M(n,3),$ and
$M(n+1,3)=M(n,0)+M(n,1)+M(n,2).$
These recursions are based on considering the effect of appending a row to the bottom of an acceptable $n \times 2$ matrix.
The first and last of these have one term omitted, so as not to cause a $2 \times 2$ block of all the same entry. For the middle two cases, there is no way to make a constant block on appending either $[0,1]$ or $[1,0]$ to the bottom of an already acceptable matrix.
There are likely some symmetries that could streamline this recursion, and maybe it could be solved in closed form for this $n \times 2$ case. Of course for the total number of acceptable matrices one adds the $M(n,k)$ for $0 \le k \le 3$.
There is another approach to the $n \times 2$ case which might yield itself to a simple direct closed form answer using combinatorics. Let $x=[0,0],y=[1,1],a=[0,1],b=[1,1]$. Then an equivalent question to the number of acceptable $n \times 2$ matrices is the following: How many strings of length $n$ are there, using the alphabet $x,y,a,b$, in which no two adjacent terms of the string are $x$, and no two adjacent are $y$? I don't offhand have a formula for that, but it seems likely there is one.
