|
%I #57 Jan 25 2024 11:38:39
%S 1,2,3,4,7,10,12,16,20,24,29,35,40,47,53,60,68,76,84,92,101,111,121,
%T 131,141,152,164,176,188,200,213,227,241,255,269,284,300,316,332,348,
%U 365,383,401,419,437,456,476,496,516,536,557,579,601,623,645,668,692
%N Sufficient number of monominoes to exclude X-pentominoes from an n X n board.
%C a(n+2) is also the domination number (size of minimum dominating set) in an n X n grid graph (Alanko et al.).
%C Apparently also the minimal number of X-polyominoes needed to cover an n X n board. - _Rob Pratt_, Jan 03 2008
%H 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DominationNumber.html">Domination Number</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,0,0,1,-2,1).
%F a(n) = n^2 - A193764(n). - _Colin Barker_, Oct 05 2014
%F 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 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 a(n) = floor(n^2/5) - 4 for n > 15. (Conçalves et al.) - _Stephan Mertens_, Jan 24 2024
%F Empirical g.f. and recurrence confirmed by above formula. - _Ray Chandler_, Jan 25 2024
%t 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 *)
%Y Cf. A193764, A269706 (size of a minimum dominating set in an n X n X n grid).
%K nonn,easy
%O 3,2
%A _Toshitaka Suzuki_, Apr 19 2005
%E Extended to a(29) by Alanko et al.
%E More terms from _Colin Barker_, Oct 05 2014
|
