|
|
A193766
|
|
The number of dominoes in a largest saturated domino covering of the 3 by n board.
|
|
5
|
|
|
2, 4, 6, 8, 11, 13, 15, 17, 20, 22, 24, 26, 29, 31, 33, 35, 38, 40, 42, 44, 47, 49, 51, 53, 56, 58, 60, 62, 65, 67, 69, 71, 74, 76, 78, 80, 83, 85, 87, 89, 92, 94, 96, 98, 101, 103, 105, 107, 110, 112, 114, 116, 119, 121, 123, 125, 128, 130, 132, 134, 137
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
A domino covering of a board is saturated if the removal of any domino leaves an uncovered cell.
|
|
LINKS
|
|
|
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
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|