cp's OEIS Frontend

A104519 Sufficient number of monominoes to exclude X-pentominoes from an n X n board.

%I A104519 #66 Feb 16 2025 08:32:56
%S A104519 1,2,3,4,7,10,12,16,20,24,29,35,40,47,53,60,68,76,84,92,101,111,121,
%T A104519 131,141,152,164,176,188,200,213,227,241,255,269,284,300,316,332,348,
%U A104519 365,383,401,419,437,456,476,496,516,536,557,579,601,623,645,668,692
%N A104519 Sufficient number of monominoes to exclude X-pentominoes from an n X n board.
%C A104519 a(n+2) is also the domination number (size of minimum dominating set) in an n X n grid graph (Alanko et al.).
%C A104519 Apparently also the minimal number of X-polyominoes needed to cover an n X n board. - _Rob Pratt_, Jan 03 2008
%H A104519 Harvey P. Dale, <a href="/A104519/b104519.txt">Table of n, a(n) for n = 3..1000</a>
%H A104519 Samu Alanko, Simon Crevals, Anton Isopoussu, Patric R. J. Östergård, and Ville Pettersson, <a href="https://doi.org/10.37236/628">Computing the Domination Number of Grid Graphs</a>, The Electronic Journal of Combinatorics, 18 (2011), #P141.
%H A104519 Daniel Gonçalves, Alexandre Pinlou, Michaël Rao, and Stéphan Thomassé, <a href="https://doi.org/10.1137/11082574">The Domination Number of Grids</a>, SIAM Journal on Discrete Mathematics, 25 (2011), 1443.
%H A104519 Stephan Mertens, <a href="https://arxiv.org/abs/2408.08053">Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph</a>, arXiv:2408.08053 [math.CO], 2024. See p. 15.
%H A104519 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DominationNumber.html">Domination Number</a>
%H A104519 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H A104519 <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,0,0,1,-2,1).
%F A104519 a(n) = n^2 - A193764(n). - _Colin Barker_, Oct 05 2014
%F A104519 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
%F A104519 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
%F A104519 a(n) = floor(n^2/5) - 4 for n > 15. (Conçalves et al.) - _Stephan Mertens_, Jan 24 2024
%F A104519 Empirical g.f. and recurrence confirmed by above formula. - _Ray Chandler_, Jan 25 2024
%t A104519 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 *)
%t A104519 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 *)
%Y A104519 Cf. A193764, A269706 (size of a minimum dominating set in an n X n X n grid).
%K A104519 nonn,easy
%O A104519 3,2
%A A104519 _Toshitaka Suzuki_, Apr 19 2005
%E A104519 Extended to a(29) by Alanko et al.
%E A104519 More terms from _Colin Barker_, Oct 05 2014