[go: up one dir, main page]
login
The OEIS is supported by the many generous donors to the OEIS Foundation.
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: a193764 -id:a193764
Displaying 1-5 of 5 results found.
page 1
     Sort: relevance | references | number | modified | created      Format: long | short | data
A104519
Sufficient number of monominoes to exclude X-pentominoes from an n X n board.
+10
10
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
(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 X-polyominoes needed to cover an n X n board. - Rob Pratt, Jan 03 2008
LINKS
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).
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 *)
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 *)
CROSSREFS
Cf. A193764, A269706 (size of a minimum dominating set in an n X n X n grid).
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
A193768
The domination number of the 4 X n board.
+10
6
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
(list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
COMMENTS
The domination number of a rectangular grid is the minimal number of X-pentominoes or its fragments that can cover the board.
LINKS
Table of n, a(n) for n=1..67.
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).
FORMULA
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
EXAMPLE
You can't cover the 1 by 4 board with an X-pentomino, but you can do it with two of them.
MATHEMATICA
LinearRecurrence[{2, -1}, {2, 3, 4, 4, 6, 7, 7, 8, 10, 10, 11}, 70] (* Harvey P. Dale, Feb 17 2020 *)
PROG
(PARI) 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
CROSSREFS
Row 4 of A350823.
Cf. A193764, A193765, A193766, A193767.
KEYWORD
nonn,easy
AUTHOR
Andrew Buchanan, Tanya Khovanova, Alex Ryba, Aug 06 2011
STATUS
approved
A193766
The number of dominoes in a largest saturated domino covering of the 3 by n board.
+10
5
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
(list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
COMMENTS
A domino covering of a board is saturated if the removal of any domino leaves an uncovered cell.
LINKS
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)
FORMULA
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
EXAMPLE
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.
MATHEMATICA
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 *)
PROG
(PARI) a(n) = 3*n - (3*n+4)\4 \\ Charles R Greathouse IV, Jun 11 2015
CROSSREFS
Cf. A077915, A193764, A193765, A193767, A193768.
KEYWORD
nonn,easy
AUTHOR
Andrew Buchanan, Tanya Khovanova, Alex Ryba, Aug 06 2011
STATUS
approved
A193765
The number of dominoes in the largest saturated domino covering of the n X n board plus one (n >= 2).
+10
4
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
(list; graph; refs; listen; history; text; internal format)
OFFSET
2,1
COMMENTS
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.
LINKS
Table of n, a(n) for n=2..52.
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).
FORMULA
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
EXAMPLE
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.
CROSSREFS
Cf. A104519, A193764, A193766, A193767, A193768.
KEYWORD
nonn
AUTHOR
Andrew Buchanan, Tanya Khovanova, Alex Ryba, Aug 06 2011
STATUS
approved
A193767
The number of dominoes in a largest saturated domino covering of the 4 by n board.
+10
4
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
(list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
COMMENTS
A domino covering of a board is saturated if the removal of any domino leaves an uncovered cell.
LINKS
Table of n, a(n) for n=1..59.
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).
FORMULA
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
EXAMPLE
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.
PROG
(PARI) 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
CROSSREFS
Cf. A193764, A193765, A193766, A193768.
KEYWORD
nonn,easy
AUTHOR
Andrew Buchanan, Tanya Khovanova, Alex Ryba, Aug 06 2011
STATUS
approved
page 1

Search completed in 0.006 seconds

Lookup Welcome Wiki Register Music Plot 2 Demos Index WebCam Contribute Format Style Sheet Transforms Superseeker Recents
The OEIS Community
Maintained by The OEIS Foundation Inc.
Last modified November 28 07:46 EST 2024. Contains 378181 sequences.
License Agreements, Terms of Use, Privacy Policy