Counting Of Binary Matrices Avoiding Some 2 × 2 Matrices

Abstract

The number of matrices avoiding certain types of matrices is NP-hard in general. In this paper the binary matrices are considered. In particular, the problem of finding the total number of special binary matrices avoiding some types of 2 × 2 matrices is the main objective of this paper. The solution of the problem is given under some constraints as well as under general situation. The formula for the special binary matrices is obtained for total count of matrices of order n × k and also obtained the formula for special binary matrices avoiding some matrices of order 2 × 2. The formula is obtained in terms of the Catalan numbers.