A255255 -id:A255255 - cp's OEIS frontend

A255256 Number A(n,k) of 2-colorings of a k X n rectangle such that no nontrivial subsquare has monochromatic corners; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 14, 8, 1, 1, 16, 50, 50, 16, 1, 1, 32, 178, 276, 178, 32, 1, 1, 64, 634, 1498, 1498, 634, 64, 1, 1, 128, 2258, 8352, 10980, 8352, 2258, 128, 1, 1, 256, 8042, 46730, 85138, 85138, 46730, 8042, 256, 1, 1, 512, 28642, 260204, 655090, 781712, 655090, 260204, 28642, 512, 1

Offset: 0

Alois P. Heinz, Feb 19 2015

			A(2,2) = 2^(2*2) - 2 = 14 because there are exactly two of sixteen 2-colorings of the 2 X 2 square resulting in nontrivial subsquares with monochromatic corners.
Square array A(n,k) begins:
  1,  1,    1,     1,      1,       1,        1, ...
  1,  2,    4,     8,     16,      32,       64, ...
  1,  4,   14,    50,    178,     634,     2258, ...
  1,  8,   50,   276,   1498,    8352,    46730, ...
  1, 16,  178,  1498,  10980,   85138,   655090, ...
  1, 32,  634,  8352,  85138,  781712,  6965108, ...
  1, 64, 2258, 46730, 655090, 6965108, 58339148, ...

Alois P. Heinz, Antidiagonals n = 0..12

Columns (or rows) k=0-5 give: A000012, A000079, A055099, A133357, A255255, A255262.

Main diagonal gives A018803.

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

Original entry on oeis.org

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

Victor S. Miller, Dec 21 2007

Figures obtained via clever exhaustion, using Gray Codes.

			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.

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

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

Cf. A133129, A255255.

Column k=3 of A255256.

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

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

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

cp's OEIS Frontend

A255256 Number A(n,k) of 2-colorings of a k X n rectangle such that no nontrivial subsquare has monochromatic corners; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

Extensions