03. Подстановки: соответствия и равенство
Упорядоченный список, например , сообщает, какое число стоит на первом, втором и третьем месте. А если нужно явно записать соответствия «числу поставлено в пару число », «числу — число », «числу — число »? Для этого удобна таблица из двух строк.
Два ряда и столбцы
Пусть . Определение 23.1. Подстановка на — это двухстрочная таблица
у которой каждая строка является перестановкой чисел . Вертикальная пара называется -м столбцом. Она означает: верхнему числу сопоставлено нижнее .
Например, в таблице
пять столбцов. Четвёртый столбец — , то есть числу сопоставлено число . Остальные соответствия: , , , .
Верхняя строка содержит каждое число из ровно раз, поэтому для каждого входного числа указана ровно одна пара. Нижняя строка тоже содержит каждое число ровно раз: два разных входа не получают один и тот же выход, а каждый выход использован. Такое взаимно однозначное соответствие называют биекцией множества на себя. Двухстрочная таблица — способ показать эту биекцию.
Равенство: сравниваем пары, а не места столбцов
Определение 23.2. Две подстановки равны, если у них одни и те же столбцы, даже когда столбцы записаны в разном порядке. Например,
У обеих таблиц одинаковые пять пар:
Слева столбец первый, справа — четвёртый, но само соответствие не изменилось. Это один из способов записать данную подстановку.
Важно двигать столбец целиком. Если в верхней строке поменять местами и , но нижнюю строку оставить прежней, пары станут другими: уже будет стоять над , а — над . Такая таблица задаёт другую подстановку.
Равенство подстановок обладает обычной транзитивностью: если и , то . Причина проста: у всех трёх таблиц один и тот же набор столбцов. Если верхние строки двух равных таблиц записаны в одном порядке, то должны совпадать и нижние: под каждым верхним числом находится его единственный выход.
Здесь заметно отличие от предыдущего урока. Для перестановок-списков порядок мест входит в определение равенства. У подстановки порядок показа столбцов свободен, потому что верхнее число служит меткой входа и остаётся вместе со своим выходом.
Каноническая запись
Чтобы легко сравнивать подстановки, расположим столбцы по возрастанию верхних чисел. Получим канонический вид:
Любую подстановку можно так записать: в верхней строке каждое число от до присутствует один раз, поэтому нужные столбцы можно поставить в нужном порядке. Для нашего примера канонический вид равен
Проверьте, например, столбец для входа : в исходной таблице это , в канонической — тоже .
В каноническом виде верхняя строка у всех подстановок одинакова. Поэтому две канонические записи равны тогда и только тогда, когда у них совпадают нижние строки. Нижняя строка содержит выходы для входов в этом порядке.
Сколько подстановок и сколько записей одной подстановки
Нижняя строка канонического вида может быть любой перестановкой . Из предыдущего урока мы знаем, что таких списков . Каждому соответствует ровно одна подстановка. Поэтому утверждение 23.1 говорит:
где — множество всех подстановок на , а вертикальные черты обозначают число его элементов. Например, на есть разных подстановок.
Но у одной подстановки тоже есть разных табличных записей: можно переставить её различных столбцов всеми возможными способами. Это следствие 23.1. Оно не противоречит предыдущему результату. Число в первом случае считает разные соответствия, а во втором — разные порядки записи одного и того же соответствия.
Например, для
таблица обозначает ту же : её столбцы просто показаны в другом порядке. Таких порядков шесть, но подстановка при этом одна.
Проверь себя
- Найди канонический вид таблицы . Какое число сопоставлено числу ?
- Равны ли и ?
- Сколько различных подстановок существует на ? Сколько разных порядков столбцов имеет запись каждой из них?
Показать решение
1. Переносим столбцы целиком: . Входу соответствует выход .
2. Да: в обеих таблицах одни и те же столбцы , и .
3. Различных подстановок . У каждой также табличных представления, полученных перестановкой столбцов.
