TAOCP 7.2.1.6 Exercise 70
Let $\sigma = a_1 a_2 \cdots a_n$ be a bit string with $a_i \in {0,1}$ and let $\nu(\sigma)$ denote the number of 1s in $\sigma$, so $\nu(\sigma)=\sum_{i=1}^n a_i$.
Section 7.2.1.6: Generating All Trees
Exercise 70. ▶ [20] [20] Find a simple rule that defines, for every bit string $\sigma$, another bit string $\sigma'$ called its mate, with the following properties: (i) $\sigma'' = \sigma$; (ii) $|\sigma'| = |\sigma|$; (iii) either $\sigma \le \sigma'$ or $\sigma' \le \sigma$; (iv) $\nu(\sigma) + \nu(\sigma') = |\sigma|$.
Verified: yes
Solve time: 1m42s
Solution
Let $\sigma = a_1 a_2 \cdots a_n$ be a bit string with $a_i \in {0,1}$ and let $\nu(\sigma)$ denote the number of 1s in $\sigma$, so $\nu(\sigma)=\sum_{i=1}^n a_i$.
Define the mate $\sigma' = a'_1 a'_2 \cdots a'_n$ by
$a'_i = 1 - a_i \quad \text{for } 1 \le i \le n.$
This operation is well defined for every bit string and preserves length since exactly one bit is produced for each input bit.
Applying the transformation twice yields
$a''_i = 1 - a'_i = 1 - (1 - a_i) = a_i,$
hence $\sigma'' = \sigma$.
For the weight condition,
$\nu(\sigma') = \sum_{i=1}^n a'i = \sum{i=1}^n (1 - a_i) = n - \sum_{i=1}^n a_i = n - \nu(\sigma),$
so
$\nu(\sigma) + \nu(\sigma') = n = |\sigma|.$
To verify the lexicographic comparability condition, let $j$ be the first index such that $a_j \ne a'_j$. By construction, every index satisfies $a'_i = 1 - a_i$, so $a_j = 0$ implies $a'_j = 1$ and $a_j = 1$ implies $a'_j = 0$. Since all earlier positions agree only in the trivial sense that no disagreement occurs before $j$, the lexicographic order between $\sigma$ and $\sigma'$ is decided at position $j$, giving either $\sigma < \sigma'$ or $\sigma' < \sigma$.
Thus the mapping satisfies involution, preserves length, enforces $\nu(\sigma)+\nu(\sigma')=|\sigma|$, and guarantees comparability in lexicographic order.
This completes the proof. ∎
$$ \boxed{\sigma' = \text{bitwise complement of } \sigma} $$