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!)
A146971 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
1, 2, 14, 130, 1615, 23140, 383820, 7006916, 140537609, 3035127766 (list; graph; refs; listen; history; text; internal format)
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 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
REFERENCES
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.
LINKS
József Balogh, Béla Bollobás and Robert Morris, Bootstrap percolation in high dimensions, arXiv:0907.3097 [math.PR], 2009-2010.
József Balogh, Béla Bollobás and Robert Morris, Bootstrap percolation in high dimensions, Combin. Probab. Comput. 19 (2010), no. 5-6, 643-692.
Michael S. Branicky, Python program.
Erik D. Demaine, Martin L. Demaine and Helena A. Verrill, , PDF version of "Coin-Moving Puzzles"
Ivars Peterson, Sliding-Coin 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
Sequence in context: A168658 A235347 A235352 * A246481 A048990 A089602
KEYWORD
nonn,more
AUTHOR
John Tromp, Nov 03 2008
EXTENSIONS
Additional term a(8) from Alvaro Begue's C-program. - John Tromp, Nov 05 2008
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
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 April 12 17:42 EDT 2024. Contains 371635 sequences. (Running on oeis4.)