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

1, 8, 50, 276, 1498, 8352, 46730, 260204, 1447890, 8062968, 44907298, 250082756, 1392637914, 7755351712, 43188407610, 240509081468, 1339353796226, 7458635202952, 41535888495186, 231306378487028, 1288106280145770, 7173247100732400, 39946606186601514

Offset: 0

Author

Victor S. Miller, Dec 21 2007

Keywords

• nonn
• easy

Comments

Figures obtained via clever exhaustion, using Gray Codes.

Examples

			a(1) = 8, because there are no conditions.
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.
		

References

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Sci.math, Discussion of a related problems

Crossrefs

Cf. A133129, A255255.

Column k=3 of A255256.

Programs

Maple

gf:= -(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):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..30);  # Alois P. Heinz, Feb 18 2015

Formula

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

Extensions

a(0), a(8)-a(22) from Alois P. Heinz, Feb 18 2015