**3.1) Permutations**

Every ordering of the first **n** natural numbers $1,2,\dots,n$ is called a permutation.

There are $n!$ permutations of the first **n** natural numbers.

**3.2) Inversions**

If we have the permutation $i_1, i_2, \dots i_n$ (of the first **n** natural numbers) then the numbers $i_k$ and $i_s$ are said to form an **inversion** if $k \lt s$ but $i_k > i_s$

In other words, an **inversion** in a permutation is a pair of numbers such that the larger number appears to the left of the smaller one in the permutation. The **inversion number** of a permutation is the total number of inversions. The inversion number of the permutation $i_1, i_2, \dots i_n$ is denoted by $[i_1, i_2, \dots ,i_n]$.

**3.3) Parity of a permutation**

Odd permutations - the inversion number is odd

Even permutations - the inversion number is even

**3.4) Sign of a permutation**

The sign of a permutation $i_1, i_2, \dots i_n$ is defined as $(-1)^{[i_1, i_2, \dots ,i_n]}$, where $[i_1, i_2, \dots ,i_n]$ is the **inversion number** of the permutation. It is obvious that the sign is $+1$ for even permutations and $-1$ for odd permutations.

**3.5) Transposition**

We say that we have applied a **transposition** if in a permutation **P** we swap the order of any two elements and the other elements we leave in place. When we do this, we get (from **P**) a new permutation **R**.

__Lemma 1__: The permutations **P** and **R** are of different parity.

__Lemma 2__: When $n \ge 2$, the number of the even permutations is equal to the number of the odd permutations.

**3.6) Determinant**

The concepts introduced here are important building blocks for introducing the concept of determinant (of a square matrix). The concept of determinant is usually defined using the Leibniz formula for determinants

## No comments:

## Post a Comment