The goal of this challenge is to check and extend the OEIS sequence A334248: Number of distinct acyclic orientations of the edges of an n-dimensional cube.

Take an n-dimensional cube (if n=1, this is a line; if n=2, a square; if n=3, a cube; if n=4, a hypercube/tesseract; etc), and give a direction to all of its edges so that no cycles are formed. The terms of the sequence are the number of (rotationally and reflectively) distinct orientations that can be obtained.


For n=2, there are 14 ways to assign directions to the edges of a square with no cycles formed:

Acyclic orientations of a cube

However, only three of these are distinct if they are rotated and reflected:

Three distinct acyclic orientations

So when n=2, the answer is 3.

The winner of this challenge will be the program that calculates the most terms when run on my computer (Ubuntu, 64GB RAM) in one hour. If there is a tie, the program that computes the terms in the shortest time will be the winner.

  • 2
    \$\begingroup\$ You should consider extending the challenge to include n=5. Or make the winning criterion the number of terms that can be computed in under an hour. \$\endgroup\$ Commented Apr 22, 2020 at 7:44
  • \$\begingroup\$ This is a better criterion, I'll adjust it \$\endgroup\$
    – mscroggs
    Commented Apr 22, 2020 at 7:53
  • 6
    \$\begingroup\$ Oh gosh, this is counting among the exponentially many orientations of graphs that are themselves exponential in size, which likely gives doubly exponential growth. Finding more terms for OEIS will be hard. \$\endgroup\$
    – xnor
    Commented Apr 22, 2020 at 8:11
  • \$\begingroup\$ I'm afraid running time goes up so quickly that any stupid program works 4 out quickly but quite optimized one can't do with 5 \$\endgroup\$
    – l4m2
    Commented Apr 22, 2020 at 13:56
  • 2
    \$\begingroup\$ The OEIS sequence has been updated to reflect that A334248(5) = 12284402192625939. Any hope of computing the next term? Obviously this isn’t something that can be brute forced. \$\endgroup\$ Commented Apr 25, 2020 at 16:45

1 Answer 1


Wolfram Language (Mathematica), n = 4, <1 second on my computer

(* Elements of the hyperoctahedral group,represented by matrices *)
HyperoctahedralGroup[n_] := 
  Join @@ Table[
    Permute[IdentityMatrix@n, perm]*sign, {perm, 
     Permutations@Range@n}, {sign, Tuples[{1, -1}, n]}];

(* Action of group elements on a vertex of the hypercube,
where each vertex is represented by an integer from 1 to 2^n *)
ActOn[n_, g_, v_] := 
  FromDigits[(1 + (IntegerDigits[v - 1, 2, n]*2 - 1) . g)/2, 2] + 1;

(* Orbits of vertices under such action *)
Orbits[n_, g_] := 
  ConnectedComponents@Table[v <-> ActOn[n, g, v], {v, 2^n}];

(* Whether any orbit contains adjacent vertices *)
OrbitConatinsAdjacentVertices[edges_, orbits_] := 
  Or @@ Or @@@ Outer[SubsetQ, orbits, edges, 1];

(* Merging vertices in each orbit into a single vertex *)
MergeVertices[edges_, orbits_] := 
    Sort /@ (edges /. (Alternatives@##2 -> #1 & @@@ orbits))];

(* Number of acyclic orientations fixed by some group element *)
InvariantAcyclicOrientations[n_, edges_, g_] := 
  With[{orbits = Orbits[n, g]}, 
   If[OrbitConatinsAdjacentVertices[edges, orbits], 0, 
    Abs[ChromaticPolynomial[MergeVertices[edges, orbits], -1]]]];

(* OEIS sequence A334248 *)
A334248[n_] := 
  With[{edges = List @@@ EdgeList@HypercubeGraph@n}, 
   Sum[InvariantAcyclicOrientations[n, edges, g], {g, 

Do[Print[n -> A334248[n]], {n, 1, 4}]

Try it online!

Not really optimized. Takes less than 1 seconds on my computer to calculate the first four terms, but takes forever for the fifth term. It seems that Mathematica cannot compute the chromatic polynomial of HypercubeGraph[5] in a reasonable time.

Based on Peter Kagey's deleted answer (which did not consider rotations and reflections), and uses Burnside's lemma.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.