login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A255936 Number of n X n binary matrices having a contiguous 2 by 2 submatrix whose every element is 1. 0
0, 0, 1, 95, 23360, 17853159, 47300505935, 455725535985152, 16477833186525760257, 2285218507961233452756479, 1234874616385516438189472371200, 2628743329824106687023439956782224783, 22201933512060923158839975337648286975677119 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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.

LINKS

Table of n, a(n) for n=0..12.

S. R. Cowell, A formula for the reliability of a d-dimensional consecutive-k-out-of-n:F system, International Journal of Combinatorics, Vol. 2015, Article ID 140909, 5 pages

Index entries for sequences related to binary matrices

FORMULA

a(n) = A002416(n) - A139810(n). - Alois P. Heinz, Mar 11 2015

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

MATHEMATICA

failurenumber[m_, n_, r_, s_] :=

Module[{numberofnodes, numberofcases, cases, badsubmatrix,

   failurecases, i, j},

  numberofnodes = m n;

  numberofcases = 2^numberofnodes;

  cases = Tuples[{0, 1}, {m, n}];

  badsubmatrix = Table[1, {r}, {s}];

  failurecases =

   Parallelize[

    Select[cases,

     Apply[Or,

       Flatten[Table[#[[i ;; i + r - 1, j ;; j + s - 1]] ==

          badsubmatrix, {i, 1, m - r + 1}, {j, 1, n - s + 1}]]] &]];

  Length[failurecases] ]

failurenumberslist = Map[failurenumber[#1, #1, 2, 2] &, Range[2, 5]]

CROSSREFS

Cf. A002416, A139810.

Sequence in context: A017811 A017758 A203342 * A203187 A103281 A266173

Adjacent sequences:  A255933 A255934 A255935 * A255937 A255938 A255939

KEYWORD

nonn

AUTHOR

Simon Cowell, Mar 11 2015

EXTENSIONS

a(6)-a(12) from Alois P. Heinz, Mar 11 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 25 09:38 EDT 2022. Contains 354835 sequences. (Running on oeis4.)