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

Задача 12. Дана подстановка о = (I 2 3 4 2 4 3 1 . Найти ее степени. Решение. Имеем: о2 = 1 2 3 4 4 1 3 2 • а 3 = а 2 оа = ( I 2 3 4^| 4 1 3 2 П 2 3 4 s '1 2 3 4 1 2 4 3 1 V 7 I 1 2 3 4 j Тогда очевидно, что а 4 = о3 ° а = = е о а = а и т.д. Свойства умножения подстановок. 1. Умножение выполняется только для подстановок одинако­ вой степени. 2. Для умножения подстановок не выполняется переместитель­ ный закон. 3. Для умножения подстановок выполняется сочетательный з а ­ кон: Oi(o2 о ст3) = (О] о о2)с3. Поэтому в дальнейшем не оговарива­ ется количество подстановок при умножении. 4. Подстановка не изменяется, если ее умножить на тождествен­ ную: с о е = е ° о =о. 5. Поскольку любая подстановка а — биекция, для нее суще­ ствует обратная функция, тоже являющаяся подстановкой: мож ­ но указать обратную о"1 е S„, т.е. такую, что о ° о-1 = а ”1 ° о = е. Чтобы из подстановки о = получить ' 1 2 ... Xj ... п ^ ^с(1) а (2 ) ... о (х , ) ... о ( л ) у обратную, нужно поменять местами образы и прообразы, т .е . верхнюю и нижнюю строчки, и, если требуется, привести к к а ­ ноническому виду. Например, о = Г1 2 3 4 5 6 7 3 6 2 5 3 1 7 4 у . Тогда о -1 '6 2 5 3 1 7 4" 1 2 3 4 5 6 7^ [ ( 1 2 3 4 5 6 7 ' 5 2 4 7 3 1 6 6. Обратная подстановка единственна. 7. Подстановка, обратная единичной, также является тожде­ ственной. 8. Для того чтобы перемножить степени подстановки о, доста­ точно эту подстановку возвести в степень, равную сумме показа­ телей множителей, т.е. от ° а”= ат+п, Ут, п е Z. Следствия 1. Для отрицательных значений показателя к справедливо сг1*1 = ( ( Г 1)!*!, V к е Z. 57