16.2.1 Inversion of a pair (i, j) with respect to pi

Types: N/A
Examples: N/A
Constructions: N/A
Generalizations: 16.2 Symmetric Groups

Properties: N/A
Sufficiencies: N/A
Questions: N/A

Inversion of a pair

(i, j)

with respect to

π

Let $π \in S_{n}$ . Suppose $i, j \in [n]$ are chosen such that

1 \leq i < j \leq n

We call the pair $(i, j)$ an inversion with respect to $π$ iff

π (i) > π (j)

Remark. In other words, the pair $(i, j)$ is an inversion with respect to a given permutation $π$ if the outputs of $π (i)$ and $π (j)$ are in opposite orders of the inputs $i$ and $j$ . A quick way to check if $(i, j)$ is an inversion with respect to $π$ is to calculate the ratio

\frac{π (i) - π (j)}{i - j}

If the ratio $< 0$ , then $(i, j)$ is an inversion with respect to $π$ .
If the ratio $> 0$ , then $(i, j)$ is not an inversion with respect to $π$ .
$⧫$