OFFSET
1,2
COMMENTS
This sequence arose in a discussion among Carlos Rivera, Emmanuel Vantieghem, Dmitry Kamenetsky, W. Edwin Clark, Fred Schneider, Ramón David, and Claudio Meller concerning Puzzle 772 at Prime Puzzles (see Prime Puzzle #772 link).
Later we discovered the relationship to Sutner's paper. A corollary of that paper is that a(n) > 0 for all n. An obvious conjecture is that a(n) = 1 for n mod 3 = 0 or 1 and if n mod 3 = 2 then a(n) = 2^(2n-1).
LINKS
Carlos Rivera, Prime Puzzle #772
Klaus Sutner, Linear Cellular Automata and the Garden-of-Eden, Mathematical Intelligencer Vol 11, No. 2 1989.
FORMULA
Empirical g.f.: -x*(64*x^5+8*x^4+64*x^3-x^2-8*x-1) / ((x-1)*(4*x-1)*(x^2+x+1)*(16*x^2+4*x+1)). - Colin Barker, Jan 31 2015
EXAMPLE
For n = 2 the a(2) = 8 predecessors of the all-ones matrix are the eight 2 X 2 binary matrices with one or three zero entries.
MAPLE
a:=proc(n)
local A, A1, V, E, i, j, G, f, g, w;
V:=NULL:
E:={}:
for i from 1 to n do
for j from 1 to n do
V:=V, [i, j];
E:=E union {seq(seq({[i, j], [i+x, j+y]}, x=-1..1), y=-1..1)};
od:
od:
V:=[V];
E:=remove(t->evalb(has(t, 0) or has(t, n+1)), E):
E:=remove(t->evalb(nops(t) = 1), E):
for i from 1 to nops(V)do
f(V[i]):=i:
od:
g:=proc(U)
map(f, U);
end:
G:=GraphTheory:-Graph(map(f, V), map(g, E));
A:=GraphTheory:-AdjacencyMatrix(G)+LinearAlgebra[IdentityMatrix](n^2);
A1:=LinearAlgebra:-Modular:-Mod(2, convert(A, listlist), integer[]);
w:=n^2-LinearAlgebra:-Modular:-Rank(2, A1);
return 2^w;
end proc:
CROSSREFS
KEYWORD
nonn
AUTHOR
W. Edwin Clark, Jan 30 2015
STATUS
approved