Рассмотрим множество первых 
натуральных чисел 
.
Определение.Перестановкой 
множества элементов из 
назовем любое расположение этих элементов в некотором порядке.
Пример. Рассмотрим 
. Перестановками для элементов из 
будут: 
и т.д.
Можно показать, что число различных перестановок для множества из элементов равно 
.
Определение. Числа 
и 
образуют инверсию в перестановке , если 
и расположено левее .
Определение. Число инверсий всех элементов перестановки 
назовем числом инверсийперестановки и обозначим 
.
Для подсчета числа инверсий в перестановке необходимо подсчитать для каждого элемента перестановки сколько элементов больших него стоит перед ним (или сколько элементов меньших него стоит за ним) и все эти числа сложить.
Определение. Перестановка называется четной (нечетной), если число инверсий в ней четное (нечетное). Перестановка без инверсий считается четной.
