# 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?

-
Does a submatrix have consecutive rows and columns, or just any? Also, isn't the condition equivalent to the simpler condition that there must not be a constant $2\times2$ submatrix? – joriki Nov 4 '12 at 14:51
submatrix have consecutive rows and columns. Its not similar to that, because there might be a 2x3 matrix in above example which has same number. – user1437473 Nov 4 '12 at 15:00
I don't understand. How can there be a constant $2\times3$ matrix without there being a constant $2\times2$ matrix? – joriki Nov 4 '12 at 15:12
Sorry I didnt get your point at that time. Yes i think problem can be reduced to 2x2 submatrix. – user1437473 Nov 4 '12 at 15:18
Do you have any approach for 2x2 submatrix? – user1437473 Nov 4 '12 at 15:19

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.

-