Inversions of a Random Permutation

Concept & Intuition

For a permutation π of the labels 1, 2, ..., n, an inversion is any ordered pair of indices (i, j) with 1 ≤ i < j ≤ n such that πi > πj. The minimum possible inversion count is 0 (the ascending permutation) and the maximum is n(n - 1)/2 (the strictly descending permutation).

By the inversion-table bijection, inserting the j-th element into a random permutation of the first j - 1 elements adds an independent discrete uniform number of new inversions on {0, 1, ..., j - 1}.

Mathematical Formulation

Because the total inversion count is the sum of independent discrete uniform variables Xj ~ Uniform({0, 1, ..., j - 1}) for j = 1, ..., n, its probability generating function is the Mahonian product:

Gn(q) = (1 / n!) ∏j=1n (1 + q + q2 + ... + qj-1)

By linearity of expectation and independence of the summands Xj, the mean and variance have closed forms:

E[In] = ∑j=1n (j - 1)/2 = n(n - 1) / 4, and Var(In) = ∑j=1n (j2 - 1)/12 = n(n - 1)(2n + 5) / 72.

Worked Example & Boundary Behavior

Let us calculate the exact distribution and moments for a random permutation of size n = 4.

1. The expected number of inversions (mean) is given by the formula: n(n - 1) / 4.
2. For n = 4, the mean is: 4 × (4 - 1) / 4 = 12 / 4 = 3.
3. The variance is given by: n(n - 1)(2n + 5) / 72.
4. For n = 4, the variance is: 4 × 3 × 13 / 72 = 156 / 72 = 13 / 6 ≈ 2.1667.
5. Expanding (1)(1 + q)(1 + q + q2)(1 + q + q2 + q3) yields coefficients 1, 3, 5, 6, 5, 3, 1 over 4! = 24 permutations, so probing k = 3 inversions gives exact mass 6/24 = 1/4 = 0.25.

Interactive Experiment

You can interact with the module to inspect the exact probability mass function for the number of inversions.

1. Open the Inversions of a Random Permutation module.
2. Set Permutation size to 4 and Inversions probe to 3.
3. Observe that the Mean is 3, Variance is 13/6, and Probe Probability is 1/4 = 0.25.
4. Check the boundary cases n = 0 and n = 1, where the only possible inversion count is 0 with probability 1.

Interpretation & Limitations

The interactive visualization limits the permutation size up to n = 7 (7! = 5040 permutations, up to 21 inversions) so every exact rational probability can be displayed without truncation. Although individual pair indicators I(i < j, πi > πj) are dependent, grouping inversions by their right endpoint restores independence across j = 1, ..., n.

References

The inversion distribution is a foundational topic in algebraic combinatorics and non-parametric statistics.

• Gessel and Stanley, Algebraic Enumeration — Derives the inversion-table bijection and the Mahonian product (1)(1 + q)...(1 + q + ... + qn-1).