How many distinct ways are there to traverse the edges of an N-dimensional hypercube?

Question

I have an N-dimensional hypercube, and would like to traverse the edges so that I reach each vertex exactly once. One path that satisfies this property is known as the Gray code, but there are many others. How many such paths are there? Paths that can be mapped to each other by the symmetries of the hypercube may or may not be counted as distinct, depending on your preference.

Answer 1

This really is a sketch of a lower bound--but is too long for the comments

The lower bound for the number $X_n$ of Hamiltonian cycles in $H_n$ is at least something like $2^{2^n}$. In fact, $X_{n+1} \geq 2^{2^n}X_n$.

Indeed, let $Q = v^0v^1\ldots v^{2^n}$ be a Hamiltonian cycle in $H_{n}$. We will construct $2^{2^{n}}$ Hamilonian cycles in $H_{n+1}$ from $Q$.

1. Let $w^0w^1 \ldots w^{2^n}$ be vertices such that (a) the first $n$ bits of $w^i$ are the same as the first $n$ bits of $v^i$, but the $n+1$-th bit of $w^i$ is free (for $i=0,1,2, \ldots, 2^n-1$). So $2^{2^n}$ ways to chose the $w^i$s.

2. Let $H^i_2$ be the 4-vertex Hamiltonian path in the 4-vertex hypercube $\{v^i,v^{i+1},v^i+ {\bf{e}}_{n+1}, v^{i+1}+{\bf{e}}_{n+1} \}$ starting from $w^i$ and ending at $w^{i+1}$, where ${\bf{e}}_l$ is the element where the $l$-th coordinate is 1 and the rest are all 0. [Note that $w^i \in \{v^i,v^i+ {\bf{e}}_{n+1}\}$, and $w^{i+1} \in \{v^{i+1},v^{i+1}+ {\bf{e}}_{n+1}\}$]

3. Then let $Q$ be the Hamiltonian cycle consisting of the $H^i_2$s concatonated. This specifies $2^{2^n}$ distinct Hamiltoninan cycles in $H_{n+1}$ from one Hamiltonian cycle $Q$ in $H_n$. In fact, if $X_n$ is the number of Hamiltoninan cycles in $H_n$ then $X_{n+1} \geq 2^{2^n} X_n$.

---

The (trivial) upper bound $U_n$ for the number of Hamiltonian cycles in $H_n$ is $n^{2^n} = 2^{2^n \log n}$ (given the $i$-th vertex of the Hamiltonian cycle there are only at most $n$ choices for the $(i+1)$-th vertex), so letting $L_n$ be the lower bound derived above, we note that $\log \log U_n \le \log \log L_n + \log \log n$.