Hamiltonian Path through $n$-bit strings with maximum number of $0\mapsto 1$ transitions

Question

Let $G_n$ be the complete graph whose vertices are the $2^n$ $n$-bit strings. Let $H_n$ denote the Hamiltonian path through $G_n$ that uses the maximum number of edges that correspond to a single bit transition $0\mapsto 1$. What is this maximum number? And is there an algorithm that generates this Hamiltonian path?

The classical Gray code is a Hamiltonian path that uses only edges with $0\mapsto 1$ or $1 \mapsto 0$ transitions (single bit flips in both directions). I want to use as many single bit flips as possible in one direction ($0\to 1$) and have no restrictions on other transitions.

Here is an example for $n=4$ that uses 10 $(0\mapsto 1)$ transitions $(\rightarrow)$ and 6 others $(\Rightarrow)$:

$0000\rightarrow 0001 \rightarrow 0011 \rightarrow 0111 \rightarrow 1111 \Rightarrow 0010\rightarrow 0110 \rightarrow 1110 \Rightarrow 0100 \rightarrow 0101 \rightarrow 1101 \Rightarrow 1000 \rightarrow 1001 \rightarrow 1011 \Rightarrow 1010 \Rightarrow 1100 \Rightarrow 0000$

Answer 1

Then best you can do is $2^n-\binom n {\lfloor n/2 \rfloor}$. The binary strings of length $n$ can be decomposed into $\binom n {\lfloor n/2 \rfloor}$ chains, sets that can be ordered so that all transitions are of the form you are interested in. Joining these chains up produces a Hamiltonian path in $G_n$ achieving the above bound.

In the other direction, any Hamiltonian path gives rise to a set of chains by deleting the edges that are not of the preferred type. But Sperner's theorem says that we need at least $\binom n {\lfloor n/2 \rfloor}$ chains to cover all binary words of length $n$.

I believe that it is possible but non-trivial to describe an optimal chain decomposition explicitly (it was a starred question on an exercise sheet in a course I have taken).