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

1, 1, 3, 54, 511863, 12284402192625939

Offset

0,3

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

Table of n, a(n) for n=0..5.

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.

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

Crossrefs

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

Cf. A334358.

Sequence in context: A214006 A154604 A188798 * A193256 A319038 A340214

Adjacent sequences: A334245 A334246 A334247 * A334249 A334250 A334251

Keyword

nonn,more

Author

Matthew Scroggs, Apr 20 2020

Extensions

a(5) from Andrew Howroyd, Apr 24 2020

Status

approved