

A146971


Number of weightn binary n X n matrices that yield the allones matrix after repeatedly changing a 0 having at least two 1neighbors to a 1.


3




OFFSET

1,2


COMMENTS

There is a proof that the minimum initial weight is n which can be summarized in the single word "perimeter".
Can also be described as the number of percolating sets of size n for 2neighbor 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


REFERENCES

Erik D. Demaine, Martin L. Demaine and Helena A. Verrill, "CoinMoving Puzzles", in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 405431, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 2428, 2000.


LINKS

Ivars Peterson, SlidingCoin Puzzles, Science News 163(5), Feb 01, 2003. Description of results in the above paper.


EXAMPLE

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.


PROG

(Python) # see linked program


CROSSREFS



KEYWORD

nonn,more


AUTHOR



EXTENSIONS

Additional term a(8) from Alvaro Begue's Cprogram.  John Tromp, Nov 05 2008
Computed a(9) and a(10) with a 128bitboard based program, the former verifying a result from Alvaro's array based program.  John Tromp, Nov 20 2008


STATUS

approved



