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

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,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.

Sequence in context: A276215 A202117 A100458 * A000960 A147614 A171747

Adjacent sequences: A193762 A193763 A193764 * A193766 A193767 A193768

Keyword

nonn

Author

Andrew Buchanan, Tanya Khovanova, Alex Ryba, Aug 06 2011

Status

approved