Take the 2-minute tour ×
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.

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?

share|improve this question
1  
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

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.