|
|
A075462
|
|
a(n) is the number of solutions to the all-ones lights out problem on an n X n square.
|
|
11
|
|
|
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), 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]
Whitman College Department of Mathematics, Lights Out
|
|
FORMULA
|
|
|
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
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|