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

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,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=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 + 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

G.f.: x^2*(2 + 2*x + 2*x^2 + 2*x^4 + x^5 - 2*x^6 + 2*x^8 - x^9 - 2*x^10 + 3*x^11 - 2*x^12 + x^13 - x^16 + 2*x^17 - x^18)/(1 - 2*x + x^2 - x^5 + 2*x^6 - x^7). - Charles R Greathouse IV, May 20 2026

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 X 2 board with 2 dominoes and a removal of one of them will leave both cells uncovered. Hence a(2) = 2.

Prog

(PARI) a(n)=if(n>13, (4*n^2-4*n+[20, 20, 17, 16, 17][n%5+1])/5, [2, 6, 12, 18, 26, 37, 48, 61, 76, 92, 109, 129][n-1]) \\ Charles R Greathouse IV, May 20 2026

Crossrefs

Cf. A104519, A193765, A193766, A193767, A193768.

Sequence in context: A267461 A108585 A294062 * A278484 A159793 A238739

Adjacent sequences: A193761 A193762 A193763 * A193765 A193766 A193767

Keyword

nonn,easy

Author

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

Status

approved