Підстановка елементів даної безлічі (математична), заміна кожного з його елементів а яким-небудь іншим елементом j( а ) з тієї ж безлічі; при цьому повинні виходити всі елементи вихідної безлічі і кожен лише один раз. Таким чином, поняття П. по суті збігається з поняттям взаємно однозначного відображення безлічі на себе (див. Взаємно однозначна відповідність ), проте воно застосовується переважно до кінцевої безлічі. Лише цей випадок і розглядається нижчим. Для П. прийнятий запис
,
тут під кожним з елементів даної безлічі написаний відповідний йому елемент. Оскільки властивості П. не залежать від природи елементів а, b..., з, те переважно (в усякому разі — в учбових цілях) використовують цілі числа 1, 2..., n, при цьому у верхньому рядку вони переважно записуються в своєму природному порядку; П. приймає вигляд
або простіше
,
де j 1 , j 2 ..., j n — ті ж числа 1, 2..., n, але записані, можливо, в якому-небудь іншому порядку. Т. о. другий рядок П. утворює перестановку j 1 , j 2 ..., j n з чисел 1, 2..., n. Різних П. з n елементів існує стільки ж, скільки і перестановок, тобто n ! = 1×2×3×...× n . Підстановка
,
що залишає на місці всі елементи називається одиничною, або тотожною. Для кожної підстановки А існує зворотна, тобто така, яка переводить j i в i; вона позначається через А -1 . Наприклад,
;
.
Результат послідовного вживання двох підстановок А і В знову буде деякою підстановкою З: якщо А переводить i в j i , а В переводить j i в y i , то З переводить i в y i . Підстановка З називається твором підстановок А і В, що записується так: З = АВ. Наприклад, якщо
;,
.
При множенні П. не виконується закон комутативності, т. е ., взагалі кажучи, АВ ¹ ВА; так, в тому ж прикладі
.
Легко бачити, що IA = AI = А, АА -1 = А -1 А = I, А ( ВС ) = ( АВ ) З (асоціативний закон). Т. о., все П. з n елементів утворюють групу, звану симетричною групою міри n.
П., що переставляє місцями лише 2 елементи i і j, називають транспозицією і позначається так: ( i, j ), наприклад
Будь-яку П. можна розкласти в твір транспозицій. Число множників при розкладанні різними способами даною П. в твір транспозицій завжди буде або парним, або непарним. Відповідно до цього і П. називають або парною, або непарною; наприклад, А = (1, 3)(5, 4)(5, 1) — непарна П. Четность П. можна визначити також по числу інверсій, тобто по числу порушень порядку в нижньому рядку П., якщо числа верхнього рядка розташовані в їх природному порядку: парність П. збігається з парністю числа інверсій; наприклад, в нижньому рядку підстановки А є 5 інверсій, тобто випадків, коли більше число стоїть раніше меншого: (3, 2), (3, 1),(2, 1), (5, 1) і (5, 4). Існує n !/2 парних і n !/2 непарних П. з n елементів.
П., що циклічно переставляє дану групу елементів, а останні елементи що залишає на місці, називається циклом. Число елементів, що переставляються, називають довжиною циклу. Наприклад, підстановка А є цикл довжини 4: вона переводить 1 у 3, 3 в 5, 5 в 4, 4 в1; коротко це записується так: А = (1, 3, 5, 4). Транспозиція є цикл довжини 2. Будь-яку П. можна розкласти в твір незалежних (тобто загальних елементів, що не мають) циклів. Наприклад,
