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
KEYWORD
nonn,easy
AUTHOR
Andrew Buchanan, Tanya Khovanova, Alex Ryba, Aug 06 2011
STATUS
approved