Розташування перших n натуральних чисел в порядку їх зростання визначається як еталонного, а будь-який інший порядок розміщення цих чисел - як перестановка "нормального" розташування.
Виявляється, що довільна перестановка таких чисел може бути отримана з нормальної регулювання за допомогою деякого числа транспозиція, тобто змінами позицій однієї пари елементів перестановки при збереженні позицій інших елементів.
Розглянемо безліч S натуральних чисел від 1 до n. розташованих в порядку зростання (в природному порядку):
Під перестановкою безлічі S розуміється безліч цих же чисел, впорядковане деяким іншим чином:
Перестановка називається транспозицією. якщо переставляються місцями тільки два елементи множини, тоді як інші елементи залишаються на своїх місцях.
Будь-яку перестановку безлічі S можна здійснити за допомогою декількох транспозиція. Наприклад, перестановка є результатом трьох транспозиція безлічі S.
Кажуть, що перестановка безлічі S містить інверсію елементів i j і i k. якщо порушений їх природний порядок розташування, тобто більший елемент розташований лівіше меншого:
Наприклад, перестановка містить три інверсії елементів:
2 і 1,
4 і 1,
4 і 3.
Число інверсій визначає парність перестановки. Перестановка називається парною. якщо вона містить парне число інверсій елементів. Непарна перестановка містить непарне число інверсій.
Зауважимо, що парна перестановка може бути перетворена до природного порядку за допомогою тільки парного числа транспозиція, тоді як для перетворення непарної перестановки до природного порядку потрібно непарне число транспозиція. (Це твердження є наслідком Теореми 1. см розділ "Теореми про транспозиція і перестановках".)
Приклад. Перестановка є непарною, оскільки містить 3 інверсії елементів.
Можна також сказати, що перестановка є непарною, оскільки являє собою послідовність трьох транспозиція.