Перестановки.
Упорядоченная совокупность чисел 
в которой
1) 
2) 
называется перестановкой чисел 1,2,...,n.
Перестановка 1,2,...,n называется натуральной.
Преобразование перестановки, при котором два её числа 
меняются местами,называется транспозицией.
Говорят, что два числа 
в перестановке 
образуют инверсию(беспорядок), если большее из них предшествует меньшему, т.е. если 
при i 2 число четных перестановок равно числу нечетных. Действительно, после упорядочения в списке всех перестановок четные и нечетные перестановки будут чередоваться, а так как п! четно при n > 2, то количества четных и нечетных перестановок совпадают и равны n!/2.
С ледствие 2. От каждой перестановки из п чисел можно перейти к любой другой перестановке из этих же чисел при помощи конечного числа транспозиций.
Теорема 4.4. Если 
– перестановка из первых n натуральных чисел с числом инверсий s, то после преобразования ее в натуральную перестановку индексные номера 1,2,...,n образуют новую перестановку с тем же числом инверсий s.
Доказательство. Рассмотрим в перестановке
любые ее два числа 
и 
.
Числа и образуют либо инверсию ( > 
), либо порядок ( < 
). После преобразования перестановки в натуральную числа и будут располагаться следующим образом:
1, 2,..., ,..., ,..., 
в случае инверсии,
1, 2,..., ,..., ,..., n в случае порядка,
причем в обоих случаях i < j. Это означает, что числа и в перестановке и их индексы i и j в перестановке индексных номеров одновременно образуют либо инверсию, либо порядок. Следовательно, обе эти перестановки имеют одинаковое число инверсий s.