A334358 -id:A334358 - cp's OEIS frontend

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.

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

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

Original entry on oeis.org

1, 1, 3, 54, 511863, 12284402192625939

Offset: 0

Matthew Scroggs, Apr 20 2020

a(n) is the number of acyclic orientations of the edges of an n-dimensional cube, with rotations and reflections of the same orientation not counted.

Except for n=0 and n=2, a(n) can be obtained by substituting -1 for x in the chromatic polynomials given in A334358. This fails for n = 2 because the square when folded diagonally gives a graph with an odd number of vertices. The contribution from this graph needs to be negated when determining the number of acyclic orientations. - Andrew Howroyd, Apr 24 2020

Matthew Scroggs, Python code to calculate A334248.
Mathematics Stack Exchange, Combinatorial problem: Directed Acyclic Graph.
Eric Weisstein's World of Mathematics, Hypercube Graph.
Wikipedia, Acyclic orientation.

Cf. A333418. A334247 is the number of acyclic orientations with rotations and reflections of the same orientation included.

Cf. A334358.

a(n) = Sum_{k=1..2^n} (-1)^k * A334358(n, 2^n-k)/(n!*2^n) for n >= 3. - Andrew Howroyd, Apr 24 2020

a(5) from Andrew Howroyd, Apr 24 2020

A334356 Number of nonequivalent proper colorings of the vertices of a cube using at most n colors up to rotations and reflections of the cube.

Original entry on oeis.org

0, 1, 15, 154, 1115, 5955, 24836, 85260, 251154, 655005, 1548085, 3374646, 6876805, 13237679, 24271170, 42667640, 72305556, 118640025, 189179979, 294066610, 446766495, 664893691, 971175920, 1394580804, 1971618950, 2747841525, 3779550801, 5135742990, 6900303529

Offset: 1

Andrew Howroyd, Apr 24 2020

Adjacent vertices may not have the same color.

a(n) is the number of nonequivalent n-colorings of the cubical graph up to graph isomorphism.

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Cubical Graph
Eric Weisstein's World of Mathematics, Vertex Coloring
Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Cf. A128766, A140986, A334357, A334358.

a(n) = {n*(n - 1)*(n^6 - 11*n^5 + 61*n^4 - 195*n^3 + 384*n^2 - 428*n + 216)/48}

a(n) = n*(n - 1)*(n^6 - 11*n^5 + 61*n^4 - 195*n^3 + 384*n^2 - 428*n + 216)/48.

a(n) = Sum_{k=1..8} n^k * A334358(3,8-k) / 48.

A334357 Number of nonequivalent proper colorings of the vertices of a 4D hypercube using at most n colors up to rotations and reflections of the cube.

Original entry on oeis.org

0, 1, 72, 7173, 610160, 28654530, 723903411, 11151501102, 117740542158, 928786063095, 5822688352360, 30338870238171, 135818642249082, 535712216425568, 1898338161488055, 6136965479845740, 18323823959847156, 51039512178104637, 133722394132080528

Offset: 1

Andrew Howroyd, Apr 24 2020

Adjacent vertices may not have the same color.

a(n) is the number of nonequivalent n-colorings of the tesseract graph up to graph isomorphism.

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Tesseract Graph
Eric Weisstein's World of Mathematics, Vertex Coloring
Index entries for linear recurrences with constant coefficients, signature (17,-136,680,-2380,6188,-12376,19448,-24310,24310,-19448,12376,-6188,2380,-680,136,-17,1).

Cf. A128767, A158348, A334356, A334358.

a(n) = n*(n - 1)*(n^14 - 31*n^13 + 465*n^12 - 4471*n^11 + 30805*n^10 - 161035*n^9 + 659293*n^8 - 2149343*n^7 + 5610000*n^6 - 11666144*n^5 + 19009100*n^4 - 23485632*n^3 + 20729104*n^2 - 11646800*n + 3125472)/384.

a(n) = Sum_{k=1..16} n^k * A334358(4,16-k) / 384.

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A334356 Number of nonequivalent proper colorings of the vertices of a cube using at most n colors up to rotations and reflections of the cube.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A334357 Number of nonequivalent proper colorings of the vertices of a 4D hypercube using at most n colors up to rotations and reflections of the cube.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula