|
| |
|
|
A085577
|
|
Size of maximal subset of the n^2 cells in an n X n grid such that there are at least 3 edges between any pair of chosen cells.
|
|
4
|
|
|
|
1, 1, 2, 4, 6, 8, 10, 13, 17, 20, 25, 29, 34, 40, 45, 52, 58, 65, 73, 80, 89, 97, 106, 116, 125, 136, 146, 157, 169, 180, 193, 205, 218, 232, 245, 260, 274, 289, 305, 320, 337, 353, 370, 388, 405, 424, 442, 461, 481, 500, 521, 541, 562, 584, 605, 628, 650
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
Equivalently, no pair of chosen cells are closer than a knight's move apart. This is a one-error-correcting code in the Lee metric.
Equivalently, maximal number of 5-celled Greek crosses that can be packed into an n+2 X n+2 chessboard.
A233735(n+2) is a lower bound on a(n).
Conjecture: if n == 4 (mod 5), then a(n)=(n^2+4)/5. - Erich Friedman, Apr 19 2015
More general conjecture: if n != 5, then a(n) = ceiling(n^2/5). - Rob Pratt, Jul 10 2015
|
|
|
LINKS
|
Kival Ngaokrajang, Packings of A233735(n) Greek crosses. [Note that it is possible to pack 17 Greek crosses into an 11 X 11 grid (see EXAMPLES), so these arrangements are not always optimal.]
|
|
|
FORMULA
|
a(n) approaches n^2/5 as n -> infinity.
Conjectures:
a(n) = 2*a(n-1) - a(n-2) + a(n-5) - 2*a(n-6) + a(n-7) for n > 8.
G.f.: x*(1 - x + x^2 + x^3 - x^5 + x^6 - x^9 + 2*x^10 - x^11) / ((1-x)^3*(1 + x + x^2 + x^3 + x^4)). (End)
|
|
|
EXAMPLE
|
For example, a(3) = 2:
..o
...
o..
.o....o..
...o....o
o....o...
..o....o.
....o....
.o....o..
...o....o
o....o...
..o....o.
|
|
|
MATHEMATICA
|
(* Warning: this program gives correct results up to n=70, but must not be used to extend the sequence beyond that limit. *) a[n_] := a[n] = If[n <= 9, {1, 1, 2, 4, 6, 8, 10, 13, 17}[[n]], n^2 - 4*n + 8 - a[n-4] - a[n-3] - a[n-2] - a[n-1]]; Table[a[n], {n, 1, 70}] (* Jean-François Alcover, Nov 24 2016 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
