09. Подстановки множества

Рассмотрим конечное непустое множество , .

Определение. Подстановкой -й степени множества называется взаимно однозначное отображение множества на себя

.

Если каждому элементу множества ставится в соответствие его номер – натуральное число, не превосходящее , то подстановка множества записывается в виде матрицы размерности :

.

Элементы первой строки матрицы являются прообразами отображения , элементы второй строки матрицы являются образами отображения .

Определение. Канонической называется подстановка, в которой прообразы располагаются в порядке возрастания.

Множество всех различных подстановок данного множества мощности N обозначается . Мощность множества равна числу перестановок элементов множества A.

.

Например, для заданного множества число всех его подстановок равно . Подстановки и являются различными каноническими подстановками множества . Подстановка не является канонической.

Определение. Произведением двух подстановок и множества А называется композиция отображений и .

Например, произведение подстановок и равно

Произведение подстановок и равно:

Произведение подстановок множества не является коммутативным.

Теорема 9.1. Для любых трех подстановок множества А , и верно .

Рассмотрим множество , .

Определение. Тождественной Подстановкой -й степени называется взаимно однозначное отображение множества на себя

.

В матричной форме тождественная подстановка записывается .

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

Теорема 9.2. Для любой подстановки множества А существует единственная обратная подстановка .

Теорема 9.3.

.

Например, для подстановки множества обратная подстановка .

В комбинаторном анализе под Инверсией понимается пара образов подстановки множества, в которой при .

Также Инверсией называется перемена местами двух соседних образов Канонической подстановки.

Теорема 9.4. Всякую подстановку можно представить в виде произведения инверсий.

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

Определение. Число называется Чётностью подстановки .

Определение. Чётной называется подстановка , для которой , Нечётной называется подстановка , для которой .

Например, каноническая подстановка множества является нечётной, так как число инверсий, приводящих к равно трём:

.

В множестве имеется чётных и нечётных подстановок.

Задачи и упражнения.

9.1. Для следующих подстановок укажите степень подстановки, приведите подстановку к каноническому виду, найдите обратную подстановку:

1) ; 2) ;

3) ; 4) .

9.2. Для подстановок и задачи 3.21. найдите

1) ; 2) ; 3) ; 4) .

9.3. Найти чётность подстановки для заданных подстановок и .

< Предыдущая		Следующая >