OFFSET
3,2
COMMENTS
a(n+2) is also the domination number (size of minimum dominating set) in an n X n grid graph (Alanko et al.).
Apparently also the minimal number of X-polyominoes needed to cover an n X n board. - Rob Pratt, Jan 03 2008
LINKS
Harvey P. Dale, Table of n, a(n) for n = 3..1000
Samu Alanko, Simon Crevals, Anton Isopoussu, Patric R. J. Östergård, and Ville Pettersson, Computing the Domination Number of Grid Graphs, The Electronic Journal of Combinatorics, 18 (2011), #P141.
Daniel Gonçalves, Alexandre Pinlou, Michaël Rao, and Stéphan Thomassé, The Domination Number of Grids, SIAM Journal on Discrete Mathematics, 25 (2011), 1443.
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], 2024. See p. 15.
Eric Weisstein's World of Mathematics, Domination Number
Eric Weisstein's World of Mathematics, Grid Graph
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,0,1,-2,1).
FORMULA
a(n) = n^2 - A193764(n). - Colin Barker, Oct 05 2014
Empirical g.f.: -x^3*(x^19 -2*x^18 +x^17 -x^14 +2*x^13 -3*x^12 +2*x^11 +x^10 -2*x^9 +2*x^7 -x^6 -x^5 +2*x^4 +1) / ((x -1)^3*(x^4 +x^3 +x^2 +x +1)) - Colin Barker, Oct 05 2014
Empirical recurrence a(n) = 2*a(n-1)-a(n-2)+a(n-5)-2*a(n-6)+a(n-7) with a(3)=-3, a(4)=-1, a(5)=1, a(6)=3, a(7)=5, a(8)=8, a(9)=12 matches the sequence for 9 <= n <= 14 and 16 <= n <= 51. - Eric W. Weisstein, Jun 27 2017
a(n) = floor(n^2/5) - 4 for n > 15. (Conçalves et al.) - Stephan Mertens, Jan 24 2024
Empirical g.f. and recurrence confirmed by above formula. - Ray Chandler, Jan 25 2024
MATHEMATICA
Table[Piecewise[{{n - 2, n <= 6}, {7, n == 7}, {10, n == 8}, {40, n == 15}}, Floor[n^2/5] - 4], {n, 3, 51}] (* Eric W. Weisstein, Apr 12 2016 *)
LinearRecurrence[{2, -1, 0, 0, 1, -2, 1}, {1, 2, 3, 4, 7, 10, 12, 16, 20, 24, 29, 35, 40, 47, 53, 60, 68, 76, 84, 92}, 60] (* Harvey P. Dale, Aug 30 2024 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Toshitaka Suzuki, Apr 19 2005
EXTENSIONS
Extended to a(29) by Alanko et al.
More terms from Colin Barker, Oct 05 2014
STATUS
approved