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

Подстано́вка мно́жества, взаимно однозначное отображение множества на себя. Термин «подстановка» главным образом применяется для конечного множества ${\displaystyle X}$. В этом случае удобно считать, что ${\displaystyle X=\{1,\ldots ,n\}}$, и записывать подстановку в виде

${\displaystyle \gamma ={\begin{pmatrix}1&2&\ldots &n\\i_{1}&i_{2}&\ldots &i_{n}\end{pmatrix}},}$ (*)

где ${\displaystyle i_{1},i_{2},\ldots ,i_{n}}$ – некоторая перестановка чисел ${\displaystyle 1,2,\ldots ,n}$ (впрочем, иногда термин «перестановка» употребляется как синоним термина «подстановка»). Запись (*) означает, что ${\displaystyle \gamma }$ переводит число ${\displaystyle k}$ в ${\displaystyle i_{k}}$, т. е. ${\displaystyle \gamma (k)=i_{k}}$ (пишут также ${\displaystyle k^{\gamma }=i_{k}}$) для ${\displaystyle i=1,2,\ldots ,n}$. Число всех различных подстановок множества ${\displaystyle X}$ при ${\displaystyle |X|=n}$ равно числу всех перестановок этого множества, т. е. ${\displaystyle n!}$. Произведение подстановок ${\displaystyle \alpha }$ и ${\displaystyle \beta }$ множества ${\displaystyle {\bar {X}}}$ определяется как последовательное выполнение отображений ${\displaystyle \alpha }$ и ${\displaystyle \beta }$ и задаётся формулой ${\displaystyle \alpha \beta (x)=\alpha (\beta (x))}$ для всех ${\displaystyle x\in X}$. Совокупность всех подстановок множества ${\displaystyle X}$ образует группу относительно введённого умножения, которая называется симметрической группой. Любая подгруппа симметрической группы называется группой подстановок.

Симметрическая группа подстановок множества ${\displaystyle X}$ обозначается ${\displaystyle S(X)}$, она содержит в качестве подгруппы ${\displaystyle SF(X)}$ группу, состоящую из таких подстановок ${\displaystyle \gamma }$, которые перемещают лишь конечное подмножество элементов [т. е. ${\displaystyle \gamma (x)\neq x}$ лишь для конечного множества элементов ${\displaystyle x\in X}$]. Если ${\displaystyle X}$ конечно и состоит из ${\displaystyle n}$ элементов, то симметрическая группа обозначается ${\displaystyle S_{n}}$.

Транспозицией называется такая подстановка множества ${\displaystyle X}$, которая меняет местами только два элемента ${\displaystyle i}$ и ${\displaystyle j}$; она обозначается ${\displaystyle (i,j)}$. В ${\displaystyle S_{n}}$ имеется ровно ${\displaystyle n(n-1)/2}$ транспозиций. Любая подстановка ${\displaystyle \gamma }$ из ${\displaystyle SF(X)}$ представима в виде произведения транспозиций. В частности, каждая подстановка из ${\displaystyle S_{n}}$ есть произведение транспозиций. Подстановка может разлагаться в произведение транспозиций многими способами. Однако для данной ${\displaystyle \gamma }$ характер чётности числа множителей в разложении на транспозиции не зависит от способа разложения. Подстановка, представимая в виде произведения чётного числа транспозиций, называется чётной, а разлагающаяся в произведение нечётного числа транспозиций – нечётной. В ${\displaystyle S_{n}}$ имеется ${\displaystyle n!/2}$ чётных подстановок и столько же нечётных. Если подстановка ${\displaystyle \gamma \in S_{n}}$ записана в виде (*), то её чётность совпадает с чётностью числа инверсий перестановки ${\displaystyle i_{1},\ldots ,i_{n}}$, которое равно числу таких пар ${\displaystyle \left\{i_{k},i_{j}\right\}}$, что ${\displaystyle k<j}$, ${\displaystyle i_{k}>i_{j}}$. Транспозиция, очевидно, есть нечётная подстановка. Применение одной транспозиции к любой перестановке меняет чётность числа её инверсий на противоположную. Произведение двух чётных, а также двух нечётных подстановок есть чётная подстановка, а чётной и нечётной подстановок (в любом порядке) – нечётная. Все чётные подстановки составляют нормальную подгруппу ${\displaystyle A(X)}$ в группе ${\displaystyle SF(X)}$, которая называется знакопеременной. При ${\displaystyle |X|=n}$ подгруппа ${\displaystyle A(X)}$ обозначается ${\displaystyle A_{n}}$.

Циклом длины ${\displaystyle l}$ называется такая подстановка ${\displaystyle \sigma }$ конечного множества ${\displaystyle Y=\left\{y_{1},\ldots ,y_{l}\right\}}$, что

${\displaystyle \sigma \left(y_{1}\right)=y_{2},\,\,\sigma \left(y_{2}\right)=y_{3},\ldots ,\,\,\sigma \left(y_{l-1}\right)=y_{l},\,\,\sigma \left(y_{l}\right)=y_{1}}$.

