bulgakov

03. Подстановки: соответствия и равенство

Упорядоченный список, например (4,1,2)(4,1,2), сообщает, какое число стоит на первом, втором и третьем месте. А если нужно явно записать соответствия «числу 11 поставлено в пару число 44», «числу 22 — число 11», «числу 33 — число 22»? Для этого удобна таблица из двух строк.

Два ряда и столбцы

Пусть Nn={1,2,…,n}N_n=\{1,2,\ldots,n\}. Определение 23.1. Подстановка на NnN_n — это двухстрочная таблица

π=(i1i2⋯inj1j2⋯jn),\pi= \begin{pmatrix} i_1&i_2&\cdots&i_n\\ j_1&j_2&\cdots&j_n \end{pmatrix},

у которой каждая строка является перестановкой чисел NnN_n. Вертикальная пара (ikjk)\binom{i_k}{j_k} называется kk-м столбцом. Она означает: верхнему числу iki_k сопоставлено нижнее jkj_k.

Например, в таблице

π=(4215323541)\pi= \begin{pmatrix} 4&2&1&5&3\\ 2&3&5&4&1 \end{pmatrix}

пять столбцов. Четвёртый столбец — (54)\binom54, то есть числу 55 сопоставлено число 44. Остальные соответствия: 4↦24\mapsto2, 2↦32\mapsto3, 1↦51\mapsto5, 3↦13\mapsto1.

Верхняя строка содержит каждое число из NnN_n ровно раз, поэтому для каждого входного числа указана ровно одна пара. Нижняя строка тоже содержит каждое число ровно раз: два разных входа не получают один и тот же выход, а каждый выход использован. Такое взаимно однозначное соответствие называют биекцией множества NnN_n на себя. Двухстрочная таблица — способ показать эту биекцию.

Равенство: сравниваем пары, а не места столбцов

Определение 23.2. Две подстановки равны, если у них одни и те же столбцы, даже когда столбцы записаны в разном порядке. Например,

(4215323541)=(2154335421).\begin{pmatrix} 4&2&1&5&3\\ 2&3&5&4&1 \end{pmatrix} = \begin{pmatrix} 2&1&5&4&3\\ 3&5&4&2&1 \end{pmatrix}.

У обеих таблиц одинаковые пять пар:

(15),(23),(31),(42),(54).\binom15,\quad\binom23,\quad\binom31,\quad\binom42,\quad\binom54.

Слева столбец (42)\binom42 первый, справа — четвёртый, но само соответствие 4↦24\mapsto2 не изменилось. Это один из способов записать данную подстановку.

Важно двигать столбец целиком. Если в верхней строке поменять местами 44 и 22, но нижнюю строку оставить прежней, пары станут другими: 44 уже будет стоять над 33, а 22 — над 22. Такая таблица задаёт другую подстановку.

Равенство подстановок обладает обычной транзитивностью: если π=σ\pi=\sigma и σ=λ\sigma=\lambda, то π=λ\pi=\lambda. Причина проста: у всех трёх таблиц один и тот же набор столбцов. Если верхние строки двух равных таблиц записаны в одном порядке, то должны совпадать и нижние: под каждым верхним числом находится его единственный выход.

Здесь заметно отличие от предыдущего урока. Для перестановок-списков (i1,…,in)(i_1,\ldots,i_n) порядок мест входит в определение равенства. У подстановки порядок показа столбцов свободен, потому что верхнее число служит меткой входа и остаётся вместе со своим выходом.

Каноническая запись

Чтобы легко сравнивать подстановки, расположим столбцы по возрастанию верхних чисел. Получим канонический вид:

π=(12⋯na1a2⋯an).\pi= \begin{pmatrix} 1&2&\cdots&n\\ a_1&a_2&\cdots&a_n \end{pmatrix}.

Любую подстановку можно так записать: в верхней строке каждое число от 11 до nn присутствует один раз, поэтому нужные столбцы можно поставить в нужном порядке. Для нашего примера канонический вид равен

π=(1234553124).\pi= \begin{pmatrix} 1&2&3&4&5\\ 5&3&1&2&4 \end{pmatrix}.

Проверьте, например, столбец для входа 33: в исходной таблице это (31)\binom31, в канонической — тоже (31)\binom31.

В каноническом виде верхняя строка у всех подстановок одинакова. Поэтому две канонические записи равны тогда и только тогда, когда у них совпадают нижние строки. Нижняя строка содержит выходы для входов 1,2,…,n1,2,\ldots,n в этом порядке.

Сколько подстановок и сколько записей одной подстановки

Нижняя строка канонического вида может быть любой перестановкой NnN_n. Из предыдущего урока мы знаем, что таких списков n!n!. Каждому соответствует ровно одна подстановка. Поэтому утверждение 23.1 говорит:

∣Sn∣=n!,|S_n|=n!,

где SnS_n — множество всех подстановок на NnN_n, а вертикальные черты обозначают число его элементов. Например, на N3N_3 есть 3!=63!=6 разных подстановок.

Но у одной подстановки тоже есть n!n! разных табличных записей: можно переставить её nn различных столбцов всеми возможными способами. Это следствие 23.1. Оно не противоречит предыдущему результату. Число n!n! в первом случае считает разные соответствия, а во втором — разные порядки записи одного и того же соответствия.

Например, для

α=(123213)\alpha=\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}

таблица (312321)\begin{pmatrix}3&1&2\\3&2&1\end{pmatrix} обозначает ту же α\alpha: её столбцы (33),(12),(21)\binom33,\binom12,\binom21 просто показаны в другом порядке. Таких порядков шесть, но подстановка при этом одна.

Проверь себя

  1. Найди канонический вид таблицы (312231)\begin{pmatrix}3&1&2\\2&3&1\end{pmatrix}. Какое число сопоставлено числу 11?
  2. Равны ли (123312)\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix} и (231123)\begin{pmatrix}2&3&1\\1&2&3\end{pmatrix}?
  3. Сколько различных подстановок существует на N4N_4? Сколько разных порядков столбцов имеет запись каждой из них?
Показать решение

1. Переносим столбцы целиком: (123312)\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}. Входу 11 соответствует выход 33.

2. Да: в обеих таблицах одни и те же столбцы (13)\binom13, (21)\binom21 и (32)\binom32.

3. Различных подстановок 4!=244!=24. У каждой также 4!=244!=24 табличных представления, полученных перестановкой столбцов.

ПрактикаЗагружаем тест…