|
 |
Hi,
I need an algorithem (is that correctly spelled?) to get all edges of an
4d cube only once. Counting gives me 32 edges, writing them down gives
me 31 in one way, 34 in another way. So I thought, I better find an
algorithem, but I can't find one.
I only need to know what points are connected.
Can you help me?
Thanks in advance,
Remco Poelstra
Post a reply to this message
|
|
|
|
Remco Poelstra wrote:
> I need an algorithem (is that correctly spelled?) to get all edges of an
> 4d cube only once. Counting gives me 32 edges, writing them down gives
> me 31 in one way, 34 in another way. So I thought, I better find an
> algorithem, but I can't find one.
> I only need to know what points are connected.
> Can you help me?
The number of edges in the 4-cube should be 32.
Here's an algorithm.
Assume the vertices of a cube in n-space are at the points whose
coordinates are all ones and zeroes ("1s" and "0s"): for example, the
3-cube has eight vertices: 000, 100, 010, 001, 110, 101, 011, 111.
(000 is lazy but unambiguous notation for (0,0,0), for example)
Let the dimension of the space be n, so the coordinate will be a
string of n bits. Define the "level" of a vertex to be the number of
1s in its label, so level 0 is just the vertex at the origin, and the
highest level point has n 1s. On level L, there are (n choose L)
vertices.
Notice that to get from a vertex to an adjacent vertex (i.e., along
one of the edges we are trying to count), exactly one digit changes,
either from 0 to 1 (so the level increases) or from 1 to 0 (so the
level decreases). There aren't any adjacent vertices on the same
level.
To count the edges, start at the lowest level (L=0). There are n ways
to change a single 0 to a 1, so there are n edges at the vertex at the
origin. (of course, there are n edges at each vertex, but to avoid
counting them twice, we'll ignore this fact.)
At each of the (n choose L) vertices on level L, count how many edges
there are to the next higher level. This means if there are L 1s,
then there are (n-L) 0s, and we want to change one of them to a 1.
Counting only these (n-L) edges, and not the edges back to the
previous level, makes sure we don't count any twice.
The last step in the algorithm is level L=n, when there are no 0s
remaining, and no new edges to count.
So, the resulting total of edges counted is: (n-L) edges to the next
level, at each of the (n choose L) vertices on level L, for each of
the levels from L=0 through L=n, for a total of:
(sum from L=0 to L=n) (n-L)*(n choose L).
Notice the L=n term is always zero.
Some examples:
n=1 (the line segment whose vertices are 0 and 1 on the number line)
(1-0)*(1 choose 0) + (1-1)*(1 choose 1) = 1 edge.
n=2 (the square with vertices 00 01 10 11)
(2-0)*(2 choose 0) + (2-1)*(2 choose 1) + (2-2)*(2 choose 2) = 2*1 +
1*2 + 0 * 1 = 4 edges.
n=3 (the cube)
(3-0)*(3 choose 0) + (3-1)*(3 choose 1) + (3-2)*(3 choose 2) +
(3-3)*(3 choose 3) = 3*1+2*3+1*3+0*1 = 12 edges.
n=4
4*1+3*4+2*6+1*4+0*1=32 edges.
Exercise:
The finite sum
(sum from L=0 to L=n) (n-L)*(n choose L)
is equal to n*2^(n-1).
Hint:
use calculus.
or, find another way to count the edges so that n*2^(n-1) is more
obvious.
Adam C.
Post a reply to this message
|
|
