Inversions

The number of inversions of a permutation $p$: pairs $i < j$ with $p_i > p_j$ (its Kendall-tau distance from the identity).

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaInversion (discrete mathematics)↗MathWorldPermutationInversion↗WikidataQ1368009↗FindStatSt000293via BinaryWord✓↗St000766via IntegerComposition✓↗St000018via Permutation✓↗

Inversions(p)the inversion count of a one-line permutation $p$

CombinatoricaInversions[p]SageMathenumeratio_stat("Permutation", p, "Inversions")

Typed signatures

Type	Package	Applies
(binary_word | composition | list | permutation) -> integer | number	combinatorics	always

Domain: Permutation statistics

Details

• Ranges from $0$ (the identity) to $\binom{n}{2}$ (the reversal $n, n-1, \dots, 1$)
• Generating function over $S_n$ is the q-factorial $[n]_q! = \prod_{i=1}^{n} \frac{1 - q^i}{1 - q}$
• Equidistributed with MajorIndex on $S_n$ (MacMahon), so both are Mahonian statistics
• Aggregates over a whole collection compose from built-ins: $\mathrm{Sum}(\mathrm{Map}(\mathrm{Inversions}, \mathrm{SymmetricGroup}(n)))$ folds the stat over the lazy family
• Defined over Permutation as an expression in _x, evaluated by compute-engine — the definition IS the implementation.
• Takes a Permutation, and also a bare list of integers: this reading compares entries with each other rather than with their positions, so it stands on any sequence.

Definition

Epsil, as the implementation runs it.

on Permutation, over _x

0 if Length(_x) < 2 else Sum(Map(
                                  Function(
                                            Count(Filter(
                                                          Range(
                                                                 i + 1,
                                                                 Length(_x),
                                                               ),
                                                          Function(
                                                                    _x[i] >
                                                                    _x[j],
                                                                    j,
                                                                  ),
                                                        )),
                                            i,
                                          ),
                                  Range(1, Length(_x)),
                                ))

on IntegerComposition, over _x

0 if Length(_x) < 2 else Sum(Map(Function(
                                           Count(Filter(Range(
                                                               i + 1,
                                                               Length(_x),
                                                               1,
                                                             ), Function(_x[i] >
                                                                        _x[j], j))),
                                           i,
                                         ), Range(1, Length(_x) - 1)))

on BinaryWord, over _x

0 if Length(_x) < 2 else Sum(Map(Function(
                                           Count(Filter(Range(
                                                               i + 1,
                                                               Length(_x),
                                                               1,
                                                             ), Function(_x[i] >
                                                                        _x[j], j))),
                                           i,
                                         ), Range(1, Length(_x) - 1)))

Examples

Basic #

$(3,1)$ and $(3,2)$

live ↗

In$\mathrm{Inversions}(\bigl\lbrack3, 1, 2\bigr\rbrack)$Out$2$

the identity has none

live ↗

In$\mathrm{Inversions}(\bigl\lbrack1, 2, 3\bigr\rbrack)$Out$0$

the one-line word $312$

live ↗

In$\mathrm{Inversions}({\operatorname{Permutation}}([3, 1, 2]))$Out$2$

the one-line word $312$, as a plain list

live ↗

In$\mathrm{Inversions}(\bigl\lbrack3, 1, 2\bigr\rbrack)$Out$2$

the one-line word $2413$

live ↗

In$\mathrm{Inversions}({\operatorname{Permutation}}([2, 4, 1, 3]))$Out$3$

the arrangement $314$

live ↗

In$\mathrm{CombinatorialStat}({\operatorname{Arrangement}}([3, 1, 4]), \text{Inversions})$Out$1$

Applications #

the inversion distribution over $S_3$, mapped across the lazy SymmetricGroup

live ↗

In$\mathrm{ListFrom}(\mathrm{Map}(p↦\mathrm{Inversions}(p), \mathrm{SymmetricGroup}(3)))$Out$\bigl\lbrack0, 1, 1, 2, 2, 3\bigr\rbrack$

total inversions over all of $S_4$, folded with $\mathrm{Sum}$: $\frac{n!}{2}\binom{n}{2} = 72$

live ↗

In$\sum\mathrm{Map}(p↦\mathrm{Inversions}(p), \mathrm{SymmetricGroup}(4))$Out$72$

Properties #

the reversal attains the maximum $\binom{4}{2}$

live ↗

In$\mathrm{Inversions}(\bigl\lbrack4, 3, 2, 1\bigr\rbrack)$Out$6$

FindStat's value for [1]

live ↗

In$\mathrm{CombinatorialStat}({\operatorname{Permutation}}([1]), \text{Inversions})$Out$0$

Known value · FindStat St000018

FindStat's value for [1,2]

live ↗

In$\mathrm{CombinatorialStat}({\operatorname{Permutation}}([1, 2]), \text{Inversions})$Out$0$

Known value · FindStat St000018

FindStat's value for [2,1]

live ↗

In$\mathrm{CombinatorialStat}({\operatorname{Permutation}}([2, 1]), \text{Inversions})$Out$1$

Known value · FindStat St000018

About

Examples	12
Checked against	Combinatorica 7 agreeSageMath 9 agreemathlib4 6 agree
Crosswalk	WikipediaMathWorldWikidataFindStat ×3CombinatoricaSageMath

Implementation

mappedcombinatoricapackages/oracle/src/mappings.ts

mappedsagepackages/oracle/src/mappings.ts

mappedmathlib4packages/oracle/src/mappings.ts

Pairs i < j with l[i] > l[j], counted over Fin pairs of the list; a permutation word and a plain list agree, a composition (which has its own inversions) does not

See also: MajorIndex, Descents, SymmetricGroup