Подстановки и перестановки n-степени

Пусть дан отрезок натурального ряда {1,2,…,n}. Назовем перестановкой порядка n любое расположение элементов этого множества.

Обозначим через Pn – число перестановок порядка n. Можно показать, что Pn=n!, n!=(n-1)…2*1

P₃=3!=3*2*1=6

Пусть дана перестановка порядка n: n₁, n₂,…n_k…n_j…n_n

n_k, n_j совершают инверсию n_k>n_j

ОПРЕДЕЛЕНИЕ:

Перестановку называют четной (нечетной), если общее число инверсий совершаемых всеми символами этой перестановки четно (нечетно).

ЛЕММА:

Если в перестановке поменять местами любые 2 символа, то четность перестановки изменяется на противоположную.

ОПРЕДЕЛЕНИЕ:

Подстановкой называют взаимноодназначное отображение множества {1,2,…,n} на себя.

Подстановки принято записывать:

Отметим что разных подстановок существует n!

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

ОПРЕДЕЛЕНИЕ:

Подстановка называется четной (нечетной) если ее строки имеют одинаковую (разную) четность.