login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A334248 Number of distinct acyclic orientations of the edges of an n-dimensional cube. 3
1, 1, 3, 54, 511863, 12284402192625939 (list; graph; refs; listen; history; text; internal format)
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.

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 A227054

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 11 04:03 EDT 2020. Contains 336421 sequences. (Running on oeis4.)