cp's OEIS Frontend

A255936 Number of n X n binary matrices having a contiguous 2 by 2 submatrix whose every element is 1.

%I A255936 #34 Oct 23 2015 03:48:49
%S A255936 0,0,1,95,23360,17853159,47300505935,455725535985152,
%T A255936 16477833186525760257,2285218507961233452756479,
%U A255936 1234874616385516438189472371200,2628743329824106687023439956782224783,22201933512060923158839975337648286975677119
%N A255936 Number of n X n binary matrices having a contiguous 2 by 2 submatrix whose every element is 1.
%C A255936 This sequence is of interest in the theory of 'Reliability in Engineering', where a 2-dimensional m by n array of elements might be considered to have failed if and only if it includes a contiguous r by s rectangle of failed elements. This is an extension of the 1-dimensional problem exemplified by a sequence of pumping stations along a pipeline. In the case where each element fails with probability 1/2, independently of the other elements, computing the probability that the system fails becomes a combinatorial problem.
%H A255936 S. R. Cowell, <a href="http://dx.doi.org/10.1155/2015/140909">A formula for the reliability of a d-dimensional consecutive-k-out-of-n:F system</a>, International Journal of Combinatorics, Vol. 2015, Article ID 140909, 5 pages
%H A255936 <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>
%F A255936 a(n) = A002416(n) - A139810(n). - _Alois P. Heinz_, Mar 11 2015
%F A255936 a(n) = -2^(n^2) Sum_{J a nonempty subset of E} (-1)^|J| Prod_{J' a nonempty subset of J} exp[(-1)^|J'| log(2) max(0, 2-(max_{e in J'} e_1 - min_{e in J'} e_1)) max(0, 2-(max_{e in J'} e_2 - min_{e in J'} e_2))], for n >= 2, where E={1,..,n-1} x {1,..,n-1}. (special case of Corollary 2 in the Cowell reference) - _Simon Cowell_, Sep 07 2015
%t A255936 failurenumber[m_, n_, r_, s_] :=
%t A255936 Module[{numberofnodes, numberofcases, cases, badsubmatrix,
%t A255936    failurecases, i, j},
%t A255936   numberofnodes = m n;
%t A255936   numberofcases = 2^numberofnodes;
%t A255936   cases = Tuples[{0, 1}, {m, n}];
%t A255936   badsubmatrix = Table[1, {r}, {s}];
%t A255936   failurecases =
%t A255936    Parallelize[
%t A255936     Select[cases,
%t A255936      Apply[Or,
%t A255936        Flatten[Table[#[[i ;; i + r - 1, j ;; j + s - 1]] ==
%t A255936           badsubmatrix, {i, 1, m - r + 1}, {j, 1, n - s + 1}]]] &]];
%t A255936   Length[failurecases] ]
%t A255936 failurenumberslist = Map[failurenumber[#1, #1, 2, 2] &, Range[2, 5]]
%Y A255936 Cf. A002416, A139810.
%K A255936 nonn
%O A255936 0,4
%A A255936 _Simon Cowell_, Mar 11 2015
%E A255936 a(6)-a(12) from _Alois P. Heinz_, Mar 11 2015