TAOCP 5.1.2 Exercise 1

Section 5.1.2: Permutations of a Multiset

Exercise 1. [**] [M05] True or false: Let $M_1$ and $M_2$ be multisets. If $\alpha$ is a permutation of $M_1$ and $\beta$ is a permutation of $M_2$, then $\alpha \mathbin{\text{?}} \beta$ is a permutation of $M_1 \cup M_2$.

Verified: yes
Solve time: 30m29s

False.

A permutation of a multiset must be a bijection from the multiset onto itself. If $\alpha$ is a permutation of $M_1$ and $\beta$ is a permutation of $M_2$, there is no reason why the product $\alpha\beta$ (or any analogous composition) should be a permutation of $M_1\cup M_2$, because $\alpha$ and $\beta$ need not act on the same underlying multiset. In general, the operation is not even defined unless the domains and codomains are suitably identified.

For example, let $M_1={a}$ and $M_2={b}$. The only permutations are the identity permutations on these multisets. Their composition is not defined, since the image of $a$ under the first permutation lies in $M_1$, not in $M_2$. Therefore the stated assertion fails in general.

$$ \boxed{\text{False}} $$