The Inversion Sequence of a Permutation
| Definition: If $A = \{1, 2, ..., n \}$ is a finite $n$-element set of positive integers and $(x_1, x_2, ..., x_n)$ is an $n$-permutation of the elements in $A$ then the Inversion Sequence of this permutation is a finite sequence $(a_i)_{i=1}^{n} = (a_1, a_2, ..., a_n)$ where for each $j \in \{1, 2, ..., n \}$ we have that $a_j$ is defined to be the number of integers to the left of $j$ in the $n$-permutation $(x_1, x_2, ..., x_n)$ that are larger than $j$. |
Be careful! In the definition above, we use the round bracket notation to represent both a permutation AND a finite sequence.
For example, consider the set $A = \{1, 2, 3, 4, 5, 6 \}$ of positive integers and the $6$-permutation $(4, 2, 5, 1, 6,3)$.
Now $a_1$ of our inversion sequence will be the number of integers to the left of $1$ in our $6$-permutation that are larger than $1$. We see that the numbers $4$, $2$, and $5$ are all to the left of $1$ in our permutation and each is greater than $1$ so $a_1 = 3$.
$a_2$ of our inversion sequence will be the number of integers to the left of $2$ in our $6$-permutation that are larger than $2$. We see the number $4$ is the only integer to the left of $2$ and $4$ is larger than $2$ so $a_2 = 1$.
In we carry this process up to $a_6$ we see that our inversion sequence for this particular permutation is:
(1)There are a few important properties to note about inversion sequences. Consider a general $n$-permutation $(x_1, x_2, ..., x_n)$. The term $a_n$ of the inversion sequence will always equal $0$. Similarly, if $j = x_1$ then $a_j = 0$. This is because there are no terms to the left of $x_1$, and so the number of terms to the left of $j$ in the $n$-permutation is $0$, i.e., $a_j = 0$.
Another important property is that $0 \leq a_1 \leq n-1$, $0 \leq a_2 \leq n-2$, …, $0 \leq a_{n-1} \leq 1$ since for each $j \in \{1, 2, ..., n \}$ we have that there can be at most $n - j$ integers to the left of $j$ in the $n$-permutation and larger than $j$.
Thus, $a_1 \in \{0, 1, 2, ..., n-1 \}$, $a_2 \in \{0, 1, 2, ..., n-2 \}$, …, $a_{n-1} \in \{0, 1 \}$ and $a_n \in \{ 0 \}$. Thus $a_1$ can be one of $n$ numbers, $a_2$ can be one of $n - 1$ numbers, …, $a_{n-1}$ can be one of $2$ numbers and $a_n$ can be one of $1$ numbers. Therefore the number of inversion sequences for an $n$-permutation is $n \cdot (n - 1) \cdot ... \cdot 2 \cdot 1 = n!$, i.e., the number of inversion sequences equals the number of $n$-permutations of a finite $n$-element set $A$ of positive integers.