login
The number of dominoes in a largest saturated domino covering of the 3 by n board.
5

%I #27 Dec 11 2015 16:44:26

%S 2,4,6,8,11,13,15,17,20,22,24,26,29,31,33,35,38,40,42,44,47,49,51,53,

%T 56,58,60,62,65,67,69,71,74,76,78,80,83,85,87,89,92,94,96,98,101,103,

%U 105,107,110,112,114,116,119,121,123,125,128,130,132,134,137

%N The number of dominoes in a largest saturated domino covering of the 3 by n board.

%C A domino covering of a board is saturated if the removal of any domino leaves an uncovered cell.

%H Vincenzo Librandi, <a href="/A193766/b193766.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,1,-1)

%F a(n) = 3*n - floor((3*n+4)/4) = 3*n - A077915(n).

%F 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

%e 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.

%t Table[3 n - Floor[(3 n + 4)/4], {n, 100}]

%t LinearRecurrence[{1,0,0,1,-1},{2,4,6,8,11},70] (* _Harvey P. Dale_, Dec 11 2015 *)

%o (PARI) a(n) = 3*n - (3*n+4)\4 \\ _Charles R Greathouse IV_, Jun 11 2015

%Y Cf. A077915, A193764, A193765, A193767, A193768.

%K nonn,easy

%O 1,1

%A Andrew Buchanan, _Tanya Khovanova_, Alex Ryba, Aug 06 2011