A182406 -id:A182406 - cp's OEIS frontend

A068239 1/2 the number of colorings of a 3 X 3 square array with n colors.

1, 123, 4806, 71410, 583455, 3232341, 13675228, 47502036, 141991245, 377162335, 910842306, 2033854758, 4253012491, 8411348505, 15856955640, 28673921896, 49991146713, 84387303171, 138412872190, 221253017370, 345558093111, 528471784093, 792890261076

Offset: 2

R. H. Hardin, Feb 24 2002

nonn

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

Cf. A068239-A068305, A000332, A002417, A027441, A182368, A182406.

a:= n-> (79+(-323+(594+(-648+(459+(-216+(66+(-12+n)*n)*n) *n)*n)*n)*n)*n) *n/2:
seq(a(n), n=2..30); # Alois P. Heinz, Apr 27 2012

From Alois P. Heinz, Apr 27 2012: (Start)
G.f.: x^2*(1199*x^7 +16567*x^6 +60099*x^5 +71075*x^4 +28765*x^3 +3621*x^2 +113*x+1) / (x-1)^10.
a(n) = (79*n -323*n^2 +594*n^3 -648*n^4 +459*n^5 -216*n^6 +66*n^7 -12*n^8 +n^9) / 2.
(End)

A182368 Triangle T(n,k), n>=1, 0<=k<=n^2, read by rows: row n gives the coefficients of the chromatic polynomial of the square grid graph G_(n,n), highest powers first.

Original entry on oeis.org

1, 0, 1, -4, 6, -3, 0, 1, -12, 66, -216, 459, -648, 594, -323, 79, 0, 1, -24, 276, -2015, 10437, -40614, 122662, -292883, 557782, -848056, 1022204, -960627, 682349, -346274, 112275, -17493, 0, 1, -40, 780, -9864, 90798, -647352, 3714180, -17590911, 69997383

Offset: 1

Alois P. Heinz, Apr 26 2012

The square grid graph G_(n,n) has n^2 = A000290(n) vertices and 2*n*(n-1) = A046092(n-1) edges. The chromatic polynomial of G_(n,n) has n^2+1 = A002522(n) coefficients.

			3 example graphs:                          o---o---o
.                                          |   |   |
.                             o---o        o---o---o
.                             |   |        |   |   |
.                o            o---o        o---o---o
Graph:        G_(1,1)        G_(2,2)        G_(3,3)
Vertices:        1              4              9
Edges:           0              4             12
The square grid graph G_(2,2) is the cycle graph C_4 with chromatic polynomial q^4 -4*q^3 +6*q^2 -3*q => row 2 = [1, -4, 6, -3, 0].
Triangle T(n,k) begins:
  1,    0;
  1,   -4,     6,      -3,        0;
  1,  -12,    66,    -216,      459,       -648,         594, ...
  1,  -24,   276,   -2015,    10437,     -40614,      122662, ...
  1,  -40,   780,   -9864,    90798,    -647352,     3714180, ...
  1,  -60,  1770,  -34195,   486210,   -5421612,    49332660, ...
  1,  -84,  3486,  -95248,  1926585,  -30755376,   403410654, ...
  1, -112,  6216, -227871,  6205479, -133865298,  2382122274, ...
  1, -144, 10296, -487280, 17169852, -480376848, 11114098408, ...
  ...

Alois P. Heinz, Rows n = 1..9, flattened
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Grid Graph
Wikipedia, Chromatic Polynomial

Columns 0, 1 give: A000012, (-1)*A046092(n-1).
Sums of absolute values of row elements give: A080690(n).
Cf. A000290, A002522, A182406, A185442, A193233, A193277, A193283.

Reverse /@ CoefficientList[Table[ChromaticPolynomial[GridGraph[{n, n}], x], {n, 5}], x] // Flatten (* Eric W. Weisstein, May 01 2017 *)

A091940 Given n colors, sequence gives number of ways to color the vertices of a square such that no edge has the same color on both of its vertices.

Original entry on oeis.org

