

A075462


a(n) is the number of solutions to the allones lights out problem on an n X n square.


12



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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), 175180.
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), 4248.
Cowen, R.; Hechler, S. H.; Kennedy, J. W.; and Ryba, A., Inversion and neighborhood inversion in graphs, Graph Theory Notes New York 37 (1999), 3741.
Cowen, R. and Kennedy, J., The Lights Out puzzle, Math. Educ. Res. 9 (2000), 2832.
Goldwasser, J. and Klostermeyer, W., Maximization versions of 'Lights Out' games in grids and graphs, Congr. Numer. 126 (1997), 99111.
K. Sutner, Linear cellular automata and the GardenofEden, Math. Intelligencer 11 (1989), 4953.


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) [From 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, n1] + b[k, n2], 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}] (* JeanFrançois Alcover, Oct 10 2012, after Max Alekseyev and Birkas Gyorgy *)


CROSSREFS

Cf. A075463, A075464, A076436, A076437.
Sequence in context: A070569 A084473 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



