Подстановки

Определение 4.1. Подстановкой n-го порядка называется взаимно однозначное отображение множества чисел от 1 до n на себя.

Подстановки можно записывать в виде таблицы, где под каждым числом стоит его образ. Например, подстановка 3 порядка переводит 1 в 3, 2 в 1 и 3 в 2.

Лемма 4.1. Число подстановок n-го порядка равно n!.

Доказательство очевидно.

Определение подстановки, как взаимно однозначной функции позволяет перенести понятие суперпозиции функций на подстановки. Пусть подстановка f ставит в соответствие номеру i номер f(i), а подстановка g ставит в соответствие номеру j номер g(j). Рассмотрим функцию f(g(i)). Очевидно, эта функция задает взаимно однозначное отображение множества чисел от 1 до n, и, следовательно, определяет подстановку.

Определение 4.2. Подстановку, определенную функцией f(g(i)) называют суперпозицией или произведением подстановок g и f и обозначают gf.

Для примера найдем суперпозицию подстановок и . Поскольку f(g(1))=f(1)=2, f(g(2))=f(3)=3, f(g(3))=f(2)=1, то .

Отметим некоторые свойства операции произведения подстановок.

Свойство 4.1 Операция произведения подстановок не коммутативна, то есть в общем случае .

Действительно, Свойство 4.2. Операция умножения подстановок ассоциативна, то есть f(gh)=(fg)h.

Доказательство. В подстановке f(gh) номер i отображается в номер (gh)(f(i))=h(g(f(i))), а в подстановке (fg)h номер i отображается в число h((fg)(i))=h(g(f(i))). В обоих случаях образ совпадает.

Определение 4.3Подстановка называется тождественной, и обозначается e. Подстановка f называется обратной к подстановке g, если fg=e.

Свойство 4.3. Обратная подстановка существует и единственна.

Доказательство очевидным образом следует из определения подстановки как взаимно однозначного соответствия.

Начиная с некоторого номера j, построим последовательность чисел . В данной последовательности обязательно наступит повторение, поскольку множество значений подстановки конечно. Пусть - наименьший номер, после которого появляется ранее встречавшееся число в последовательности (т.е. и k>s). Если , то номер является образом двух номеров и , что противоречит определению подстановки как взаимно однозначного соответствия. Следовательно, , и последовательность , начиная с члена, начинает повторяться. Не повторяющаяся часть последовательности (т.е. её первые k+1 членов) называется циклом длины k+1.

Циклы называются независимыми, если никакие два цикла не имеют общих номеров.

Кроме табличной записи подстановок существует их запись в виде произведения независимых циклов.

Часто удобно представлять подстановку в виде произведения независимых циклов, а не в табличном виде. В отличие от табличного вида подстановка пишется в строчку. За каждым номером i следует его образ f(i). Номера в цикле разделены тире. Циклы пишутся через запятую. Не пишутся также элементы, которые переходят сами в себя (т.е. циклы длины 1). Например, подстановка запишется как (1-3), а подстановка запишется как (1-3-2, 4-5)