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

Запись означает, что в первой

Запись означает, что в первой

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

Определение 1. Подстановкой из n элементов называется биектив­ное отображение из множества {1, 2,..., n} в себя. Запись вида

fi1 i2-in Л

\Jih-}J ’

где i1, i2, —, in — различные элементы множества {1,2, —, n} и j1, j2, —, jn —различные элементы множества {1,2, —, n}, обозна­чает подстановку a, для которой a(ik) = jk при всех k g {1, 2, —, n}. Множество подстановок из n элементов обозначается Sn. Подстанов­ку можно графически изобразить следующим образом. Расположим на плоскости элементы множества {1,2, —, n} и для каждого i проведем стрелку из элемента i в элемент a(i). То, что получилось, называется графом подстановки.

& Проясним несколько моментов, которые могут вызвать трудности после прочтения определения. Несмотря на данное «формальное» определение, подстановка — это очень наглядный объект. При реше­нии задач этого листка следует обязательно «поиграть» с подстанов­ками, проверяя утверждения для небольших n, в том числе, сделав несколько фишек с номерами, и переставляя их.

Запись ^ j'”означает, что в первой строке стоят числа 1, 2,

—, n, как-то перемешанные (то есть не обязательно по порядку), а в нижней строке тоже стоят числа 1, 2, —, n, возможно, перемешанные по-другому. Отметим отдельно, что подстановка — это биективное отображение. Запись a(ik) = jk означает, что число (ik) при подста­новке (ведь подстановка —это отображение) переходит в число jk.

Важно понимать, что требование того, чтобы отображение пе­реводило именно множество {1, 2, —, n} в себя — это вопрос согла­шения. Можно было бы определить подстановку на произвольном

100                         Подстановки 1 Ходим по циклу

множестве из п элементов. Этой темы мы еще коснемся в следующих листках, когда определим действие группы.