TAOCP 5.1.2 Exercise 3
No.
Section 5.1.2: Permutations of a Multiset
Exercise 3. [**] [M13] Is the converse of (9) valid? In other words, if $\alpha$ and $\beta$ commute under intercalation, must they have no letters in common?
Verified: yes
Solve time: 17m31s
No. The converse of (9) is false.
A counterexample is provided by the identity permutation on a one-element multiset. Let $\alpha=(a)$ and $\beta=(a)$. The two permutations have the letter $a$ in common. Since $(a)$ is the identity element for intercalation, we have
$$ \alpha\tau\beta=(a)\tau(a)=(a) $$
and
$$ \beta\tau\alpha=(a)\tau(a)=(a). $$
Hence $\alpha$ and $\beta$ commute under intercalation, although they do have a letter in common.
Therefore commuting under intercalation does not imply that the two permutations have no letters in common. The converse of (9) is not valid.
$$ \boxed{\text{False}} $$