Section 5.1.2: Permutations of a Multiset

Exercise 2. [**] [10] The intercalation of cadab and bddad is computed in (5); find the intercalation bddadcadab that is obtained when the factors are interchanged.

Verified: no
Solve time: 15m46s

Using the definition of intercalation, we write

$$ \beta=\text{bddad} \qquad\Longrightarrow\qquad \begin{pmatrix} a&b&d&d&d\ b&d&d&a&d \end{pmatrix}, $$

and

$$ \alpha=\text{cadab} \qquad\Longrightarrow\qquad \begin{pmatrix} a&a&b&c&d\ c&a&d&a&b \end{pmatrix}. $$

After juxtaposing the two-line representations in the order $\beta,\alpha$ and then stably sorting the columns by the top row, the columns with top entries $a,a,a,b,b,c,d,d,d,d$ have bottom entries

$$ b,\ c,\ a,\ d,\ d,\ a,\ d,\ a,\ d,\ b. $$

Hence

$$ \text{bddad} ,\tau, \text{cadab}

\text{bcaddadadb}. $$

Therefore the intercalation obtained when the factors are interchanged is

$$ \boxed{\text{bcaddadadb}}. $$

This differs from $\text{cabddabdad}$, illustrating that the intercalation product is not commutative in general.