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

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

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

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

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

$$\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.$$Конечный цикл обозначается $\left(y_1, y_2, \ldots, y_l\right)$. Бесконечным циклом называется такая подстановка счётного множества

$$Y=\left\{\ldots, y_{-2}, y_{-1}, y_0, y_1, y_2, \ldots\right\},$$что для любого целого $i$ $\sigma\left(y_i\right)=y_{i+1}$. Обозначение бесконечного цикла таково:

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

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

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

$$\gamma=\left(\begin{array}{lllll} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{array}\right);$$$\gamma$ записывается в виде

$$(1,3,4)(2,5)$$и является произведением своих независимых циклов. Вообще, если $\gamma$ нетождественная подстановка, имеющая лишь конечное число циклов неединичной длины, то $\gamma$ – произведение таких циклов. В частности, каждая нетождественная подстановка из $S F(X)$ является произведением своих независимых циклов неединичной длины. Порядок подстановки $\gamma$ из $S F(X)$, т. е. порядок циклической группы $\langle\gamma \rangle$, равен наименьшему общему кратному длин её независимых циклов.

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

$$\gamma=( a_1, \ldots, a_l) \ldots\left(a_j, \ldots, a_n\right)$$произведение независимых циклов подстановки $\gamma$ из $S_n$, a $\delta \in S_n$ и $\delta\left(a_i\right)=b_i$, $i=1, \ldots, n$, то

$$\delta \gamma \delta^{-1}=\left(b_1, \ldots, b_l\right) \ldots\left(b_j, \ldots, b_n\right)$$– разложение подстановки $\delta \gamma \delta^{-1}$ в произведение независимых циклов. Две подстановки группы $S_n$ тогда и только тогда сопряжены в $S_n$, когда они имеют одно и то же число независимых циклов каждой длины.

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

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