[seqfan] Re: n X n binary array quasi-packing problem
Richard J. Mathar
mathar at mpia-hd.mpg.de
Mon Feb 6 13:00:55 CET 2017
Concerning http://list.seqfan.eu/pipermail/seqfan/2017-February/017250.html
There is obviously a lower bound for the king-move definition
of adjacency given for n >= 1 by
a(n) = 0,2,7,7,17,28,28,46,63,63,89,112,112,146,175,175,217,252,252,302,343,343,...
a(n)= +a(n-1) +2*a(n-3) -2*a(n-4) -a(n-6) +a(n-7).
G.f.: -x^2*(2+5*x+6*x^3+x^4) / ( (1+x+x^2)^2*(x-1)^3 ).
See A033582 for a trisection.
There is obviously a decomposition
27*a(n) = 5-18*n+21*n^2 + (17*b(n-1)-47) +6*(7*c(n)+2*c(n-1)),
with b(n) = A049347(n),
with c(n) = (-1)^n*A099254(n).
This is generated by setting 1's at each row and column 3-periodically
as shown in your 6X6 solution: If the binary array is A(r,c)
with 0<=r<n and 0<=c<n, set A(r,c) = 1 if r == 1 ( mod 3) and c==1 (mod 3)
and 0 otherwise.
More information about the SeqFan
mailing list