A334159 -id:A334159 - cp's OEIS frontend

A140986 Number of n-colorings of the cubical graph.

0, 0, 2, 114, 2652, 29660, 198030, 932862, 3440024, 10599192, 28478970, 68716010, 152040372, 313269684, 608134982, 1122341430, 1983307440, 3375066032, 5556852594, 8885943522, 13845350540, 21077015820, 31421193342, 45962742254, 66085098312, 93532729800

Offset: 0

Jonathan Vos Post, Jul 28 2008

Eric M. Schmidt, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Cubical Graph
Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Cf. A296914, A334159.

a:= n-> n^8 -12*n^7 +66*n^6 -214*n^5 +441*n^4 -572*n^3 +423*n^2 -133*n:
seq(a(n), n=0..30);  # Alois P. Heinz, Mar 01 2009

A140986(n):=n^8-12*n^7+66*n^6-214*n^5+441*n^4-572*n^3 +423*n^2-133*n$
makelist(A140986(n),n,0,30); /* Martin Ettl, Nov 03 2012 */

a(n) = n^8-12*n^7+66*n^6-214*n^5+441*n^4-572*n^3+423*n^2-133*n.
G.f.: 2*x^2*(1+48*x+849*x^2+4864*x^3+8619*x^4+4848*x^5+931*x^6)/(1-x)^9. - Colin Barker, Apr 15 2012
a(n) = Sum_{k=1..8} k!*binomial(n,k)*A334159(3,k). - Andrew Howroyd, Apr 22 2020

More terms from Alois P. Heinz, Mar 01 2009

A334247 Number of acyclic orientations of the edges of an n-dimensional cube.

Original entry on oeis.org

1, 2, 14, 1862, 193270310, 47171704165698393638

Offset: 0

Matthew Scroggs, Apr 20 2020

a(n) is the absolute value of the chromatic polynomial of the n-hypercube graph evaluated at -1.

			For n=2, there are 14 ways to orient the edges of a square without cycles (see links).

David Eppstein, 14 acyclic orientations of a square
Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A334248 is the number of acyclic orientations with rotations and reflections of the same orientation excluded.
Cf. A140986, A158348, A296914, A334159, A334278.
Cf. A033815 (cross-polytope), A058809 (wheel), A338152 (demihypercube), A338153 (prism), A338154 (antiprism).

with(GraphTheory): with(SpecialGraphs):
a:= n-> abs(ChromaticPolynomial(HypercubeGraph(n), -1)):
seq(a(n), n=0..4);  # Alois P. Heinz, Jan 14 2025

a(n) = Sum_{k=1..2^n} (-1)^(2^n-k) * k! * A334159(n, k). - Andrew Howroyd, Apr 21 2020

a(n) = |Sum_{k=0..2^n} (-1)^k * A334278(n, k)|. - Peter Kagey, Oct 13 2020

a(5) from Andrew Howroyd, Apr 23 2020

A334278 Irregular table read by rows: T(n, k) is the coefficient of x^k in the chromatic polynomial of the cubical graph Q_n, 0 <= k <= 2^n.

Original entry on oeis.org

0, 1, 0, -1, 1, 0, -3, 6, -4, 1, 0, -133, 423, -572, 441, -214, 66, -12, 1, 0, -3040575, 14412776, -31680240, 43389646, -41821924, 30276984, -17100952, 7701952, -2794896, 818036, -191600, 35264, -4936, 496, -32, 1

Offset: 0

Peter Kagey, Apr 21 2020

The sums of the absolute values of the entries in each row gives A334247, the number of acyclic orientations of edges of the n-cube.

			Table begins:
n/k| 0     1    2     3    4     5   6    7  8
---+-------------------------------------------
  0| 0,    1
  1| 0,   -1,   1
  2| 0,   -3,   6,   -4,   1
  3| 0, -133, 423, -572, 441, -214, 66, -12, 1

