A252778 Number of ways of n-coloring the square grid graph G_(3,3) such that no rectangle exists with sides parallel to the axes having all 4 corners of the same color.

0, 0, 156, 14298, 228984, 1821420, 9676020, 39328086, 131914608, 382726584, 991134540, 2342199090, 5133181416, 10561434468, 20593784484, 38341504110, 68569332960, 118371718896, 198054533628, 322265959434, 511426049880, 793510636380, 1206251784276

Offset

0,3

Comments

The square grid graph G_(3,3) has 9 vertices, 12 edges and 9 rectangles with sides parallel to the axes.

a(4) = A200045(3,3) = 228984.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Eric Weisstein's World of Mathematics, Grid Graph

Formula

a(n) = n*(n-1)*(n^7+n^6+n^5-8*n^4-8*n^3+4*n^2+22*n-14).

G.f.: 6 *x^2 *(11*x^7 +92*x^6 +2829*x^5 +13850*x^4 +26045*x^3 +15504*x^2 +2123*x +26) / (x-1)^10.

Maple

a:= n-> (((((n^3-9)*n^2+12)*n+18)*n-36)*n+14)*n:
seq(a(n), n=0..30);

Crossrefs

Cf. A200045, A252779, A252780, A252839.

Sequence in context: A240005 A035838 A035824 * A006112 A239410 A216788

Adjacent sequences: A252775 A252776 A252777 * A252779 A252780 A252781

Keyword

nonn,easy

Author

Alois P. Heinz, Dec 21 2014

Status

approved