A193764 -id:A193764 - cp's OEIS frontend

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

Toshitaka Suzuki, Apr 19 2005

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

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

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

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

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

Extended to a(29) by Alanko et al.

More terms from Colin Barker, Oct 05 2014

A193768 The domination number of the 4 X n board.

Original entry on oeis.org

2, 3, 4, 4, 6, 7, 7, 8, 10, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67

Offset: 1

Andrew Buchanan, Tanya Khovanova, Alex Ryba, Aug 06 2011

The domination number of a rectangular grid is the minimal number of X-pentominoes or its fragments that can cover the board.

			You can't cover the 1 by 4 board with an X-pentomino, but you can do it with two of them.

Andrew Buchanan, Tanya Khovanova and Alex Ryba, Saturated Domino Coverings, arXiv:1112.2115 [math.CO], 2011.
M. S. Jacobson and L. F. Kinch, On the domination number of products of graphs:I, Ars Combinatoria, vol 18, 1983, 33-44.
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Row 4 of A350823.

Cf. A193764, A193765, A193766, A193767.

LinearRecurrence[{2,-1},{2,3,4,4,6,7,7,8,10,10,11},70] (* Harvey P. Dale, Feb 17 2020 *)

Vec(x*(x^10-2*x^9+x^8+x^7-x^6-x^5+2*x^4-x^3-x+2)/(x-1)^2 + O(x^100)) \\ Colin Barker, Oct 05 2014

a(n) = n, except for n = 1, 2, 3, 5, 6 or 9. For the exceptions a(n) = n+1.
a(n) = 4n - A193767(n).
a(n) = 2*a(n-1)-a(n-2) for n>11. - Colin Barker, Oct 05 2014
G.f.: x*(x^10-2*x^9+x^8+x^7-x^6-x^5+2*x^4-x^3-x+2) / (x-1)^2. - Colin Barker, Oct 05 2014

A193766 The number of dominoes in a largest saturated domino covering of the 3 by n board.

Original entry on oeis.org

2, 4, 6, 8, 11, 13, 15, 17, 20, 22, 24, 26, 29, 31, 33, 35, 38, 40, 42, 44, 47, 49, 51, 53, 56, 58, 60, 62, 65, 67, 69, 71, 74, 76, 78, 80, 83, 85, 87, 89, 92, 94, 96, 98, 101, 103, 105, 107, 110, 112, 114, 116, 119, 121, 123, 125, 128, 130, 132, 134, 137

Offset: 1

Andrew Buchanan, Tanya Khovanova, Alex Ryba, Aug 06 2011

A domino covering of a board is saturated if the removal of any domino leaves an uncovered cell.

			If you completely cover a 3 by 1 board with 3 dominoes, you can always remove one and the board will still be covered. Hence a(2) < 3. On the other hand, you can cover the 2 by 2 board with 2 dominoes and a removal of one of them will leave one cell uncovered. Hence a(1) = 2.

Vincenzo Librandi, Table of n, a(n) for n = 1..10000
Andrew Buchanan, Tanya Khovanova and Alex Ryba, Saturated Domino Coverings, arXiv:1112.2115 [math.CO], 2011.
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1)

Cf. A077915, A193764, A193765, A193767, A193768.

Table[3 n - Floor[(3 n + 4)/4], {n, 100}]
LinearRecurrence[{1,0,0,1,-1},{2,4,6,8,11},70] (* Harvey P. Dale, Dec 11 2015 *)

a(n) = 3*n - (3*n+4)\4 \\ Charles R Greathouse IV, Jun 11 2015

a(n) = 3*n - floor((3*n+4)/4) = 3*n - A077915(n).

G.f. x*(2+2*x+2*x^2+2*x^3+x^4) / ( (1+x)*(x^2+1)*(x-1)^2 ). - R. J. Mathar, Aug 22 2011

A193765 The number of dominoes in the largest saturated domino covering of the n X n board plus one (n >= 2).

