Перестановки.

Упорядоченная совокупность чисел в которой

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.