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,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

Table of n, a(n) for n=3..59.

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

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

Crossrefs

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

Sequence in context: A204231 A135419 A051914 * A321684 A117220 A118426

Adjacent sequences: A104516 A104517 A104518 * A104520 A104521 A104522

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