login
Number of weight-n binary n X n matrices that yield the all-ones matrix after repeatedly changing a 0 having at least two 1-neighbors to a 1.
3

%I #40 Mar 10 2023 13:15:24

%S 1,2,14,130,1615,23140,383820,7006916,140537609,3035127766

%N Number of weight-n binary n X n matrices that yield the all-ones matrix after repeatedly changing a 0 having at least two 1-neighbors to a 1.

%C There is a proof that the minimum initial weight is n which can be summarized in the single word "perimeter".

%C Can also be described as the number of percolating sets of size n for 2-neighbor bootstrap percolation in the n X n grid graph; see Balogh, Bollobás and Morris. The large Schröder numbers A006318 count the permutation matrices (one 1 in each row and column) having this property. - _Jonathan Noel_, Oct 07 2018

%D Erik D. Demaine, Martin L. Demaine and Helena A. Verrill, "Coin-Moving Puzzles", in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 405-431, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24-28, 2000.

%H József Balogh, Béla Bollobás and Robert Morris, <a href="https://arxiv.org/abs/0907.3097">Bootstrap percolation in high dimensions</a>, arXiv:0907.3097 [math.PR], 2009-2010.

%H József Balogh, Béla Bollobás and Robert Morris, <a href="https://doi.org/10.1017/S0963548310000271">Bootstrap percolation in high dimensions</a>, Combin. Probab. Comput. 19 (2010), no. 5-6, 643-692.

%H Michael S. Branicky, <a href="/A146971/a146971.py.txt">Python program</a>.

%H Erik D. Demaine, Martin L. Demaine and Helena A. Verrill, , <a href="http://erikdemaine.org/papers/GameTheory2000/paper.pdf">PDF version of "Coin-Moving Puzzles"</a>

%H Ivars Peterson, <a href="https://www.sciencenews.org/article/sliding-coin-puzzles">Sliding-Coin Puzzles</a>, Science News 163(5), Feb 01, 2003. Description of results in the above paper.

%e a(3) = 14 because there are 2, 4, 4 and 4 symmetrical versions of 100 010 001, 100 001 010, 101 000 100 and 101 000 010 respectively.

%o (Python) # see linked program

%K nonn,more

%O 1,2

%A _John Tromp_, Nov 03 2008

%E Additional term a(8) from Alvaro Begue's C-program. - _John Tromp_, Nov 05 2008

%E Computed a(9) and a(10) with a 128-bitboard based program, the former verifying a result from Alvaro's array based program. - _John Tromp_, Nov 20 2008