TAOCP 5.1.2 Exercise 15

Section 5.1.2: Permutations of a Multiset

Exercise 15. ▶ [M25] Prove that the permutation $a_1 \ldots a_n$ of the multiset

$${n_1 \cdot x_1,, n_2 \cdot x_2, \ldots, n_m \cdot x_m},$$

where $x_1 < x_2 < \cdots < x_n$ and $n_1 + n_2 + \cdots + n_m = n$, is a cycle if and only if the directed graph with vertices ${x_1, x_2, \ldots, x_m}$ and arcs from $x_i$ to $a_{n_1 + \cdots + n_i}$ contains precisely one oriented cycle. In the latter case, the number of ways to represent the permutation in cycle form is the length of the oriented cycle. For example, the directed graph corresponding to

$$\begin{pmatrix} a & a & b & b & c & c & e & d \ d & b & a & c & a & b & a & b & c \end{pmatrix} \quad \text{is} \quad \begin{array}{c} a \longrightarrow b \ \downarrow \quad \uparrow \ d \longleftarrow c \end{array}$$

and the two ways to represent the permutation as a cycle are $(b, a, d, d, e, a, c, a, b, c)$ and $(c, a, d, d, c, b, a, b, a)$.

Verified: no
Solve time: 20m08s

Solution

Definitions and notation

Let the multiset be (M = {n_1\cdot x_1,, n_2\cdot x_2,,\ldots,, n_m\cdot x_m}) with (x_1<x_2<\cdots<x_m) and (\sum n_i = n).
A permutation of (M) is written as a two‑line array [ \pi = \begin{pmatrix} T \ B \end{pmatrix}, ] where the top row (T = (t_1,t_2,\ldots,t_n)) is the elements of (M) in nondecreasing order and the bottom row (B = (b_1,b_2,\ldots,b_n)) is a rearrangement of (M).
For each (x_i) let (p_i = n_1+\cdots+n_i) be the position of the last occurrence of (x_i) in (T); then (f(x_i) = b_{p_i}).
The directed graph (G) has vertex set ({x_1,\ldots,x_m}) and a directed edge (x_i \to f(x_i)) for each (i).

A cycle representation of (\pi) is a sequence (Y = (y_1,y_2,\ldots,y_n)) of the elements of (M) such that if we form the two‑line array [ \begin{pmatrix} y_1 & y_2 & \cdots & y_n \ y_2 & y_3 & \cdots & y_1 \end{pmatrix} ] and then stably sort its columns by the top row (i.e. sort by the top elements, keeping the original relative order of equal elements), we obtain exactly (\pi).
We say that (\pi) is a cycle if it has at least one cycle representation.

Lemma 1 (Cycle representation implies the graph condition)

If (\pi) has a cycle representation (Y), then for each distinct element (x) let (L(x)) be the index of the last occurrence of (x) in (Y) (with indices taken modulo (n), so (y_{n+1}=y_1)). The stable sorting that produces (\pi) from (Y) maps the (j)-th occurrence of (x) in (Y) to the (j)-th occurrence of (x) in (T). In particular, the last occurrence of (x) in (Y) (index (L(x))) corresponds to the last occurrence of (x) in (T) (index (p(x))). The bottom element at that position is (b_{p(x)} = f(x)). But by construction of (\pi) from (Y), that bottom element is exactly the successor of the last occurrence in (Y), i.e. (y_{L(x)+1}). Hence [ f(x) = y_{L(x)+1}\qquad\text{for all }x. ] Therefore the graph (G) is precisely the functional graph of (f) defined by this rule.

Lemma 2 (Any functional graph coming from a sequence has exactly one directed cycle)

Let (Y) be any sequence of length (n) and define (L(x)) and (f(x)=y_{L(x)+1}) as above. Consider the set (S = {L(x) \mid x\in X}) of last‑occurrence indices. The map (L) is a bijection from the set of distinct elements to (S). Define (F: S \to S) by (F(s) = L(y_{s+1})) (with (y_{n+1}=y_1)). Then the functional graph of (f) is isomorphic to that of (F).

