TAOCP 5.1.2 Exercise 11

**Exercise 5.

taocpmathematicsalgorithmsvolume-3

Section 5.1.2: Permutations of a Multiset

Exercise 11. [**] [M26] Let $\sigma_1, \sigma_2, \ldots, \sigma_t$ be cycles without repeated elements. Define a partial ordering $\prec$ on the $t$ objects ${x_1, \ldots, x_t}$ by saying that $x_i \prec x_j$ if $i < j$ and $\sigma_i$ has at least one letter in common with $\sigma_j$. Prove the following connection between Theorem C and the notion of “topological sorting” (Section 2.2.3): The number of distinct prime factorizations of $\sigma_1 \tau \sigma_2 \tau \cdots \tau \sigma_t$ is the number of ways to sort the given partial ordering topologically. (For example, corresponding to (22) we find that there are five ways to sort the ordering $x_1 \prec x_2$, $x_3 \prec x_4$, $x_1 \prec x_4$ topologically.) Conversely, given any partial ordering on $t$ elements, there is a set of cycles ${\sigma_1, \sigma_2, \ldots, \sigma_t}$ that defines it in the stated way.

Verified: yes
Solve time: 52m40s

Exercise 5.1.2.11 [M26]

Let $\sigma_1, \sigma_2, \ldots, \sigma_t$ be cycles without repeated elements. Define a partial ordering $\prec$ on ${x_1, \ldots, x_t}$ by

$$ x_i \prec x_j \iff i < j \text{ and } \sigma_i \text{ and } \sigma_j \text{ share a letter}. $$

Prove that the number of distinct prime factorizations of

$$ \pi = \sigma_1 \tau \sigma_2 \tau \cdots \tau \sigma_t $$

equals the number of topological sorts of this partial order. Conversely, show that every partial order on $t$ elements can be realized in this way.

Part 1: Distinct prime factorizations correspond to topological sorts

By Theorem C (TAOCP, Vol. 3, Section 5.1.2), any prime factorization of a permutation is obtained from another by interchanging adjacent disjoint cycles.

Let $x_i \prec x_j$. Then $i < j$ and $\sigma_i$ and $\sigma_j$ share a letter. Since cycles that share a letter are not disjoint, $\sigma_i$ and $\sigma_j$ can never be interchanged in a factorization. Therefore, in any factorization, $\sigma_i$ appears before $\sigma_j$, enforcing the relation $x_i \prec x_j$.

If $x_i$ and $x_j$ are incomparable in $\prec$, then $\sigma_i$ and $\sigma_j$ share no letters. Cycles without repeated elements that share no letters are disjoint. Hence $\sigma_i$ and $\sigma_j$ can be interchanged if adjacent.

Thus:

  1. Every distinct prime factorization of $\pi$ corresponds to a linear extension of the poset $({x_1, \ldots, x_t}, \prec)$.
  2. Conversely, any linear extension of $\prec$ can be obtained from the factorization $\sigma_1 \tau \cdots \tau \sigma_t$ by successively interchanging adjacent incomparable cycles. This follows from the standard fact in poset theory that any linear extension can be reached from any other by a sequence of adjacent transpositions of incomparable elements.

Hence there is a bijection between distinct prime factorizations of $\pi$ and topological sorts of $\prec$. The number of distinct prime factorizations equals the number of topological sorts.

Part 2: Realizing an arbitrary partial order with cycles

Let $P$ be a partial order on ${x_1, \dots, x_t}$. Construct cycles $\sigma_1, \dots, \sigma_t$ such that

$$ x_i \prec x_j \text{ in } P \iff i < j \text{ and } \sigma_i, \sigma_j \text{ share a letter}. $$

Construction.

  1. Introduce a distinct letter $a_{ij}$ for each ordered pair $(x_i, x_j)$ with $x_i \prec x_j$ in $P$.
  2. Define

$$ \sigma_i = (a_{ij_1}, a_{ij_2}, \dots , a_{ij_k}), $$

where ${x_{j_1}, \dots, x_{j_k}}$ are exactly the elements $x_j$ such that $x_i \prec x_j$ in $P$. That is, $\sigma_i$ is a cycle whose letters correspond to all elements greater than $x_i$ in $P$.

Verification.

Let $i < j$. Then $\sigma_i$ and $\sigma_j$ share a letter if and only if $x_i \prec x_j$ in $P$, because $a_{ij}$ appears in exactly the cycles $\sigma_i$ and $\sigma_j$. Therefore, by construction, the induced relation

$$ x_i \prec x_j \iff i < j \text{ and } \sigma_i, \sigma_j \text{ share a letter} $$

coincides exactly with $P$.

Since each letter $a_{ij}$ appears in exactly two cycles, each $\sigma_i$ has distinct letters, and all cycles are without repeated elements.

This construction works for any partial order $P$ on $t$ elements.

Conclusion

  1. Distinct prime factorizations of $\pi = \sigma_1 \tau \cdots \tau \sigma_t$ correspond bijectively to topological sorts of the poset $({x_1, \dots, x_t}, \prec)$.
  2. Every partial order on $t$ elements can be realized as a relation induced by cycles $\sigma_1, \dots, \sigma_t$ constructed as above.

$\Box$