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.
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
Offset: 1
Examples
For example, a(3) = 2: ..o ... o.. a(9)=17 (from _Erich Friedman_, Apr 18 2015): .o....o.. ...o....o o....o... ..o....o. ....o.... .o....o.. ...o....o o....o... ..o....o.
Links
- Giovanni Resta, Table of n, a(n) for n = 1..70
- 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.]
- Popular Computing (Calabasas, CA), Problem 175: Knights Away, Vol. 5, (No. 50, May 1977), pp. PC50-18 to PC50-19.
Programs
-
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 *)
Formula
a(n) approaches n^2/5 as n -> infinity.
From Colin Barker, Oct 15 2016: (Start)
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)
Extensions
a(14)-a(30) from Rob Pratt, Jul 10 2015
a(31)-a(57) from Giovanni Resta, Jul 29 2015
Comments