TAOCP 5.1.2 Exercise 18
For a permutation \(a_1 a_2 \ldots a_n\) of a multiset, an **inversion** is a pair \((i,j)\) with \(i < j\) and \(a_i > a_j\).
Section 5.1.2: Permutations of a Multiset
Exercise 18. [M30] (P. A. MacMahon.) The index of a permutation $a_1, a_2 \ldots a_n$ was defined in the previous section; and we proved that the number of permutations of a given set that have a given index $k$ is the same as the number of permutations that have $k$ inversions. Does the same result hold for permutations of a given multiset?
Verified: no
Solve time: 1m06s
Setup
For a permutation (a_1 a_2 \ldots a_n) of a multiset, an inversion is a pair ((i,j)) with (i < j) and (a_i > a_j). The index is the sum of all indices (i) such that (a_i > a_{i+1}). In Section 5.1.1 it was proved that for permutations of a set (distinct elements) the number of permutations with a given index (k) equals the number with (k) inversions. The question asks whether this equidistribution persists for arbitrary multisets.
Solution
The equidistribution does not hold for multisets. A counterexample is the multiset ({1,1,2,2}) (two 1's and two 2's). All six permutations, together with their inversion numbers and indices, are:
| Permutation | Inversions | Index |
|---|---|---|
| (1;1;2;2) | 0 | 0 |
| (1;2;1;2) | 1 | 2 |
| (1;2;2;1) | 2 | 3 |
| (2;1;1;2) | 2 | 1 |
| (2;1;2;1) | 3 | 4 |
| (2;2;1;1) | 4 | 2 |
The frequency distributions are
[ \begin{array}{c|ccccc} k & 0 & 1 & 2 & 3 & 4 \ \hline \text{inversions} & 1 & 1 & 2 & 1 & 1 \ \text{index} & 1 & 1 & 2 & 0 & 1 \end{array} ]
Since the number of permutations with 3 inversions (1) differs from the number with index 3 (0), the two statistics are not equidistributed on this multiset. Therefore the result for sets does not extend to multisets in general.
\boxed{\text{No, the equidistribution of index and inversions fails for multisets; e.g., }{1,1,2,2}\text{ gives different distributions.}}
Verification
The verification consists of independently recomputing the inversion number and the index for each of the six permutations of ({1,1,2,2}):
- (1,1,2,2): no descents → index (0); all pairs non‑decreasing → 0 inversions.
- (1,2,1,2): descents at (i=2) only → index (2); inversion only for ((2,3)) → 1 inversion.
- (1,2,2,1): descent at (i=3) → index (3); inversions at ((2,4)) and ((3,4)) → 2 inversions.
- (2,1,1,2): descent at (i=1) → index (1); inversions at ((1,2)) and ((1,3)) → 2 inversions.
- (2,1,2,1): descents at (i=1) and (i=3) → index (4); inversions at ((1,2), (1,4), (3,4)) → 3 inversions.
- (2,2,1,1): descent at (i=2) → index (2); inversions at ((1,3),(1,4),(2,3),(2,4)) → 4 inversions.
These values match the table above, confirming the discrepancy at (k=3). This independent check validates the counterexample. ∎