cp's OEIS Frontend

A280984 Minimum number of dominoes on an n X n chessboard needed to prevent placement of another domino.

%I A280984 #82 Dec 17 2024 18:26:34
%S A280984 0,2,3,6,9,12,17,22,27,34,41,48,57,66,75,86,97,108,122,134,147,163,
%T A280984 178,192,210,227,243,263,282,300,322,343,363
%N A280984 Minimum number of dominoes on an n X n chessboard needed to prevent placement of another domino.
%C A280984 Each domino must cover exactly two adjacent squares of a row or column. Sequence inspired by question for 8 X 8 case in "Minimum Guard Problem" link.
%C A280984 A.k.a. lower matching number of the n X n grid graph. - _Eric W. Weisstein_, Dec 16 2024
%C A280984 a(n) = 0 for n = 1, a(n) = ceiling(n^2/3) + 1 for n = 19, 22, 23, 25, 26, 28, 29, 31, 32, and a(n) = ceiling(n^2/3) for other n <= 32. - _Eric W. Weisstein_, Dec 16 2024
%H A280984 Andrejs Cibulis and Walter Trump, <a href="https://doi.org/10.22364/bjmc.2020.8.4.02">Domino Exclusion Problem</a>, Baltic J. Modern Computing, Vol. 8 (2020), No. 4, 496-519.
%H A280984 A. Gyárfás, J. Lehel, and Zs. Tuza, <a href="https://doi.org/10.1016/0012-365X(88)90028-3">Clumsy packing of dominoes</a>, Discrete Mathematics, Volume 71, Issue 1 (1988), 33-46.
%H A280984 Peter Kagey, <a href="https://math.stackexchange.com/q/3191721/121988">Minimum number of dominoes on an n X n chessboard to prevent placement of another domino.</a>
%H A280984 Mathematics Stack Exchange user "Manin", <a href="https://math.stackexchange.com/questions/1573902/minimum-guard-problem">Minimum Guard Problem</a>.
%H A280984 Walter Trump, <a href="/A280984/a280984.pdf">Minimum Domino Packing</a>
%H A280984 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>.
%H A280984 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LowerMatchingNumber.html">Lower Matching Number</a>.
%F A280984 Proved: a(n) >= A008810(n) for n>1; when n = 0 (mod 3), a(n) = A008810(n). - _Andrey Zabolotskiy_, Oct 22 2017
%F A280984 a(n) > n^2/3 + n/111 for large n not congruent to 0 (mod 3) [from Gyárfás, Lehel, Tuza]. - _Peter Kagey_, May 22 2019
%Y A280984 Cf. A008810 (maximum number of L-shaped trominoes with the same orientation in an n X n square, a.k.a. ceil(n^2/3)).
%Y A280984 Cf. A378763 (lower matching number of the n X n torus grid graph).
%Y A280984 Cf. A379177 (lower matching number of the n X n X n grid graph).
%K A280984 nonn,more
%O A280984 1,2
%A A280984 _Rick L. Shepherd_, Jan 11 2017, Aug 06 2017
%E A280984 a(10)-a(14) from _Lars Blomberg_, Aug 08 2017
%E A280984 a(15) from _Andrey Zabolotskiy_, Oct 20 2017
%E A280984 a(16)-a(17) from _Rob Pratt_ (see the link to _Peter Kagey_'s question) and a(18) added by _Andrey Zabolotskiy_, Feb 13 2020
%E A280984 a(19)-a(33) from _Walter Trump_, Jun 14 2020