A182368 -id:A182368 - 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)

A182406 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) is the number of n-colorings of the square grid graph G_(k,k).

Original entry on oeis.org

1, 0, 2, 0, 2, 3, 0, 2, 18, 4, 0, 2, 246, 84, 5, 0, 2, 7812, 9612, 260, 6, 0, 2, 580986, 6000732, 142820, 630, 7, 0, 2, 101596896, 20442892764, 828850160, 1166910, 1302, 8, 0, 2, 41869995708, 380053267505964, 50820390410180, 38128724910, 6464682, 2408, 9

Offset: 1

Alois P. Heinz, Apr 27 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.

			Square array A(n,k) begins:
  1,   0,       0,           0,                 0, ...
  2,   2,       2,           2,                 2, ...
  3,  18,     246,        7812,            580986, ...
  4,  84,    9612,     6000732,       20442892764, ...
  5, 260,  142820,   828850160,    50820390410180, ...
  6, 630, 1166910, 38128724910, 21977869327169310, ...

Eric Weisstein's World of Mathematics, Grid Graph
Wikipedia, Chromatic Polynomial

Columns k=1-7 give: A000027, A091940, A068239*2, A068240*2, A068241*2, A068242*2, A068243*2.
Rows n=1-20 give: A000007, A007395, A068253*3, A068254*4, A068255*5, A068256*6, A068257*7, A068258*8, A068259*9, A068260*10, A068261*11, A068262*12, A068263*13, A068264*14, A068265*15, A068266*16, A068267*17, A068268*18, A068269*19, A068270*20.
Cf. A182368.

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

A212084 Triangle T(n,k), n>=0, 0<=k<=2n, read by rows: row n gives the coefficients of the chromatic polynomial of the complete bipartite graph K_(n,n), highest powers first.

Original entry on oeis.org

1, 1, -1, 0, 1, -4, 6, -3, 0, 1, -9, 36, -75, 78, -31, 0, 1, -16, 120, -524, 1400, -2236, 1930, -675, 0, 1, -25, 300, -2200, 10650, -34730, 75170, -102545, 78610, -25231, 0, 1, -36, 630, -6915, 52080, -279142, 1074822, -2942445, 5552680, -6796926, 4787174

Offset: 0

Alois P. Heinz, Apr 30 2012

The complete bipartite graph K_(n,n) has 2n vertices and n^2 = A000290(n) edges. The chromatic polynomial of K_(n,n) has 2n+1 = A005408(n) coefficients.

			3 example graphs:                     +-----------+
.                 o        o   o      o   o   o   |
.                 |        |\ /|      |\ /|\ /|\ /
.                 |        | X |      | X | X | X
.                 |        |/ \|      |/ \|/ \|/ \
.                 o        o   o      o   o   o   |
.                                     +-----------+
Graph:         K_(1,1)    K_(2,2)      K_(3,3)
Vertices:         2          4            6
Edges:            1          4            9
The complete bipartite graph K_(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;
  1,  -1,   0;
  1,  -4,   6,    -3,     0;
  1,  -9,  36,   -75,    78,     -31,       0;
  1, -16, 120,  -524,  1400,   -2236,    1930,     -675, ...
  1, -25, 300, -2200, 10650,  -34730,   75170,  -102545, ...
  1, -36, 630, -6915, 52080, -279142, 1074822, -2942445, ...
  ...

Alois P. Heinz, Rows n = 0..90, flattened
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Wikipedia, Chromatic Polynomial

Columns k=0-2 give: A000012, (-1)*A000290, A083374.
Row sums and last elements of rows give: A000007.
Row lengths give: A005408.
Sums of absolute values of row elements give: A048163(n+1).
T(n,2n-1) = (-1)*A092552(n).
Cf. A008277, A212085, A182368, A185442, A193233, A193277, A193283, A266695, A266972.

P:= n-> add(Stirling2(n, k) *mul(q-i, i=0..k-1) *(q-k)^n, k=0..n):
T:= n-> seq(coeff(P(n), q, 2*n-k), k=0..2*n):
seq(T(n), n=1..8);

T(n,k) = [q^(2n-k)] Sum_{j=0..n} (q-j)^n * S2(n,j) * Product_{i=0..j-1} (q-i).

T(0,0)=1 prepended by Alois P. Heinz, May 03 2024

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

A182406 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) is the number of n-colorings of the square grid graph G_(k,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A212084 Triangle T(n,k), n>=0, 0<=k<=2n, read by rows: row n gives the coefficients of the chromatic polynomial of the complete bipartite graph K_(n,n), highest powers first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

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

Extensions