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

1, 1, 3, 54, 511863, 12284402192625939

Offset: 0

Author

Matthew Scroggs, Apr 20 2020

Keywords

• nonn
• more

Comments

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

Links

• 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.

Crossrefs

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

Cf. A334358.

Formula

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

Extensions

a(5) from Andrew Howroyd, Apr 24 2020