cp's OEIS Frontend

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

%I A193765 #21 Jan 25 2024 11:47:23
%S A193765 3,7,13,19,27,38,49,62,77,93,110,130,150,173,197,222,249,278,309,341,
%T A193765 374,409,446,485,525,566,609,654,701,749,798,849,902,957,1013,1070,
%U A193765 1129,1190,1253,1317,1382,1449,1518,1589,1661,1734,1809,1886,1965,2045,2126
%N A193765 The number of dominoes in the largest saturated domino covering of the n X n board plus one (n >= 2).
%C A193765 A domino covering of a board is saturated if the removal of any domino leaves an uncovered cell.
%C A193765 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.
%H A193765 Andrew Buchanan, Tanya Khovanova and Alex Ryba, <a href="http://arxiv.org/abs/1112.2115">Saturated Domino Coverings</a>, arXiv:1112.2115 [math.CO], 2011.
%H A193765 <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (2, -1, 0, 0, 1, -2, 1).
%F A193765 For n > 6, except n = 13, a(n) = n^2 + 5 - floor((n+2)^2/5).
%F A193765 a(n) = n^2 +1 - A104519(n).
%F A193765 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
%F A193765 Empirical g.f. confirmed with above formula and recurrence in A104519. - _Ray Chandler_, Jan 25 2024
%e A193765 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.
%Y A193765 Cf. A104519, A193764, A193766, A193767, A193768.
%K A193765 nonn
%O A193765 2,1
%A A193765 Andrew Buchanan, _Tanya Khovanova_, Alex Ryba, Aug 06 2011