inversion

combinatorics

What

A pair of positions $(i,j)$ of a permutation $a$ such that $i<j$ and $a(i)>a(j)$.

Distribution

The number of permutations of length $n$ with $k$ inversions is the same as the number of permutations of length $n$ with major index equal to $k$.

Calculation

Can be calculated using dynamic programming. See: LeetCode 629