Подстановки

**Подстановка** на множестве $\{1, 2, \dots, n\}$ это взаимно однозначное отображение на себя: $$\begin{pmatrix} 1 & 2 & \dots & n \\ s_{1} & s_{2} & \dots & s_{n} \end{pmatrix}$$

Запишем подстановку в виде: $$\begin{pmatrix} 1 & 2 & \dots & n \\ s_{1} & s_{2} & \dots & s_{n} \end{pmatrix}$$ тогда **число инверсий** это число инверсий в нижней строке. **Чётность подстановки** - чётность числа инверсий. Обозначение: $(-1)^{\sigma}$

Пусть подстановка $\sigma$ записана в произвольном виде: $$\begin{pmatrix} i_{1} & i_{2} & \dots & i_{n} \\ s_{1} & s_{2} & \dots & s_{n} \end{pmatrix}$$ и $\sigma_{1} = (i_{1}, \dots, i_{n})$, $\sigma_{2} = (s_{1}, \dots, s_{n})$. Тогда **чётность подстановки** равна: $(-1)^{\sigma} = (-1)^{\sigma_{1}} \cdot (-1)^{\sigma_{2}}$

Приведём $\sigma_{1}$ с помощью $k$ транспозиций к виду $\varepsilon = (1, 2, \dots, n)$, вместе с этим совершая транспозиции в нижней строке. Так как $(-1)^{\varepsilon} = (-1)^{\sigma_{1}} \cdot (-1)^{k}$, то $(-1)^{k} = (-1)^{\sigma_{1}}$. Но так как транспозиции были и в нижней строке, то: $$(-1)^{\sigma} = (-1)^{\sigma_{2}} \cdot (-1)^{k} = (-1)^{\sigma_{1}} \cdot (-1)^{\sigma_{2}}$$ $\square$

Для подстановок верны аналогичные свойства перестановок