Розглянемо безліч перших натуральних чисел, яке позначимо як.
Визначення. Перестановкою безлічі елементів з назвемо будь-яке розташування цих елементів в деякому порядку. Число назвемо порядком перестановки.
Приклад 1. Розглянемо. Перестановками для елементів з будуть: і т.д.
Можна показати, що число різних перестановок для безлічі з елементів одно.
Визначення. Числа і утворюють інверсію (порушення порядку) в перестановці. якщо і розташоване лівіше.
Визначення. Число інверсій всіх елементів перестановки назвемо числом інверсій перестановки і позначимо.
Для підрахунку числа інверсій в перестановці необхідно підрахувати для кожного елемента перестановки скільки елементів великих нього стоїть перед ним (або скільки елементів менших нього стоїть за ним) і всі ці числа скласти.
Приклад 2. Підрахувати число інверсій в перестановці.
Трійка інверсій не утворює, четвірка теж, одиниця дає три інверсії. Отже,.
Визначення. Перестановка називається парною (непарної). якщо число інверсій в ній парне (непарне). Перестановка без інверсій вважається парної.
Властивість 1. Якщо в перестановці поміняти місцями будь-які два елементи, то її парність зміниться.
При перестановці місцями сусідніх елементів число інверсій або на одиницю збільшується, якщо ця пара елементів інверсії не утворювалися, або на одиницю зменшується, якщо вихідна пара елементів інверсію утворювала. Тобто вихідне число інверсій змінюється на одиницю, а, отже, змінюється і парність перестановки.
Розглянемо випадок не сусідніх елементів.
Нехай перестановка має вигляд. Поміняємо місцями. Отримаємо перестановку. Для того, щоб з перестановки отримати перестановку. переставимо в елемент на місце між. Для цього потрібно зробити перестановок. Після цього перемістимо елемент на місце. для чого потрібно зробити перестановок. Так як при перестановці сусідніх елементів парність змінюється, то всього змін парності буде. тобто парність перестановки зміниться.
Властивість 2. Для число парних і непарних перестановок для безлічі одно.
Очевидно, що кожної парної перестановці відповідає непарна перестановка і навпаки. Отже, тих і інших однакова кількість. А тому всього перестановок. то парних і непарних буде по кожних.
Приклад 3. Підібрати числа так, щоб перестановка була парній.
Так як перестановка шостого порядку, то можуть набувати значень або 2, або 6.
У разі отримуємо перестановку. Підрахуємо число інверсій в ній:. тобто маємо непарну перестановку.
Залишається розглянути випадок. Тоді отримуємо перестановку. .
Число інверсій в можна було б не підраховувати, а скористатися тим, що з непарності відразу слід парність перестановки відповідно до властивістю 1.
Приклад 4. Яка максимальна кількість інверсій може бути в перестановці?
Відповідь на питання випливає з технології підрахунку числа перестановок. Число інверсій в перестановці буде максимальним, якщо кожний наступний елемент перестановки буде менше попереднього, т. Е..
Приклад 5. Скільки інверсій утворює число 1 в перестановці.
Інверсії з одиницею утворюють тільки перші елементів перестановки, тобто =.