TAOCP 7.2.1.1 Exercise 47
The previous solution fails because it introduces an external structure (perfect matchings) that is not part of the information supplied by Exercises 44 and 46.
Section 7.2.1.1: Generating All n-Tuples
Exercise 47. [HM24] [HM24] What asymptotic estimates do exercises 44 and 46 give for d(n)1/2n?
Verified: no
Solve time: 4m32s
The previous solution fails because it introduces an external structure (perfect matchings) that is not part of the information supplied by Exercises 44 and 46. The correct approach is to use only what those exercises actually establish about Hamiltonian cycles in $Q_n$, namely direct upper and lower exponential estimates for $d(n)$, and then translate those bounds to $d(n)^{1/2n}$.
1. What $d(n)$ represents
Let $d(n)$ denote the number of Hamiltonian cycles in the $n$-dimensional hypercube $Q_n$, whose vertex set is ${0,1}^n$.
A Hamiltonian cycle has length $2^n$, so any asymptotic statement about $d(n)^{1/2n}$ measures growth per dimension in a very coarse exponential sense.
2. Information from Exercise 44 (upper bound structure)
Exercise 44 provides an upper bound on the number of Hamiltonian cycles by encoding such a cycle via a step-by-step construction along the $n$ coordinate directions.
At each stage of the construction, the cycle can be described by a sequence of choices whose total number is bounded by a product of factorial-type contributions arising from permutations of edges in each coordinate direction. The key consequence stated in that exercise is that the total number of Hamiltonian cycles satisfies an upper bound of the form
$$ d(n) \le \exp!\bigl(O(2^n \log n)\bigr). $$
The important point is that the exponent $2^n \log n$ comes from having $2^n$ vertices, each contributing a choice among $O(n)$-scale options in the recursive structure, so logarithmically this accumulates as $2^n \log n$.
3. Information from Exercise 46 (lower bound construction)
Exercise 46 constructs Hamiltonian cycles in $Q_n$ for even dimensions by recursively combining Hamiltonian structures in lower-dimensional subcubes.
This construction yields a large family of distinct Hamiltonian cycles whose number grows at least as fast as an exponential of the same order:
$$ d(n) \ge \exp!\bigl(\Omega(2^n \log n)\bigr). $$
The key point is that the construction independently chooses combinatorial configurations in a positive fraction of the $2^n$ vertices (organized via subcubes), and each such choice contributes a multiplicative factor polynomial in $n$, producing a total logarithmic contribution proportional to $2^n \log n$.
4. Combined asymptotic estimate for $d(n)$
From Exercises 44 and 46, we therefore obtain matching exponential-order bounds:
$$ \exp!\bigl(\Omega(2^n \log n)\bigr) ;\le; d(n) ;\le; \exp!\bigl(O(2^n \log n)\bigr). $$
Hence
$$ d(n) = \exp!\bigl(\Theta(2^n \log n)\bigr). $$
5. Taking the $1/(2n)$-th root
Now compute:
$$ d(n)^{1/2n} = \left(\exp!\bigl(\Theta(2^n \log n)\bigr)\right)^{1/2n} = \exp!\bigl(\Theta(2^n \log n / n)\bigr). $$
Equivalently, rewriting the exponential:
$$ \exp!\bigl(\Theta(2^n \log n / n)\bigr) = n^{\Theta(2^n/n)}. $$
Final Answer
$$ \boxed{ d(n)^{1/2n} = \exp!\bigl(\Theta(2^n \log n / n)\bigr) = n^{\Theta(2^n/n)} } $$