login
Number of acyclic orientations of the edges of an n-dimensional cube.
7

%I #37 Feb 16 2025 08:34:00

%S 1,2,14,1862,193270310,47171704165698393638

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

%C a(n) is the absolute value of the chromatic polynomial of the n-hypercube graph evaluated at -1.

%H David Eppstein, <a href="https://commons.wikimedia.org/wiki/File:Acyclic_orientations_of_C4.svg">14 acyclic orientations of a square</a>

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

%F a(n) = Sum_{k=1..2^n} (-1)^(2^n-k) * k! * A334159(n, k). - _Andrew Howroyd_, Apr 21 2020

%F a(n) = |Sum_{k=0..2^n} (-1)^k * A334278(n, k)|. - _Peter Kagey_, Oct 13 2020

%e For n=2, there are 14 ways to orient the edges of a square without cycles (see links).

%p with(GraphTheory): with(SpecialGraphs):

%p a:= n-> abs(ChromaticPolynomial(HypercubeGraph(n), -1)):

%p seq(a(n), n=0..4); # _Alois P. Heinz_, Jan 14 2025

%Y Cf. A334248 is the number of acyclic orientations with rotations and reflections of the same orientation excluded.

%Y Cf. A140986, A158348, A296914, A334159, A334278.

%Y Cf. A033815 (cross-polytope), A058809 (wheel), A338152 (demihypercube), A338153 (prism), A338154 (antiprism).

%K nonn,more,changed

%O 0,2

%A _Matthew Scroggs_, Apr 20 2020

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