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

0, 0, 840, 12477384, 2545607472, 116307115440, 2406303387000, 30037635498360, 262918567435104, 1765904422135392, 9653659287290280, 44745048366882600, 181129909217550480, 654743996230865424, 2149893215016113112, 6499426966335074520, 18286786291862020800

Offset

0,3

Comments

The square grid graph G_(4,4) has 16 vertices, 24 edges and 36 rectangles with sides parallel to the axes.

a(4) = A200045(4,4) = 2545607472.

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^14 +n^13 +n^12 -35*n^11 -35*n^10 +61*n^9 +547*n^8 -101*n^7 -1797*n^6 -633*n^5 +5655*n^4 -5625*n^3 +3684*n^2 -2436*n +852).

G.f.: -24 *x^2 *(1473*x^14 +32720*x^13 +4197221*x^12 +209614896*x^11 +3974036005*x^10 +33181507744*x^9 +132190513545*x^8 +263917493088*x^7 +267855509283*x^6 +135288479760*x^5 +31950100783*x^4 +3113672560*x^3 +97233591*x^2 +519296*x+35) / (x-1)^17.

Maple

a:= n-> ((((((((((((n^3-36)*n^2+96)*n+486)*n-648)*n-1696)*n
    +1164)*n+6288)*n-11280)*n+9309)*n-6120)*n+3288)*n-852)*n:
seq(a(n), n=0..30);

Crossrefs

Cf. A200045, A252778, A252779, A252839.

Sequence in context: A331652 A364179 A269894 * A364264 A362440 A159690

Adjacent sequences: A252777 A252778 A252779 * A252781 A252782 A252783

Keyword

nonn,easy

Author

Alois P. Heinz, Dec 21 2014

Status

approved