A104519 -id:A104519 - cp's OEIS frontend

A378412 Irregular triangle read by rows: T(n,k) is the coefficient of x^k in the domination polynomial of the n X n grid graph (n>=1, A104519(n+2)<=k<=n^2).

1, 6, 4, 1, 10, 57, 98, 80, 36, 9, 1, 2, 40, 554, 2484, 5494, 7268, 6402, 3964, 1760, 556, 120, 16, 1, 22, 1545, 22594, 140304, 492506, 1126091, 1823057, 2204694, 2063202, 1528544, 908623, 435832, 168426, 51953, 12550, 2296, 300, 25, 1, 288, 20896, 478624

Offset: 1

Eric W. Weisstein, Nov 25 2024

Sum_{k=A104519(n+2)..n^2} T(n,k) = A133515(n).

T(n,n^2) = 1.

			D_1(x)=x
D_2(x)=6*x^2+4*x^3+x^4
D_3(x)=10*x^3+57*x^4+98*x^5+80*x^6+36*x^7+9*x^8+x^9
D_4(x)=2*x^4+40*x^5+554*x^6+2484*x^7+5494*x^8+7268*x^9+6402*x^10+3964*x^11+1760*x^12+556*x^13+120*x^14+16*x^15+x^16

Eric W. Weisstein, Table of n, a(n) for n = 1..2922
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
Eric Weisstein's World of Mathematics, Domatic Number.
Eric Weisstein's World of Mathematics, Dominating Set.
Eric Weisstein's World of Mathematics, Domination Number.
Eric Weisstein's World of Mathematics, Grid Graph.

Cf. A104519 (domination number of the (n-2) X (n-2) grid graph).
Cf. A133515 (number of dominating sets in the n X n grid graph).
Cf. A000290 (vertex count of the n X n grid graph = n^2).

A079326 a(n) = the largest number m such that if m monominoes are removed from an n X n square then an L-tromino must remain.

Original entry on oeis.org

1, 2, 7, 9, 17, 20, 31, 35, 49, 54, 71, 77, 97, 104, 127, 135, 161, 170, 199, 209, 241, 252, 287, 299, 337, 350, 391, 405, 449, 464, 511, 527, 577, 594, 647, 665, 721, 740, 799, 819, 881, 902, 967, 989, 1057, 1080, 1151, 1175, 1249, 1274, 1351, 1377, 1457

Offset: 2

Mambetov Timur (timur_teufel(AT)mail.ru), Feb 13 2003

			a(3)=2 because if a middle row of 3 monominoes are removed from the 3 X 3, no L remains.

Index entries for linear recurrences with constant coefficients, signature (1,2,-2,-1,1).

Frobenius number for k successive numbers: A028387 (k=2), this sequence (k=3), A138984 (k=4), A138985 (k=5), A138986 (k=6), A138987 (k=7), A138988 (k=8).

Cf. A093353, A104519.

Table[FrobeniusNumber[{a, a + 1, a + 2}], {a, 2, 54}] (* Zak Seidov, Jan 08 2015 *)

a(n) = (n^2)/2 - 1 (n even), (n^2-n)/2 - 1 (n odd).
a(n) = A204557(n-1) / (n-1). - Reinhard Zumkeller, Jan 18 2012
From Bruno Berselli, Jan 18 2011: (Start)
G.f.: x^2*(1+x+3*x^2-x^4)/((1+x)^2*(1-x)^3).
a(n) = n*(2*n+(-1)^n-1)/4 - 1.
a(n) = A105638(-n+2). (End)

Edited by Don Reble, May 28 2007

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

Original entry on oeis.org

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

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

A369692 Connected domination number of the n X n grid graph.

Original entry on oeis.org

1, 2, 3, 7, 11, 14, 20, 26, 30, 39, 47, 52, 64, 74, 80, 95

Offset: 1

Alexander D. Healy, Feb 25 2024

			From _Andrew Howroyd_, Mar 06 2024: (Start)
a(16) = 95 = 16 + 5*14 + 4*2 + 1.
  . . . . . . . . . . . . . . . .
  X X X X X X X X X X X X X X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X .
(End)

Alexander D. Healy, Examples of (near-)optimal dominating sets for n <= 12
Eric Weisstein's World of Mathematics, Connected Domination Number.
Eric Weisstein's World of Mathematics, Grid Graph.

Cf. A104519, A287690, A302488, A370428.

Cf. A381730 (numbers of minimum connected dominating sets).

a(3*n) <= n*(3*n+1); a(3*n-1) <= 3*n^2 - 1; a(3*n-2) <= (n-1)*(3*n+1). Conjecturally these inequalities hold with equality for n > 1. - Andrew Howroyd, Mar 06 2024

a(10)-a(16) from Andrew Howroyd, Feb 25 2024

A347632 Number of minimum dominating sets in the n X n grid graph.

Original entry on oeis.org

1, 6, 10, 2, 22, 288, 2, 52, 32, 4, 32, 21600, 18, 540360, 34528, 100406, 70266144, 1380216154, 1682689266, 77900162, 233645826, 200997249200

Offset: 1

Eric W. Weisstein, Sep 09 2021

Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Minimum Dominating Set

