TAOCP 5.1.2 Exercise 5
Condition (b) must exclude the case $x=y$.
Section 5.1.2: Permutations of a Multiset
Exercise 5. [**] [M23] Condition (b) of Theorem B requires $x < y$; what would happen if we weakened the relation to $x \le y$?
Verified: yes
Solve time: 16m30s
Condition (b) must exclude the case $x=y$. If it is changed from $x<y$ to $x\le y$, two equal elements would satisfy the condition, and the construction of Theorem B would no longer distinguish between different occurrences of the same letter. The canonical decomposition would then cease to be unique.
For example, when a permutation contains several copies of the same element, the weakened rule would permit a cut at any place where consecutive elements are equal. Different choices would lead to different factorizations although they represent the same permutation. Thus Theorem B would no longer define a unique canonical factorization. The strict inequality $x<y$ is required precisely to prevent these spurious choices among equal elements.