

A104519


Sufficient number of monominoes to exclude Xpentominoes from an n X n board.


5



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 Xpolyominoes needed to cover an n X n board.  Rob Pratt, Jan 03 2008


LINKS

Table of n, a(n) for n=3..51.
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.
Eric Weisstein's World of Mathematics, Domination Number
Eric Weisstein's World of Mathematics, Grid Graph


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(n1)a(n2)+a(n5)2*a(n6)+a(n7) 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
The first 51 terms can be described by the following collection of piecewise functions (written in Mathematica code): 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


AUTHOR

Toshitaka Suzuki, Apr 19 2005


EXTENSIONS

Extended to a(29) by Alanko et al.
More terms from Colin Barker, Oct 05 2014
Keywords 'hard' and 'more' deleted by Colin Barker, Oct 05 2014


STATUS

approved



