

A146971


Number of weightn binary n X n matrices that yield the all1 matrix when repeatedly change a 0 having at least two 1neighbors to a 1.


2




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 2neighbour bootstrap percolation in the n X n grid graph; see Balogh, Bollobás and Morris. The large Schröder numbers A006318 count the number of 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. [From John Tromp, Nov 05 2008]
Ivars Peterson, "SlidingCoin Puzzles", Science News 163(5), Feb 01, 2003 (description of results in the above paper) [From John Tromp, Nov 05 2008]
József Balogh, Béla Bollobás and Robert Morris, "Bootstrap percolation in high dimensions," Combin. Probab. Comput. 19 (2010), no. 56, 643692.


LINKS

Table of n, a(n) for n=1..10.
József Balogh, Béla Bollobás and Robert Morris, Bootstrap percolation in high dimensions, arXiv:0907.3097 [math.PR], 20092010.
Erik D. Demaine, Martin L. Demaine and Helena A. Verrill, , PDF version of "CoinMoving Puzzles" [From John Tromp, Nov 05 2008]
Ivars Peterson, SlidingCoin Puzzles [From John Tromp, Nov 05 2008]


EXAMPLE

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


CROSSREFS

Sequence in context: A168658 A235347 A235352 * A246481 A048990 A089602
Adjacent sequences: A146968 A146969 A146970 * A146972 A146973 A146974


KEYWORD

nonn


AUTHOR

John Tromp, Nov 03 2008


EXTENSIONS

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


STATUS

approved



