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

1, 2, 14, 1862, 193270310, 47171704165698393638

Offset: 0

Author

Matthew Scroggs, Apr 20 2020

Keywords

• nonn
• more

Comments

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

Examples

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

Links

• David Eppstein, 14 acyclic orientations of a square
• Eric Weisstein's World of Mathematics, Hypercube Graph

Crossrefs

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

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

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

Programs

Maple

with(GraphTheory): with(SpecialGraphs):
a:= n-> abs(ChromaticPolynomial(HypercubeGraph(n), -1)):
seq(a(n), n=0..4);  # Alois P. Heinz, Jan 14 2025

Formula

a(n) = Sum_{k=1..2^n} (-1)^(2^n-k) * k! * A334159(n, k). - Andrew Howroyd, Apr 21 2020

a(n) = |Sum_{k=0..2^n} (-1)^k * A334278(n, k)|. - Peter Kagey, Oct 13 2020

Extensions

a(5) from Andrew Howroyd, Apr 23 2020