Main diagonal of A350820.

Cf. A104519 (domination number), A133515 (dominating sets), A290382 (minimal dominating sets).

a(7)-a(12) from Andrew Howroyd, Jan 17 2022

a(13)-a(22) from Stephan Mertens, Aug 18 2024

A321684 Independent domination number of the n X n grid graph.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 10, 12, 16, 21, 24, 30, 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

Offset: 0

Andrey Zabolotskiy, Jan 14 2019

Colin Barker, Table of n, a(n) for n = 0..1000
Simon Crevals, Patric R. J. Östergård, Independent domination of grids, Discrete Math., 338 (2015), 1379-1384.
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,0,1,-2,1).

Cf. A104519, A075324, A299029, A279404, A291297.

ogf := (-41*x^6 + 47*x^5 - x^3 - x^2 + 41*x - 47)/((x - 1)^3*(x^4 + x^3 + x^2 + x + 1)): ser := series(ogf, x, 44):
(0,1,2,3,4,7,10,12,16,21,24,30,35,40), seq(coeff(ser, x, n), n=0..42); # Peter Luschny, Jan 14 2019

concat(0, Vec(x*(1 + 2*x^4 - x^5 - x^6 + 2*x^7 + x^8 - 4*x^9 + 3*x^10 - 2*x^12 + x^13 + x^14 - 2*x^15 + 2*x^16 - 2*x^18 + x^19) / ((1 - x)^3*(1 + x + x^2 + x^3 + x^4)) + O(x^40))) \\ Colin Barker, Jan 14 2019

For n >= 14, a(n) = floor((n+2)^2 / 5 - 4).
a(n) = A104519(n+2), the domination number of the n X n grid graph, for all n except for n = 9, 11.
From Colin Barker, Jan 14 2019: (Start)
G.f.: x*(1 + 2*x^4 - x^5 - x^6 + 2*x^7 + x^8 - 4*x^9 + 3*x^10 - 2*x^12 + x^13 + x^14 - 2*x^15 + 2*x^16 - 2*x^18 + x^19) / ((1 - x)^3*(1 + x + x^2 + x^3 + x^4)).
a(n) = 2*a(n-1) - a(n-2) + a(n-5) - 2*a(n-6) + a(n-7) for n > 20.
(End)

A269706 Size of a minimum dominating set (domination number) in an n X n X n grid.

Original entry on oeis.org

1, 2, 6, 15, 25, 42, 65

Offset: 1

Eric W. Weisstein, Mar 04 2016

Eric Weisstein's World of Mathematics, Domination Number
Eric Weisstein's World of Mathematics, Grid Graph

Cf. A104519 (size of a minimum dominating set (domination number) in an n X n grid)

a(7) from Eric W. Weisstein, Aug 31 2021

A354673 Smallest number of unit cells that must be removed from an n X n square board in order to avoid any cycles.

Original entry on oeis.org

0, 1, 2, 4, 6, 10, 13, 18, 22, 28, 34, 42, 49, 58, 66, 76, 86, 98, 109, 122, 134, 148, 162, 178, 193, 210, 226, 244, 262, 282, 301, 322, 342, 364, 386, 410, 433, 458, 482, 508, 534, 562, 589, 618, 646, 676, 706, 738, 769, 802, 834, 868, 902, 938, 973, 1010, 1046

Offset: 1

Giedrius Alkauskas, Jun 02 2022

A "cycle" means a rook-connected closed path of squares.
The proof of this result is given in the Links section.
a(n+1) is very close to A239231(n); more precisely, the difference is the sequence 1,0,1,1,1,1,1,1,1,1,1,2,1,1,1,2,1,1,1,2,1,2,3,2.

			For n = 2, a(2) = 1, since removing any unit square from the 2 X 2 board leaves no cycles.
For n = 5, a(5) = 6 removed unit squares can be arranged as follows:
  x****
  *x*x*
  **x**
  *x*x*
  *****

Giedrius Alkauskas, Maximal subsets of n X n board without cycles, 2022.
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,0,0,1,-2,1).

Cf. A085577, A239072, A085577, A104519, A000170, A239231.

a(n) = ceiling(n^2/3 - n/6 + 4/3) - ceiling(n/2) for n >= 3.
From Stefano Spezia, Jun 02 2022: (Start)
G.f.: x^2*(1 + x^2 + 2*x^4 - x^5 + x^6 - x^7 + x^8)/((1 - x)^3*(1 + x)*(1 - x + x^2)*(1 + x + x^2)).
a(n) = 2*a(n-1) - a(n-2) + a(n-6) - 2*a(n-7) + a(n-8) for n > 2. (End)

cp's OEIS Frontend

A378412 Irregular triangle read by rows: T(n,k) is the coefficient of x^k in the domination polynomial of the n X n grid graph (n>=1, A104519(n+2)<=k<=n^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A079326 a(n) = the largest number m such that if m monominoes are removed from an n X n square then an L-tromino must remain.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

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

A369692 Connected domination number of the n X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A347632 Number of minimum dominating sets in the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A321684 Independent domination number of the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A269706 Size of a minimum dominating set (domination number) in an n X n X n grid.

Views

Author

Keywords

Links

Crossrefs

Extensions