A075462 a(n) is the number of solutions to the all-ones lights out problem on an n X n square.

1, 1, 1, 16, 4, 1, 1, 1, 256, 1, 64, 1, 1, 16, 1, 256, 4, 1, 65536, 1, 1, 1, 16384, 16, 1, 1, 1, 1, 1024, 1048576, 1, 1048576, 65536, 16, 64, 1, 1, 1, 4294967296, 1, 4, 1, 1, 16, 1, 1, 1073741824, 1, 256, 256, 1, 1, 4, 16, 1, 1, 1, 1, 4194304, 1, 1099511627776, 16777216

Offset

1,4

Comments

In these counts, nonidentical reflected and rotated solutions are considered distinct.

References

Caro, Y., Simple proofs to three parity theorems, Ars Combin. 42 (1996), 175-180.

Conlon, M. M.; Falidas, M.; Forde, M. J.; Kennedy, J. W.; McIlwaine, S.; and Stern, J., Inversion numbers of graphs, Graph Theory Notes New York 37 (1999), 42-48.

Cowen, R.; Hechler, S. H.; Kennedy, J. W.; and Ryba, A., Inversion and neighborhood inversion in graphs, Graph Theory Notes New York 37 (1999), 37-41.

Cowen, R. and Kennedy, J., The Lights Out puzzle, Math. Educ. Res. 9 (2000), 28-32.

Goldwasser, J. and Klostermeyer, W., Maximization versions of 'Lights Out' games in grids and graphs, Congr. Numer. 126 (1997), 99-111.

K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), 49-53.

Links

Max Alekseyev and Thomas Buchholz, Table of n, a(n) for n = 1..1000 [terms were extended by Max Alekseyev, Sep 17 2009; terms 63 through 1000 were computed by Thomas Buchholz, May 16 2014]

Millstone Website, Lights Out

Eric Weisstein's World of Mathematics, Lights Out Puzzle

Whitman College Department of Mathematics, Lights Out

Formula

a(n) = 2^A159257(n). - Max Alekseyev, Sep 17 2009

Mathematica

m[k_] := SparseArray[ {Band[{1, 1}] -> 1, Band[{1, 2}] -> 1, Band[{2, 1}] -> 1}, {k, k}]; b[k_, 0] := SparseArray[ Band[{1, 1}] -> 1, {k, k}]; b[k_, 1] := m[k]; b[k_, n_] := b[k, n] = Mod[m[k].b[k, n-1] + b[k, n-2], 2]; A159257[n_] := First[ Dimensions[ NullSpace[b[n, n], Modulus -> 2]]]; A159257[1] = 0; a[n_] := 2^A159257[n]; Table[a[n], {n, 1, 62}] (* Jean-François Alcover, Oct 10 2012, after Max Alekseyev and Birkas Gyorgy *)

Crossrefs

Cf. A075463, A075464, A076436, A076437.

Sequence in context: A084473 A343051 A040246 * A082959 A232014 A018814

Adjacent sequences: A075459 A075460 A075461 * A075463 A075464 A075465

Keyword

nonn,nice

Author

Eric W. Weisstein, Sep 17 2002

Extensions

More terms from Max Alekseyev, Sep 17 2009, and Thomas Buchholz, May 16 2014

Status

approved