Peter Kagey, Table of n, a(n) for n = 0..68 (rows 0..5; row 5 from Andrew Howroyd's file)
Andrew Howroyd, Chromatic Polynomials of Hypercubes Q_0 to Q_5
Eric Weisstein's World of Mathematics, Chromatic Polynomial.
Eric Weisstein's World of Mathematics, Hypercube Graph.

Cf. A296914 is the reverse of row 3.
Cf. A334279 is analogous for the n-dimensional cross-polytope, the dual of the n-cube.
Cf. A001787, A002378, A091940, A140986, A158348.
Cf. A334159, A334247, A334358.

with(GraphTheory): with(SpecialGraphs):
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(
    ChromaticPolynomial(HypercubeGraph(n), x)):
seq(T(n), n=0..4);  # Alois P. Heinz, Jan 14 2025

T[n_, k_] := Coefficient[ChromaticPolynomial[HypercubeGraph[n], x], x, k]

T(n,0) = 0.

T(n,k) = Sum_{i=1..2^n}, Stirling1(i,k) * A334159(n,i). - Andrew Howroyd, Apr 25 2020

A334358 Irregular triangle read by rows: row n gives scaled coefficients of the chromatic polynomial corresponding to colorings of the n-hypercube graph up to automorphism, highest powers first, 0 <= k <= 2^n.

Original entry on oeis.org

1, 0, 1, -1, 0, 1, -2, 3, -2, 0, 1, -12, 72, -256, 579, -812, 644, -216, 0, 1, -32, 496, -4936, 35276, -191840, 820328, -2808636, 7759343, -17276144, 30675244, -42494732, 44214736, -32375904, 14772272, -3125472, 0, 1, -80, 3160, -82080, 1575420, -23805776, 294640000

Offset: 0

Andrew Howroyd, Apr 24 2020

The polynomials are scaled by a factor of n!*2^n to ensure integer coefficients. When evaluated at x = k, they give the number of non-isomorphic k-colorings of the n-hypercube graph under the automorphism group of the graph. The size of the automorphism group is n!*2^n. Colors may not be interchanged.

			Triangle begins:
  0 | 1, 0;
  1 | 1, -1, 0;
  2 | 1, -2, 3, -2, 0;
  3 | 1, -12, 72, -256, 579, -812, 644, -216, 0;
  ...
The corresponding polynomials are:
  x;
  (x^2 - x)/(1!*2^1);
  (x^4 - 2*x^3 + 3*x^2 - 2*x)/(2!*2^2);
  (x^8 - 12*x^7 + 72*x^6 - 256*x^5 + 579*x^4 - 812*x^3 + 644*x^2 - 216*x)/(3!*2^3);
  ...
The polynomial (x^4 - 2*x^3 + 3*x^2 - 2*x)/(2!*2^2) gives A002817 when evaluated at integer values of x.

Andrew Howroyd, Table of n, a(n) for n = 0..68 (rows 0..5)
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A002817, A334159, A334248, A334356, A334357.

A296914 List of coefficients of chromatic polynomial of the cubical graph Q_3, highest order terms first.

Original entry on oeis.org

1, -12, 66, -214, 441, -572, 423, -133, 0

Offset: 1

N. J. A. Sloane, Dec 22 2017

Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Cubical Graph

Cf. A140986, A334159.

The chromatic polynomial is x^8-12*x^7+66*x^6-214*x^5+441*x^4-572*x^3+423*x^2-133*x.

a(n) = Sum_{k=1..8} Stirling1(k, 9-n)*A334159(3,k). - Andrew Howroyd, Apr 22 2020

A307334 Number of 3-colorings of an n-dimensional hypercube.

Original entry on oeis.org

3, 6, 18, 114, 2970, 1185282, 100301050602

Offset: 0

Aalok Sathe, Jul 24 2019

Prateek Bhakta, Benjamin Brett Buckner, Lauren Farquhar, Vikram Kamat, Sara Krehbiel, Heather M. Russell, Cut-Colorings in Coloring Graphs, Graphs and Combinatorics, (2019) 35(1), 239-248.
Luis Cereceda, Janvan den Heuvel, Matthew Johnson, Connectedness of the graph of vertex-colourings, Discrete Mathematics, (2008) 308(5-6), 913-919.
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Vertex Coloring
Wikipedia, Chromatic polynomial
Wikipedia, Hypercube

Cf. A334159.

a(n) = 3*A334159(n,1) + 6*A334159(n,2) + 6*A334159(n,3). - Andrew Howroyd, Apr 23 2020

a(6) from Andrew Howroyd, Apr 23 2020

A295176 Chromatic invariant of the n-hypercube graph.

Original entry on oeis.org

1, 1, 1, 11, 48253, 135327729523895

Offset: 0

Eric W. Weisstein, Nov 16 2017

Eric Weisstein's World of Mathematics, Chromatic Invariant
Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A295172, A295174, A334159.

a(n) = Sum_{k=2..2^n} (-1)^k*(k-2)!*A334159(n,k) for n > 0. - Andrew Howroyd, Apr 23 2020

a(5) from Andrew Howroyd, Apr 23 2020

A334359 Number of stable partitions of the n-hypercube graph.

Original entry on oeis.org

1, 1, 4, 354, 179185930, 258823757396708888836788

Offset: 0

Andrew Howroyd, Apr 25 2020

nonn

A stable partition is a partition of the vertices into sets so that no two vertices in a set are adjacent in the graph.

Equivalently, a(n) is the number of vertex colorings of the n-hypercube graph with any number of unlabeled colors. The vertices are not interchangeable.

			The a(2) = 4 stable partitions of the 2-dimensional hypercube are:
    1---2   1---2   1---2   1---2
    |   |   |   |   |   |   |   |
    2---1   2---3   3---1   3---4

Eric Weisstein's World of Mathematics, Hypercube Graph

Row sums of A334159.

cp's OEIS Frontend

A140986 Number of n-colorings of the cubical graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Maxima

Formula

Extensions

A334247 Number of acyclic orientations of the edges of an n-dimensional cube.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A334278 Irregular table read by rows: T(n, k) is the coefficient of x^k in the chromatic polynomial of the cubical graph Q_n, 0 <= k <= 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A334358 Irregular triangle read by rows: row n gives scaled coefficients of the chromatic polynomial corresponding to colorings of the n-hypercube graph up to automorphism, highest powers first, 0 <= k <= 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A296914 List of coefficients of chromatic polynomial of the cubical graph Q_3, highest order terms first.

Views

Author

Keywords

Links

Crossrefs

Formula

A307334 Number of 3-colorings of an n-dimensional hypercube.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A295176 Chromatic invariant of the n-hypercube graph.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A334359 Number of stable partitions of the n-hypercube graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs