A193768 -id:A193768 - cp's OEIS frontend

A193764 The number of dominoes in a largest saturated domino covering of the n X n board (n>=2).

2, 6, 12, 18, 26, 37, 48, 61, 76, 92, 109, 129, 149, 172, 196, 221, 248, 277, 308, 340, 373, 408, 445, 484, 524, 565, 608, 653, 700, 748, 797, 848, 901, 956, 1012, 1069, 1128, 1189, 1252, 1316, 1381, 1448, 1517, 1588, 1660, 1733, 1808, 1885, 1964, 2044, 2125

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.

			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 X 2 board with 2 dominoes and a removal of one of them will leave both cells uncovered. Hence a(2) = 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, 0, 0, 1, -2, 1).

Cf. A104519, A193765, A193766, A193767, A193768.

For n > 6, except n = 13, a(n) = n^2 + 4 - floor((n+2)^2/5).
a(n) = n^2 - 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 +2*x^6 -x^5 -2*x^4 -2*x^2 -2*x -2) / ((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

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

A350823 Array read by antidiagonals: T(m,n) is the domination number of the grid graph P_m X P_n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 4, 4, 3, 2, 3, 4, 4, 4, 4, 4, 3, 3, 4, 5, 6, 6, 5, 4, 3, 3, 5, 6, 7, 7, 7, 6, 5, 3, 4, 5, 7, 7, 8, 8, 7, 7, 5, 4, 4, 6, 7, 8, 9, 10, 9, 8, 7, 6, 4, 4, 6, 8, 10, 11, 11, 11, 11, 10, 8, 6, 4

Offset: 1

Andrew Howroyd, Jan 17 2022

Equivalently, the minimum number of X-pentominoes needed to cover an m X n grid.

			Table begins:
===================================
m\n | 1  2  3  4  5  6  7  8  9
----+------------------------------
  1 | 1  1  1  2  2  2  3  3  3 ...
  2 | 1  2  2  3  3  4  4  5  5 ...
  3 | 1  2  3  4  4  5  6  7  7 ...
  4 | 2  3  4  4  6  7  7  8 10 ...
  5 | 2  3  4  6  7  8  9 11 12 ...
  6 | 2  4  5  7  8 10 11 12 14 ...
  7 | 3  4  6  7  9 11 12 14 16 ...
  8 | 3  5  7  8 11 12 14 16 18 ...
  9 | 3  5  7 10 12 14 16 18 20 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..276
Eric Weisstein's World of Mathematics, Domination Number
Eric Weisstein's World of Mathematics, Grid Graph

Row 4 is A193768.
Main diagonal is A104519.
Cf. A286847, A300358, A350820.

T(m,n) = T(n,m).

T(1,n) = ceiling(n/3); T(2,n) = floor(n/2) + 1.

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

A350822 Number of minimum dominating sets in the grid graph P_4 X P_n.

Original entry on oeis.org

4, 12, 29, 2, 52, 92, 2, 4, 324, 2, 10, 8, 2, 16, 32, 18, 22, 74, 90, 60, 134, 270, 258, 276, 612, 888, 852, 1298, 2382, 2886, 3278, 5590, 8538, 9902, 13444, 22100, 29864, 36526, 54578, 82602, 106156, 141074, 213858, 301224, 389912, 550584, 811542, 1098516, 1471482, 2126568

Offset: 1

Andrew Howroyd, Jan 17 2022

nonn

Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Minimum Dominating Set

Row 4 of A350820.

Cf. A193768 (domination number).

a(n) = a(n-3) + 2*a(n-4) + a(n-7) for n > 16.

cp's OEIS Frontend

A193764 The number of dominoes in a largest saturated domino covering of the n X n board (n>=2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A350823 Array read by antidiagonals: T(m,n) is the domination number of the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A350822 Number of minimum dominating sets in the grid graph P_4 X P_n.

Views

Author

Keywords

Links

Crossrefs

Formula