Given m & n, we have to find out the number of possible matrices of order m\*n with the property that A(i,j) can be either 0 or 1 and that no contiguous sub-matrix of both length > 1 & breadth > 1 should have same entries i.e. all of its cells shouldn't be 0 or 1. For example if m = 2 & n = 2, the answer is 14: Total possibilities : 2 ^ (2 \* 2); Invalid cases: when all 4 cells are 0 or 1. Therefore answer is 2 ^ (2 \* 2) - 2 = 14. A sub-matrix of length > 1 & breadth = 1, also breadth > 1 & length = 1 is valid.



How many matrices are possible for the given arrangement?
Let $a\_n$ be the number of $2 \times n$ -matrices avoiding constant 2\*2-submatrices.
Then 


$$a\_n = \frac{2^{-n} \left(4 \left(17+4 \sqrt{17}\right)
 \left(3+\sqrt{17}\right)^n+\left(\sqrt{17}-17\right)
 \left(\sqrt{17}-3\right)^n e^{i \pi n}\right)}{17
 \left(3+\sqrt{17}\right)}$$


This should be fairly straightforward to prove,
let $v(n)=(e\_{01}(n),e\_{10}(n),e\_{00}(n),e\_{11}(n))$ be the vector of number of $2\times n$-matrices ending with column 01, 10, 00 resp. 11.


We then have the recursion
$$v(n+1)=\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \end{pmatrix} v(n)$$


Since this is symmetric, we may diagonalize this and from here, it should be straightforward to find the formula above.
(I cheated a bit in Mathematica).


EDIT: Of course, $e\_{01}(n)=e\_{10}(n)$ and $e\_{00}(n)=e\_{11}(n)$ by symmetry,
so one can of course reduce the above to a 2 by 2 matrix recursion instead, with entries 2,2 and 2,1. Eigenvalues of this matrix are $1/2 (3 + \sqrt{17}), 1/2 (3 - \sqrt{17})$
which explains the strange formula above.


