A333418 -id:A333418 - cp's OEIS frontend

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

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

A333444 Number of 2-colorings of edges of the n-cube up to isometry.

Original entry on oeis.org

2, 6, 144, 11251322, 314824456456819827136, 136221825854745676520058554256163406987047485113810944

Offset: 1

Peter Kagey, Mar 21 2020

nonn

Bounded below by ceiling(2^A001787(n)/A000165(n)).

Peter Kagey, Table of n, a(n) for n = 1..9
Mathematics Stack Exchange user joriki, Number of 2-colorings of edges of the n-dimensional cube?.
Wikipedia, Hypercube

Row sums of A333418.

Cf. A000165, A001787, A199406, A331359.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions