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

1, 2, 3, 4, 7, 10, 12, 16, 20, 24, 29, 35, 40, 47, 53, 60, 68, 76, 84, 92, 101, 111, 121, 131, 141, 152, 164, 176, 188, 200, 213, 227, 241, 255, 269, 284, 300, 316, 332, 348, 365, 383, 401, 419, 437, 456, 476, 496, 516, 536, 557, 579, 601, 623, 645, 668, 692

Offset: 3

Author

Toshitaka Suzuki, Apr 19 2005

Keywords

• nonn
• easy

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).

Crossrefs

Cf. A193764, A269706 (size of a minimum dominating set in an n X n X n grid).

Programs

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 *)

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

Extensions

Extended to a(29) by Alanko et al.

More terms from Colin Barker, Oct 05 2014