Original entry on oeis.org

3, 7, 13, 19, 27, 38, 49, 62, 77, 93, 110, 130, 150, 173, 197, 222, 249, 278, 309, 341, 374, 409, 446, 485, 525, 566, 609, 654, 701, 749, 798, 849, 902, 957, 1013, 1070, 1129, 1190, 1253, 1317, 1382, 1449, 1518, 1589, 1661, 1734, 1809, 1886, 1965, 2045, 2126

Offset: 2

Andrew Buchanan, Tanya Khovanova, Alex Ryba, Aug 06 2011

nonn

A domino covering of a board is saturated if the removal of any domino leaves an uncovered cell.

In a domino covering of an n X n board, a domino is redundant if its removal leaves a covering of the board. a(n) is the smallest size of board for which any domino covering must include a redundant domino.

			If you completely cover a 2 X 2 board with 3 dominoes, you can remove one and the board will still be covered. Hence a(2) >= 3. On the other hand, you can tile the 2 by 2 board with 2 dominoes and a removal of one of them will leave both cells uncovered. Hence a(2) = 3.

Andrew Buchanan, Tanya Khovanova and Alex Ryba, Saturated Domino Coverings, arXiv:1112.2115 [math.CO], 2011.
Index entries for linear recurrences with constant coefficients, signature (2, -1, 0, 0, 1, -2, 1).

Cf. A104519, A193764, A193766, A193767, A193768.

For n > 6, except n = 13, a(n) = n^2 + 5 - floor((n+2)^2/5).
a(n) = n^2 +1 - A104519(n).
Empirical g.f.: x^2*(x^18 -2*x^17 +x^16 -x^13 +2*x^12 -3*x^11 +2*x^10 +x^9 -2*x^8 +x^6 -2*x^4 -2*x^2 -x -3) / ((x -1)^3*(x^4 +x^3 +x^2 +x +1)). - Colin Barker, Oct 05 2014
Empirical g.f. confirmed with above formula and recurrence in A104519. - Ray Chandler, Jan 25 2024

A193767 The number of dominoes in a largest saturated domino covering of the 4 by n board.

Original entry on oeis.org

2, 5, 8, 12, 14, 17, 21, 24, 26, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 153, 156, 159, 162, 165, 168, 171, 174, 177

Offset: 1

Andrew Buchanan, Tanya Khovanova, Alex Ryba, Aug 06 2011

A domino covering of a board is saturated if the removal of any domino leaves an uncovered cell.

			You have to have at least two dominoes to cover the 1 by 4 board, each covering the corner. After that anything else you can remove. Hence a(1) = 2.

Andrew Buchanan, Tanya Khovanova and Alex Ryba, Saturated Domino Coverings, arXiv:1112.2115 [math.CO], 2011
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A193764, A193765, A193766, A193768.

LinearRecurrence[{2,-1},{2,5,8,12,14,17,21,24,26,30,33},60] (* Harvey P. Dale, Mar 25 2025 *)

Vec(-x*(x^10-2*x^9+x^8+x^7-x^6-x^5+2*x^4-x^3-x-2)/(x-1)^2 + O(x^100)) \\ Colin Barker, Oct 05 2014

a(n) = 3n, except for n = 1, 2, 3, 5, 6 or 9. For the exceptions a(n) = 3n-1.
a(n) = 4n - A193768(n).
a(n) = 2*a(n-1)-a(n-2) for n>11. - Colin Barker, Oct 05 2014
G.f.: -x*(x^10-2*x^9+x^8+x^7-x^6-x^5+2*x^4-x^3-x-2) / (x-1)^2. - Colin Barker, Oct 05 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A193768 The domination number of the 4 X n board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A193766 The number of dominoes in a largest saturated domino covering of the 3 by n board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A193765 The number of dominoes in the largest saturated domino covering of the n X n board plus one (n >= 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A193767 The number of dominoes in a largest saturated domino covering of the 4 by n board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula