How many different $n$-bit Gray-code-like cycles are there?

615 Views Asked by At

The Question: How many different $n$-bit Gray-code-like cycles are there?

It just needs some clarification:

$i)$ The original $n$-bit Gray code is now considered as a cycle of all $n$-bit binary numbers, which satisfies the Gray property. So are $n$-bit Gray-code-like cycles.

$ii)$ For convenience, let $n > 1$.

$iii)$ By different cycles, I exclude the difference made from rotation and reflection.

This problem is posed by myself out of curiosity. By permuting the bits, it is proved that there are at least $\dfrac{n!}{2}$ different cycles. Is that the answer?

Thanks in advance!!!

1

There are 1 best solutions below

1
On

Here is what Wikipedia has to say about the matter:

Hamiltonicity of the hypercube is tightly related to the theory of Gray codes. More precisely there is a bijective correspondence between the set of $n$-bit cyclic Gray codes and the set of Hamiltonian cycles in the hypercube $Q_n$.

There is a reference to a 1963 paper by W. H. Mills in Proc. AMS.