Подстановки

Определение. Любая биекция множества первых n натуральных чисел в себя называется подстановкой из n элементов.

Пусть М={1, 2, 3,..., n}. Так как подстановка - это биекция множества М на М, то ее можно задать перечислением пар элементов прообраз - образ. Принята следующая форма записи подстановок:

A=, где a_k, i_k ÎM.

Так как в определении подстановки существенно лишь то, как по данному прообразу определяется образ, и не существенно, в каком порядке записаны прообразы и соответствующие им образы, то всякую подстановку можно записать в виде:

A=.

Так как каждая строка подстановки есть перестановка, то можно говорить о четности верхней и нижней строк подстановки, понимая под этим четность соответствующих перестановок. Причем при любой форме записи подстановки А четности ее строк либо совпадают, либо различны.

Определение. Подстановка, у которой обе строки имеют одинаковую четность, называется четной.

Теорема. Подстановка А тогда и только тогда будет четной, когда общее число инверсий в верхней и нижней строках четно, и будет нечетной тогда и только тогда, когда общее число инверсий в верхней и нижней строках нечетно.

(Доказательство - самостоятельно.)