Подстановка

множества - взаимно однозначное отображение множества на себя. Термин "П." главным образом применяется для конечного множества X. В этом случае удобно считать, что Х={1, . ., п}, изаписывать П. В виде (*) где i1, i2, . ., in - нек-рая перестановка чисел 1, 2, . ., n (впрочем, иногда термин "перестановка" употребляется как синоним термина "П.", см., напр., [2] с. 146). Запись (*) означает, что gпереводит число kв ik, то есть y(k)=ik (пишут также kg=ik).для i=1, 2, . ., n. Число всех различных П. Множества Xпри |Х| = n равно числу всех перестановок этого множества, т. Е. N. Произведение подстановок a и b множества определяется как последовательное выполнение отображений a и b и задается формулой ab(x)=a(b(x)) для всех .

Совокупность всех П. Множества Xобразует группу относительно введенного умножения, к-рая наз. симметрической группой. Любая подгруппа симметрич. Группы наз. подстановок группой. Симметрич. Группа П. Множества Xобозначается S(X), она содержит в качестве подгруппы SF(X) - группу, состоящую из таких подстановок g, к-рые перемещают лишь конечное подмножество элементов (то есть лишь для конечного множества элементов ). Если Xконечно и состоит из пэлементов, то симметрич. Группа обозначается Sn. Транспозицией наз. Такая П. Множества X, к-рая меняет местами только два элемента iи j. Она обозначается (i, j). В S п имеется ровно ( п-1)/2 транспозиций. Любая подстановка g. Из SF(X).представима в виде произведения транспозиций. В частности, каждая П.

Из Sn есть произведение транспозиций. П. Может разлагаться в произведение транспозиций многими способами. Однако для данной g. Характер четности числа множителей в разложении на транспозиции не зависит от способа разложения. П., представимая в виде произведения четного числа транспозиций, наз. Четной, а разлагающаяся в произведение нечетного числа транспозиций - нечетной. В Sn имеется n!/2 четных П. И столько же нечетных. Если П. записана в виде (*), то ее четность совпадает с четностью числа инверсий перестановки i1, . ., in к-рое равно числу таких пар {ik, ij}, что k<j, ik>ij. Транспозиция, очевидно, есть нечетная II. Применение одной транспозиции к любой перестановке меняет четность числа ее инверсий на противоположную.

Произведение двух четных, а также двух нечетных П. Ость четная П., а четной и нечетной П. (в любом порядке) - нечетная. Все четные П. Составляют нормальную подгруппу (X).в группе SF(X), к-рая наз. Знакопеременной. При |Х|= п подгруппа (X).обозначается А п. Циклом длины lназ. Такая подстановка а конечного множества Y={y1, . ., у l], что Конечный цикл обозначается (y1, y2, . ., yl). Бесконечным циклом наз. Такая П. Счетного множества что для любого целого i s(yi)=yi+1 Обозначение бесконечного цикла таково. Цикл длины 2 есть транспозиция. Группа Sn содержит ( п-1). Циклов длины п. Для любой подстановки g из S(X).существует такое разбиение множества X на непересекающиеся подмножества, что на каждом из них g действует как цикл.

Конечные подмножества этого разбиения имеют вид где gl(x}=x, а бесконечные - где при . Циклы, индуцируемые подстановкой Y на подмножествах разбиения, наз. Независимыми циклами подстановки g. Например, (1, 3, 4) и (2, 5)- независимые циклы П. g записывается в виде и является произведением своих независимых циклов. Вообще, если g нетождественная П., имеющая лишь конечное число циклов неединичной длины, то g - произведение таких циклов. В частности, каждая нетождественная П. Из SF(X).является произведением своих независимых циклов неединичной длины. Порядок подстановки g из SF(X), т. Е. Порядок циклич. Группы <g>, равен наименьшему общему кратному длин ее независимых циклов. Из независимых циклов данной П.

Можно получить независимые циклы П., сопряженной с ней. Напр., если произведение независимых циклов подстановки g из Sn, а и d( а i)=bi, i=l, . ., п, то - разложение подстановки в произведение независимых циклов. Две П. Группы Sn тогда и только тогда сопряжены в Sn, когда они имеют одно и то же число независимых циклов каждой длины. Пусть , k - число независимых циклов подстановки s, включая и циклы длины 1. Тогда разность п-kназ. Декрементом подстановки s. Наименьшее число множителей при разложении подстановки s в произведение транспозиций совпадает с ее декрементом. Четность П. Совпадает с четностью ее декремента. П. Возникли впервые в комбинаторике 18 в. В кон. 18 в. Ж. Лагранж (J. Lagrange) применил их при исследовании разрешимости алгебраич.

Уравнении в радикалах. О. Коши (A. Cauchy) посвятил многочисленные исследования этому понятию. Ему, в частности, принадлежит идея разложения П. В произведение циклов. Исследования групповых свойств П. Восходит к Н. Абелю (N. Abel) и особенно к Э. Галуа (Е. Galois). См. Галуа теория, Подстановок группа. Лит.:[1] Jordan С., Traite des substitutions et des equations altfebriques, P., 1057. [2] Кострикин А. И., Введение в алгебру, М., 1977. [3] Курош А. Г., Курс высшей алгебры, 11 изд., М., 1975. [4] Холл М., Теория групп, пер. С англ., М., 1962. Д. А. Супруненко.