Labeling an n-cube

[e(ho0n3]

I need some closure on this one:

 

In how many ways can the vertices of an n-cube be labeled 0, … ,2ⁿ - 1 so that there is an edge between two vertices if and only if the binary representation of their labels differs in exactly one bit?

 

Let G be an appropriately labeled n-cube. Pick an arbitrary vertex v in G. How many ways can one change labels of the vertices appart from v in G and still mantain the properties of the n-cube? Because of the nature of G, there are n incident edges on v with n adjacent vertices. The labels of these vertices differ from the label of v by one bit. If one swaps the labels of two of these vertices and makes the appropriate swaps elsewhere so as to maintain the n-cube (which can be done due to the symmetry of G), one obtains a new labeling. The number of combination of adjacent vertices that can be swapped is n(n - 1)/2, so the number of different labelings of the vertices in G without changing the label of v is n(n - 1)/2.

 

The label of vertex v is arbitrary. Therefore, for every possible label of v there are n(n - 1)/2 labelings of the vertices in G. Because there are 2ⁿ - 1 possible labels for v, the number of possible labelings for the vertices in G is (2ⁿ - 1)(n - 1)n/2.

[e(ho0n3]

Seems this question isn't getting much attention. Perhaps it's too 'over-the-top'.

 

Please forgive my shameless bumping.

[bloodhound]

I done this sort of question before, but not this complex. mainly stuff like how many ways you can colour a blah blah blah with three colours so that the adjacent sides arent the same etc. etc.

[Dave]

Yeah, I just don't seem to have the patience/vision for this sort of problem. Sorry

[e(ho0n3]

It's been a long time but I think I've figured it out. Let s(n) denote the number of different vertex-labelings of an n-cube. To construct and (n+1)-cube, one combines two n-cubes G and G' by drawing an appropriate edge from a vertex in G to a vertex in G'. In how many ways can this be done? Let v be a vertex in G and v' a vertex in G' with the same label A = a[1] a[2] ... a[n]. Draw and edge from v to v'. Since the labels of v and v' must differ by one bit, one must append an extra bit x to the label of v and ~x to the label of v' in the same relative position. This can be done in n + 1 ways (in front of a[1], in front of a[2], ..., in front of a[n] or behind a[n]). Since x can have on of two values, the answer is 2(n + 1) ways. Do this for every vertex in G and G' with the same label to contruct the (n+1)-cube.

 

Because G can have on of s(n) different vertex-labelings, then the number of different vertex-labelings in the (n+1)-cube is s(n + 1) = 2(n + 1)s(n). Solving this recurrence relations gives [math]\textstyle s(n+1) = 2^{n+1}(n+1)![/math]. Hence, the number of different vertex-labelings for an n-cube is [math]\textstyle 2^{n}(n)![/math].