ПОДСТАНОВКИ.

Date: 2015-10-07; view: 385.

Пусть X®X , при этом если — биективно, то часто называют подстановкой. Мы ограничимся случаем, когда число элементов конечно, и равно n .

X ={1,2,3,…,n}, тогда отображение можно записать в виде таблицы:

(1)

Если подстановка, тогда — перестановка. Запись отображения в виде таблице (1) позволяет хорошо перемножать отображения.

Пример.

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

< Пусть имеем = .Согласно теореме 3 предыдущего параграфа, существует последовательность транспозиций переводящая первую перестановку во вторую, пусть это будет следующая последовательность транспозиций t1,t2,…,tn. Тогда очевидно, что , ибо отображения действуют на одном и том же множестве и результат их действия одинаков. >

Замечание. Разложение подстановки в произведение транспозиций, вообще говоря, неоднозначно.

Теорема 2. Характер четности числа сомножителей во всех разложениях подстановки в произведение транспозиций один и тот же.

◄ Пусть подстановка вида (1) разлагается в произведение k транспозиций. Это значит, что существует последовательность k транспозиций, переводящая перестановку (1,2,…,n) (2) в перестановку (3). Однократное применение транспозиции меняет характер четности перестановки, поэтому k — четное число тогда и только тогда, когда перестановки(2) и (3) одного характера четности. Это и доказывает теорему. >

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

Упражнение. Число четных подстановок равно числу нечетных и равно n!/2.