A334248 - OEIS

%I #27 Aug 12 2022 09:16:37

%S 1,1,3,54,511863,12284402192625939

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

%C 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.

%C 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

%H Matthew Scroggs, <a href="https://github.com/mscroggs/acyclic-orientations/blob/master/a334248.py">Python code to calculate A334248</a>.

%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/666987/combinatorial-problem-directed-acyclic-graph/673620#673620">Combinatorial problem: Directed Acyclic Graph</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Acyclic_orientation">Acyclic orientation</a>.

%F 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

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

%Y Cf. A334358.

%K nonn,more

%O 0,3

%A _Matthew Scroggs_, Apr 20 2020

%E a(5) from _Andrew Howroyd_, Apr 24 2020