0, 2, 18, 84, 260, 630, 1302, 2408, 4104, 6570, 10010, 14652, 20748, 28574, 38430, 50640, 65552, 83538, 104994, 130340, 160020, 194502, 234278, 279864, 331800, 390650, 457002, 531468, 614684, 707310, 810030, 923552, 1048608, 1185954, 1336370, 1500660

Offset: 1

Ryan Witko (witko(AT)nyu.edu), Mar 11 2004

Also equals the number of pairs of pairs ((a_1,a_2),(b_1,b_2)) that are disjoint (a_i != b_j) where all elements belong to {1,...,n}. See A212085. - Lewis Baxter, Mar 06 2023

			a(4) = 84 since there are 84 different ways to color the vertices of a square with 4 colors such that no two vertices that share an edge are the same color.
There are 4 possible colors for the first vertex and 3 for the second vertex. For the third vertex, divide into two cases: the third vertex can be the same color as the first vertex, and then the fourth vertex has 3 possible colors (4 * 3 * 1 * 3 = 36 colorings). Or the third vertex can be a different color from the first vertex, and then the fourth vertex has 2 possible colors (4 * 3 * 2 * 2 = 48 colorings). So there are a total of 36 + 48 = 84. - _Michael B. Porter_, Jul 24 2016

Alois P. Heinz, Table of n, a(n) for n = 1..1000
OEIS Wiki, Colorings of square grid graphs
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Column k=2 of A212085.
Cf. A027441, A182368, A182406.
Cf. A000217, A002061.

a := n -> (n-1)+(n-1)^4; for n to 35 do a(n) end do; # Rainer Rosenthal, Dec 03 2006

Table[2Binomial[n, 2] + 12Binomial[n, 3] + 24Binomial[n, 4], {n, 35}] (* Robert G. Wilson v, Mar 16 2004 *)
Table[(n-1)^4+(n-1),{n,1,60}] (* Vladimir Joseph Stephan Orlovsky, May 12 2011 *)

a(n) = 2*C(n,2) + 12*C(n,3) + 24*C(n,4) = n*(n-1)*(n^2-3*n+3).
a(n) = (n-1) + (n-1)^4. - Rainer Rosenthal, Dec 03 2006
G.f.: 2*x^2*(1+4*x+7*x^2)/(1-x)^5. a(n) = 2*A027441(n-1). - R. J. Mathar, Sep 09 2008
For n > 1, a(n) = floor(n^7/(n^3-1)). - Gary Detlefs, Feb 10 2010
a(n) = 2 * A000217(n-1) * A002061(n-1), n >= 1. - Daniel Forgues, Jul 14 2016
E.g.f.: exp(x)*x^2*(1 + x)^2. - Stefano Spezia, Oct 08 2022

More terms from Robert G. Wilson v, Mar 16 2004

A343095 Array read by antidiagonals: T(n,k) is the number of k-colorings of an n X n grid, up to rotational symmetry.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 6, 1, 0, 1, 4, 24, 140, 1, 0, 1, 5, 70, 4995, 16456, 1, 0, 1, 6, 165, 65824, 10763361, 8390720, 1, 0, 1, 7, 336, 489125, 1073758336, 211822552035, 17179934976, 1, 0, 1, 8, 616, 2521476, 38147070625, 281474993496064, 37523658921114744, 140737496748032, 1, 0

Offset: 0

Andrew Howroyd, Apr 14 2021

			Array begins:
====================================================================
n\k | 0 1       2            3               4                 5
----+---------------------------------------------------------------
  0 | 1 1       1            1               1                 1 ...
  1 | 0 1       2            3               4                 5 ...
  2 | 0 1       6           24              70               165 ...
  3 | 0 1     140         4995           65824            489125 ...
  4 | 0 1   16456     10763361      1073758336       38147070625 ...
  5 | 0 1 8390720 211822552035 281474993496064 74505806274453125 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..860
Peter Kagey and William Keehn, Counting tilings of the n X m grid, cylinder, and torus, arXiv:2311.13072 [math.CO], 2023. See p. 3.

