[seqfan] Re: n X n binary array quasi-packing problem

[Rob Pratt]

I used integer linear programming to confirm and extend both b = 8 and b = 4:

n	b = 8	b = 4
1	0	0
2	2	1
3	7	3
4	10	8
5	17	11
6	28	17
7	34	25
8	46	32
9	63	43
10	72	52
11	89	64
12	112	77
13	124	91
14	146	108
15	175	
16	190	
17	217	
18	252	
19	270	
20	302	
21	343	
22	364	
23	401	
24	448	
25	472	
26	514	
27	567	
28	594	
29	641	
30	700	
31	730	
32	782	
33	847	
34	880	
35	937	
36	1008	

-----Original Message-----
From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Richard J. Mathar
Sent: Monday, February 06, 2017 7:01 AM
To: seqfan at seqfan.eu
Subject: [seqfan] Re: n X n binary array quasi-packing problem

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.

--
Seqfan Mailing list - http://list.seqfan.eu/