[seqfan] A hard sequence. Can anyone compute the next term?

Andrew Weimholt andrew.weimholt at gmail.com
Tue Jun 14 20:16:48 CEST 2011


Let a(n) = the number of ways to color the vertices
of an n-cube (red and black) such that each of its
(n-1)-cubes has a different number of red vertices.

Configurations that differ by rotations and reflections
of the cube and inversions of color are considered
equivalent.

For n=0, there are no (n-1)-cubes, so it trivially
satisfies the requirement that each (n-1)-cube
have a different number of red vertices.
So a(0)=1

For n=1, the (n-1)-cubes are the vertices themselves,
so there is one way to assign them different colors.
a(1) = 1

For n=2, and n=3, there are more (n-1)-cubes than
possible values for the number of red vertices on
an n-cube, so a(2)=0, a(3)=0

For n=4, there are also no solutions.
There are 8 cubes on the tesseract, and 9 possible
values for the number of red vertices [0..8].
Since each 3-cube must have a different number
of red vertices, there must either be a cube with
0 red vertices, or a cube with 8. This limits
the possible values of red vertices of all
6 neighboring cubes to one of 4 values, so a
solution for n=4 is impossible.
a(4)=0

For n=5, there are 5 solutions.

So the sequence begins   1,1,0,0,0,5,...

My brute force algorithm for computing this
sequence is O(2^n), so it won't be feasible
to use it for computing the next term.
Can anyone come up with a better way for
computing more terms?

Andrew



More information about the SeqFan mailing list