login
Number of 2-colorings of a 3 X n rectangle for which no subsquare has monochromatic corners.
4

%I #15 Feb 19 2015 20:36:46

%S 1,8,50,276,1498,8352,46730,260204,1447890,8062968,44907298,250082756,

%T 1392637914,7755351712,43188407610,240509081468,1339353796226,

%U 7458635202952,41535888495186,231306378487028,1288106280145770,7173247100732400,39946606186601514

%N Number of 2-colorings of a 3 X n rectangle for which no subsquare has monochromatic corners.

%C Figures obtained via clever exhaustion, using Gray Codes.

%D J. Solymosi, "A Note on a Question of Erdos and Graham", Combinatorics, Probability and Computing, Volume 13, Issue 2 (March 2004) 263 - 267.

%H Alois P. Heinz, <a href="/A133357/b133357.txt">Table of n, a(n) for n = 0..1000</a>

%H Sci.math, <a href="http://groups.google.com/group/sci.math/browse_thread/thread/8ad2914e793bb150/61d68fde1f1cca65?lnk=st&amp;q=Angelo+Wentzler+group%3Asci.math#61d68fde1f1cca65">Discussion of a related problems </a>

%F G.f.: -(x+1)*(8*x^7-12*x^6-2*x^5-16*x^4-30*x^3-15*x^2-4*x-1) / (24*x^8-4*x^7-46*x^6-66*x^5-74*x^4-25*x^3-7*x^2-3*x+1). - _Alois P. Heinz_, Feb 18 2015

%e a(1) = 8, because there are no conditions.

%e a(2) = 50 because if the middle row is not monochromatic, the top and bottom rows are unconstrained, contributing 2*4*4. If the middle row is monochromatic, the top and bottom rows can each take on only 3 values contributing 2*3*3.

%p gf:= -(x+1)*(8*x^7-12*x^6-2*x^5-16*x^4-30*x^3-15*x^2-4*x-1)/

%p (24*x^8-4*x^7-46*x^6-66*x^5-74*x^4-25*x^3-7*x^2-3*x+1):

%p a:= n-> coeff(series(gf, x, n+1), x, n):

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Feb 18 2015

%Y Cf. A133129, A255255.

%Y Column k=3 of A255256.

%K nonn,easy

%O 0,2

%A _Victor S. Miller_, Dec 21 2007

%E a(0), a(8)-a(22) from _Alois P. Heinz_, Feb 18 2015