БИЛЕТ 46. Перестановки и подстановки. Их четность. Умножение подстановок. Транспозиции. Изменение четности перестановки при транспозиции.
Перестановкой попарно различных элементов k[1],..,k[n] называется упорядоченный набор pi=(i[i],...,i[n]), и для каждого p найдется такое t, что i[p]=k[t].
Т. Число перестановок из n элементов равно n!
Транспозиция - перестановка, в которой 2 элемента поменялись местами, а другие остались на своих местах.
Т. Все n! перестановок из n элементов можно расположить в таком порядке, что каждая следующая перестановка получается из предыдущей одной транспозицией, причем начинать можно с любой перестановки.
Док-во: Докажем методом мат.индукции по параметру n. База очевидна. Теперь предположим, что все (n-1)! перестановок из n элементов можно получить с помощью транспозиций. Вначале в качестве исходной рассмотрим перестановку 1,2,..,n. По предположению индукции с помощью только транспозиций можно получить все перестановки элементов 2,...,n. В начало каждой перестановки припишем 1. В результате получим все (n-1)! перестановок с первым элементом 1. В последней из выписанных перестановок совершим транспозицию элементов 1 и 2. Выпишем все перестановки элементов, стоящих на всех местах, кроме первого, а потом припишем везде в начале 2. И так далее с каждым номером. Общее количество выписанных перестановок равно n(n-1)!=n!, причем все эти перестановки попарно различны.
Осталось показать, что можно начинать с любой перестановки. Для этого просто перенумеруем исходную перестановку.
Т. Транспозиция меняет четность перестановки.
Док-во: очевидно, что транспозиция двух соседних элементов добавляет/убирает одну инверсию, а значит и меняет четность. Когда будем менять элементы i[p] и i[s], мы совершим 2(s-p)-1 транспозиций (нечетное число), а значит четность перестановки изменится.
Подстановка - биекция fi конечного множества в себя.
Чтобы однозначно определить подстановку, достаточно указать образ каждого элемента. Это можно сделать, записав таблицу: т=(те 2 набора записать друг под другом).
Обозначим б(т)=б(k[1],..,k[n])+б(i[1],..,i[n]).
Т. Четность величины б(т) совпадает для всех таблиц, определяющих одну и ту же подстановку.
Док-во: транспозиция столбцов меняет знак обеих перестановок, а следовательно сохраняет знак величины б(т).