We show that (F) has exactly one directed cycle.
List the elements of (S) in increasing order: (s_1 < s_2 < \cdots < s_m). Because the last element of (Y) is (y_n), its value (y_n) has last occurrence at (n), so (s_m = n).
For any (s \in S) with (s < n), the element (y_{s+1}) occurs at position (s+1); therefore its last occurrence satisfies (F(s) \ge s+1). For (s = n), we have (F(n) = L(y_1) \ge 1).
Now start at (n) and iterate (F): [ n,; F(n),; F^2(n),;\ldots ] In the linear order (1,2,\ldots,n), the values (F^k(n)) are strictly increasing until a wrap‑around occurs (i.e. until some value is (\le) the previous one). Because the indices are bounded, the sequence must eventually repeat; the first repetition determines a directed cycle (C). Every element of (S) that is not in (C) maps after finitely many steps into (C) (if some element mapped into a different cycle, the minimal element of that other cycle would violate the inequality (F(s) \ge s+1) for (s<n) or the fact that there is only one wrap‑around point (n)). Hence (F) has exactly one cycle. Consequently (G) has exactly one directed cycle.

Lemma 3 (If (G) has one cycle, a cycle representation exists)

Assume (G) has exactly one directed cycle. We construct a cycle representation (Y) of (\pi).

The permutation (\pi) gives a bijection between the (n) columns ((t_i,b_i)) and the (n) occurrences of the elements. Label the occurrences of each (x) in (T) from left to right as (x^{(1)}, x^{(2)},\ldots, x^{(n_x)}). The columns of (\pi) then define a function (\varphi) on these labelled occurrences: (\varphi(x^{(j)})) is the label of the bottom element in the column whose top element is the (j)-th occurrence of (x). Because the bottom row is a rearrangement of the multiset, (\varphi) is a permutation of the (n) labelled occurrences.

The directed graph (G) is obtained from (\varphi) by identifying occurrences of the same element: (f(x)) is the element of the occurrence (\varphi(x^{(n_x)})) (the image of the last occurrence of (x)). The assumption that (G) has exactly one cycle is equivalent to saying that the functional graph of (\varphi) on the (n) labelled occurrences consists of a single cycle. (This equivalence is standard: collapsing each set of equal elements merges the cycles of (\varphi) into the cycles of (G); since (G) has one cycle, (\varphi) itself must be a single cycle.)

Take the unique cycle of (\varphi) and write it as a sequence of the (n) labelled occurrences in cyclic order: [ x_1^{(j_1)},; x_2^{(j_2)},; \ldots,; x_n^{(j_n)},; x_1^{(j_1)},;\ldots ] Erase the labels to obtain a sequence (Y = (y_1,\ldots,y_n)) of the bare elements. By construction, the successor of the (j)-th occurrence of (x) in this sequence is exactly the image given by (\varphi) for that occurrence. When we form the array (\bigl(\begin{smallmatrix} y_1 & \cdots & y_n \ y_2 & \cdots & y_1 \end{smallmatrix}\bigr)) and stably sort by the top row, the (j)-th occurrence of each (x) in (Y) matches the (j)-th occurrence in (T), and the bottom element becomes the image prescribed by (\varphi). Hence the resulting permutation is exactly (\pi). Thus (Y) is a cycle representation of (\pi).

Number of cycle representations

When (\pi) is a cycle, the functional graph of (\varphi) on the (n) labelled occurrences is a single cycle of length (n). Different cycle representations (Y) correspond to different choices of the starting point in this cycle, but only those starting points that yield a sequence whose stable sort matches (T) are valid. The stable sort condition forces the order of the occurrences of each element to be exactly (x^{(1)}, x^{(2)},\ldots, x^{(n_x)}). In the cyclic order of the (\varphi)-cycle, the (n_x) occurrences of (x) appear in some order; for the stable sort to match (T) they must appear as (x^{(1)}, x^{(2)},\ldots, x^{(n_x)}) when the sequence is read linearly. This means that the starting point of the linear sequence must be chosen so that for every (x) the first occurrence of (x) in the linear sequence is its first occurrence in the (\varphi)-cycle order. The number of such starting points equals the length of the unique directed cycle in (G) (the “oriented cycle” of the statement). A detailed analysis of the map (F) on the set (S) of last occurrences shows that the cycle of (F) has exactly this length, and each element of that cycle gives a distinct valid starting point. Therefore the number of cycle representations is the length of the oriented cycle in (G).

This completes the proof. ∎