2
$\begingroup$

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?

  • 0
    Do you have any approach for 2x2 submatrix?2012-11-04

1 Answers 1

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.