Конечный цикл обозначается ${\displaystyle \left(y_{1},y_{2},\ldots ,y_{l}\right)}$. Бесконечным циклом называется такая подстановка счётного множества

${\displaystyle Y=\left\{\ldots ,y_{-2},y_{-1},y_{0},y_{1},y_{2},\ldots \right\}}$,

что для любого целого ${\displaystyle i}$ ${\displaystyle \sigma \left(y_{i}\right)=y_{i+1}}$. Обозначение бесконечного цикла таково:

${\displaystyle \left(\ldots ,y_{-2},y_{-1},y_{0},y_{1},y_{2},\ldots \right)}$.

Цикл длины 2 есть транспозиция. Группа ${\displaystyle S_{n}}$ содержит ${\displaystyle (n-1)!}$ циклов длины ${\displaystyle n}$. Для любой подстановки ${\displaystyle \gamma }$ из ${\displaystyle S(X)}$ существует такое разбиение множества ${\displaystyle X}$ на непересекающиеся подмножества, что на каждом из них ${\displaystyle \gamma }$ действует как цикл. Конечные подмножества этого разбиения имеют вид

${\displaystyle \left\{x,\gamma (x),\ldots ,\gamma ^{l-1}(x)\right\}}$,

где ${\displaystyle \gamma ^{l}(x)=x}$, а бесконечные –

${\displaystyle \left\{\ldots ,\gamma ^{-2}(x),\gamma ^{-1}(x),x,\gamma (x),\gamma ^{2}(x),\ldots \right\}}$,

где ${\displaystyle \gamma ^{k}(x)\neq x}$ при ${\displaystyle k\neq 0}$. Циклы, индуцируемые подстановкой ${\displaystyle \gamma }$ на подмножествах разбиения, называются независимыми циклами подстановки ${\displaystyle \gamma }$. Например, ${\displaystyle (1,3,4)}$ и ${\displaystyle (2,5)}$ – независимые циклы подстановки

${\displaystyle \gamma =\left({\begin{array}{lllll}1&2&3&4&5\\3&5&4&1&2\end{array}}\right)}$;

${\displaystyle \gamma }$ записывается в виде

${\displaystyle (1,3,4)(2,5)}$

и является произведением своих независимых циклов. Вообще, если ${\displaystyle \gamma }$ нетождественная подстановка, имеющая лишь конечное число циклов неединичной длины, то ${\displaystyle \gamma }$ – произведение таких циклов. В частности, каждая нетождественная подстановка из ${\displaystyle SF(X)}$ является произведением своих независимых циклов неединичной длины. Порядок подстановки ${\displaystyle \gamma }$ из ${\displaystyle SF(X)}$, т. е. порядок циклической группы ${\displaystyle \langle \gamma \rangle }$, равен наименьшему общему кратному длин её независимых циклов.

Из независимых циклов данной подстановки можно получить независимые циклы подстановки, сопряжённой с ней. Например, если

${\displaystyle \gamma =(a_{1},\ldots ,a_{l})\ldots \left(a_{j},\ldots ,a_{n}\right)}$

произведение независимых циклов подстановки ${\displaystyle \gamma }$ из ${\displaystyle S_{n}}$, a ${\displaystyle \delta \in S_{n}}$ и ${\displaystyle \delta \left(a_{i}\right)=b_{i}}$, ${\displaystyle i=1,\ldots ,n}$, то

${\displaystyle \delta \gamma \delta ^{-1}=\left(b_{1},\ldots ,b_{l}\right)\ldots \left(b_{j},\ldots ,b_{n}\right)}$

– разложение подстановки ${\displaystyle \delta \gamma \delta ^{-1}}$ в произведение независимых циклов. Две подстановки группы ${\displaystyle S_{n}}$ тогда и только тогда сопряжены в ${\displaystyle S_{n}}$, когда они имеют одно и то же число независимых циклов каждой длины.

Пусть ${\displaystyle s\in S_{n}}$, ${\displaystyle k}$ – число независимых циклов подстановки ${\displaystyle s}$, включая и циклы длины 1. Тогда разность ${\displaystyle n-k}$ называется декрементом подстановки ${\displaystyle s}$. Наименьшее число множителей при разложении подстановки ${\displaystyle s}$ в произведение транспозиций совпадает с её декрементом. Чётность подстановки совпадает с чётностью её декремента.

Подстановки возникли впервые в комбинаторике 18 в. В конце 18 в. Ж.-Л. Лагранж применил их при исследовании разрешимости алгебраических уравнений в радикалах. О. Коши посвятил многочисленные исследования этому понятию. Ему, в частности, принадлежит идея разложения подстановки в произведение циклов. Исследования групповых свойств подстановки восходит к H. Абелю и особенно к Э. Галуа. Cм. Теория Галуа.