Rows 0..5 are A000012, A001477, A006528, A282613, A283027, A283031.
Columns 0..10 are A000007, A000012, A047937, A047938, A047939, A047940, A047941, A047942, A047943, A047944, A047945.
Main diagonal is A343096.
Cf. A182406, A246106, A343097, A343874.

{{1}}~Join~Table[Function[n, (k^(n^2) + 2*k^((n^2 + 3 #)/4) + k^((n^2 + #)/2))/4 &[Mod[n, 2] ] ][m - k + 1], {m, 0, 8}, {k, m + 1, 0, -1}] // Flatten (* Michael De Vlieger, Nov 30 2023 *)

T(n,k) = (k^(n^2) + 2*k^((n^2 + 3*(n%2))/4) + k^((n^2 + (n%2))/2))/4

T(n,k) = (k^(n^2) + 2*k^((n^2 + 3*(n mod 2))/4) + k^((n^2 + (n mod 2))/2))/4.

A068253 1/3 of the number of colorings of an n X n square array with 3 colors.

Original entry on oeis.org

1, 6, 82, 2604, 193662, 33865632, 13956665236, 13574876544396, 31191658416342674, 169426507164530254380, 2176592549084872196370724, 66158464020552857153017287240, 4759146677426447759184119036493676, 810410082813497381147177065840601910384

Offset: 1

R. H. Hardin, Feb 24 2002

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..24

Cf. A068239-A068305, A000332, A002417, A027441, A182368, A182406.
See A047938 for number of improper colorings.
Main diagonal of A078099.
Twice A207993 for n>1.

M[1] = {{1}}; M[m_] := M[m] = {{M[m - 1], Transpose[M[m - 1]]}, {Array[0 &, {2^(m - 2), 2^(m - 2)}], M[m - 1]}} // ArrayFlatten; W[m_] := M[m] + Transpose[M[m]]; T[m_, 1] := 2^(m - 1); T[1, n_] := 2^(n - 1); T[m_, n_] := MatrixPower[W[m], n - 1] // Flatten // Total; a[n_] := T[n, n]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 12}] (* Jean-François Alcover, Nov 01 2017, after code from A078099 *)

For formula see A078099.

More terms from Vladeta Jovovic, Jul 22 2004
a(11)-a(12) from Alois P. Heinz, Mar 25 2009
a(13)-a(14) from Andrew Howroyd, Jun 26 2017

A068254 1/4 the number of colorings of an n X n square array with 4 colors.

Original entry on oeis.org

1, 21, 2403, 1500183, 5110723191, 95013316876491, 9639473169171326643, 5336900216006709884938623, 16124704040675904181778734982451, 265865038636937159336134567410478299051

Offset: 1

R. H. Hardin, Feb 24 2002

nonn

Jean-François Alcover, Table of n, a(n) for n = 1..16

Main diagonal of A222444.

Cf. A068239-A068305, A000332, A002417, A027441, A182368, A182406.

A222444 = Cases[Import["https://oeis.org/A222444/b222444.txt", "Table"], {, }][[All, 2]];
a[n_] := A222444[[2 n^2 - 2 n + 1]];
Table[a[n], {n, 1, 16}] (* Jean-François Alcover, Sep 23 2019 *)

a(9)-a(10) from Alois P. Heinz, Apr 27 2012

A068255 1/5 the number of colorings of an n X n square array with 5 colors.

Original entry on oeis.org

1, 52, 28564, 165770032, 10164078082036, 6584229526795818280, 45062665956031451017237456, 3258395057698765483724093981321824, 2489232886416012985921659124731697904597044, 20091032492258710696689787524926465967570325433558752

Offset: 1

R. H. Hardin, Feb 24 2002

nonn

Jean-François Alcover, Table of n, a(n) for n = 1..14

Main diagonal of A222144.

Cf. A068239-A068305, A000332, A002417, A027441, A182368, A182406.

A222144 = Cases[Import["https://oeis.org/A222144/b222144.txt", "Table"], {, }][[All, 2]];
a[n_] := A222144[[2 n^2 - 2 n + 1]];
Table[a[n], {n, 1, 14}] (* Jean-François Alcover, Sep 23 2019 *)

a(8)-a(10) from Alois P. Heinz, Apr 27 2012

A068256 1/6 the number of colorings of an n X n square array with 6 colors.

Original entry on oeis.org

1, 105, 194485, 6354787485, 3662978221194885, 37246546285522069805565, 6681224184095576349599961437005, 21141920893108925844961568245788270386085, 1180188030501408210062775052100916976604905321333565, 1162187850685436026547128866816039344195930156602955871508107885

Offset: 1

R. H. Hardin, Feb 24 2002

nonn

Jean-François Alcover, Table of n, a(n) for n = 1..13

Main diagonal of A222281.

Cf. A068239-A068305, A000332, A002417, A027441, A182368, A182406.

A222281 = Cases[Import["https://oeis.org/A222281/b222281.txt", "Table"], {, }][[All, 2]];
a[n_] := A222281[[2 n^2 - 2 n + 1]];
Table[a[n], {n, 1, 13}] (* Jean-François Alcover, Sep 23 2019 *)

a(8)-a(10) from Alois P. Heinz, Apr 27 2012

A068257 1/7 the number of colorings of an n X n square array with 7 colors.

Original entry on oeis.org

1, 186, 923526, 122408393436, 433110977725751106, 40908457493732914322944536, 103146129375410533061371714364918916, 6942544711174164051575906086886643368922134556, 12474132532762777585883439690925675118905860580968258566406

Offset: 1

R. H. Hardin, Feb 24 2002

nonn

Jean-François Alcover, Table of n, a(n) for n = 1..13

Main diagonal of A222340.

Cf. A068239-A068305, A000332, A002417, A027441, A182368, A182406.

A222340 = Cases[Import["https://oeis.org/A222340/b222340.txt", "Table"], {, }][[All, 2]];
a[n_] := A222340[[2 n^2 - 2 n + 1]];
Table[a[n], {n, 1, 13}] (* Jean-François Alcover, Sep 23 2019 *)

a(7)-a(9) from Alois P. Heinz, Apr 27 2012

A068258 1/8 the number of colorings of an n X n square array with 8 colors.

Original entry on oeis.org

1, 301, 3418807, 1465295106499, 23698346512668445387, 14462834689097706163375677127, 333066712033498255371201983520013525951, 289435280548175417311368841643540798029239265418611, 9491047284937011500293532002379383630495589849878668222747216079

Offset: 1

R. H. Hardin, Feb 24 2002

nonn

Jean-François Alcover, Table of n, a(n) for n = 1..12

Main diagonal of A222462.

Cf. A068239-A068305, A000332, A002417, A027441, A182368, A182406.

A222462 = Cases[Import["https://oeis.org/A222462/b222462.txt", "Table"], {, }][[All, 2]];
a[n_] := A222462[[2 n^2 - 2 n + 1]];
Table[a[n], {n, 1, 12}] (* Jean-François Alcover, Sep 23 2019 *)

a(6)-a(9) from Alois P. Heinz, Apr 27 2012

cp's OEIS Frontend

A068239 1/2 the number of colorings of a 3 X 3 square array with n colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A182368 Triangle T(n,k), n>=1, 0<=k<=n^2, read by rows: row n gives the coefficients of the chromatic polynomial of the square grid graph G_(n,n), highest powers first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A091940 Given n colors, sequence gives number of ways to color the vertices of a square such that no edge has the same color on both of its vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A343095 Array read by antidiagonals: T(n,k) is the number of k-colorings of an n X n grid, up to rotational symmetry.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A068253 1/3 of the number of colorings of an n X n square array with 3 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A068254 1/4 the number of colorings of an n X n square array with 4 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A068255 1/5 the number of colorings of an n X n square array with 5 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A068256 1/6 the number of colorings of an n X n square array with 6 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica