Таблицы Брадиса

Остается лишь вспомнить ответ п!

Остается лишь вспомнить ответ п!

Элементы математики в задачах - Г. А. Мерзон

Задача 3. Какие из следующих изображений являются графами под­становок?

 

Решение. а) Картинка является графом подстановки (2341

б)   Картинка не является графом подстановки, так как в одну вершину входят две стрелки.

в)  Картинка является графом подстановки •

г)  Картинка является графом подстановки                 •

Задача 4. а) Сколько элементов в множестве Бп7

б)  Сколькими способами можно записать подстановку из п эле­ментов?

Конечно, имеется в виду число различных записей в виде таблицы ^                       (а не графиком, в виде таблицы и т. п.).                                                                                                                           ^

Решение, а) Заметим, что вопрос о числе биективных отображений из множества, состоящего из п элементов, в себя уже был разобран в задаче 2. Остается лишь вспомнить ответ: п! = п(п — 1)...1.

б)  Как уже было замечено, одна и та же подстановка может быть

(231^

,132,

дают одну и ту же подстановку. Нетрудно понять, что различные записи одной и той же подстановки могут различаться лишь поряд­ком столбцов. Следовательно, всего записей одной перестановки из п элементов столько же, сколько существует способов переставить п столбцов. То есть в точности столько же, сколько существует переста­новок из п элементов, а именно п!.

Чтобы избежать неоднозначности, обычно используют так назы­ваемую каноническую запись подстановки, при которой все числа сверху упорядочены по возрастанию. В этом случае вся информация

о  том, какие элементы куда переходят, содержится в нижней стро­ке. Но иногда, например, при умножении подстановок, оказывается удобнее пользоваться другими записями. Вот примеры подстановок,