Спирина, М.С. Дискретная математика

Подстановку вида о =(1, 2, п) = е называют тождественной, так как \/х е Еп, е(х) =х. Нетрудно видеть, что это частный случай уже рассмотренного в подразд. 1.3 единичного отображения. Пусть заданы две подстановки о, и о2, причем Е „— 3—» ^ - * Е ’„ -*Е”п. Штрихи означают то же множество Е„, толь­ ко служат для различия между областями определения и значе­ ний. Тогда произведение отображений а 2° о,: Еп — — > Е’ так­ же является подстановкой и называется произведением подстано­ вок О! и а 2и записывается о = о 2 ° о,. Очевидно, что произведение определено для подстановок одинаковой степени. Как и в других функциях, в подстановке о = о2 ° о , сначала выполняется первая подстановка, а затем вторая действует на ре­ зультат первой: о(х) = (о2 о о,)(х) = о 2(о,(х)). Поэтому (за исклю­ чением совпадений) для произведения подстановок не выполня­ ется переместительный закон. ( \ 5 4 3 2Л Задача 11. Даны две подстановки: о, = 3 5 2 4 1 а 2 - '1 2 1 Привести подстановки к канонической записи и наити их произведения. Решение. Вторая подстановка записана в каноническом виде, первая — нет. Поэтому в верхней строке запишем числа от 1 до 5, а в нижней 0 ,(1 ) = 3, о , (2) = 1, ..., о , (5) = 5. Итак, (1 2 3 4 5^ а, = . Найдем о2 ° о,. Сначала выполняется первая [3 1 4 2 5 J подстановка о,(1) = 3, а затем вторая о2(3) = 4, т.е. а 2 ° о,(1) = = о 2(о,(1)) = о 2(3) = 4. Поэтому можно сразу записывать в матри- П 2 3 4 5 ^ Аналогично найдем остальные об- цу: о2 оо, = V разы: о2 ° о, = 1 5^ и Теперь найдем о, ° о2: о 2(1) = 2, а a ,(2) = 1, т.е. о, о о 2(1) = о , ( о 2(1)) = о ,(2 ) = 1. (I 2 3 4 5Л В итоге получим о, ° о 2 = Ф 0 2 оо , . 1 5 2 4 3 Ч У Натуральной степенью подстановки о называется подстановка о л =о - . . . о, т.е. произведение п функций, каждая из которых есть о. Очевидно, что степень подстановки не зависит от порядка мно­ жителей. 56