В результате изучения этой темы читатель
узнает: определение перестановки из n элементов, число всех перестановок из n элементов, определение подстановки, матричный способ записи подстановки, канонический вид записи подстановки, формулировку теоремы о числе подстановок, понятие циклического разложения подстановки, формулировку теоремы о разложении подстановки в произведение непересекающихся циклов, понятие транспозиции, формулировку теоремы о представлении подстановки произведением транспозиций, как задаётся операция умножения подстановок, свойства операции умножения подстановок, символ обозначения симметрической группой подстановок n-ой степени, понятие порядка подстановки, формулировку теоремы о порядке подстановки циклической подгруппы, понятие инверсии, понятия чётной и нечётной подстановок, формулировку о числе чётных подстановка, аксиомы знакопеременной группы;
научится: задавать подстановки через биективное отображение, матрицей, произведение циклов и произведение транспозиций, осуществлять умножение подстановок, определять обратную подстановку для заданной, рассчитывать число k-циклов в симметрической группе подстановок n-ой степени, определять порядок подстановки циклической подгруппы, определять число инверсий, выяснять, является ли заданная подстановка чётной (нечётной).
Определение. Пусть K – конечное множество, состоящее из n элементов, которые могут быть перенумерованы первыми n натуральными числами, тогда каждая последовательность n различных элементов с учетом порядка называется перестановкой этих элементов (перестановкой из n элементов).
Каноническая запись подстановок.
Неважно, в каком порядке располагаются столбцы, поэтому одна и та же подстановка допускает различные представления, как показано в примере.
Однако каждую подстановку можно записать таким образом, чтобы все элементы в верхней строке располагались в порядке возрастания.
Такая запись подстановок называется канонической записью.
При канонической записи подстановок любые две подстановки одной степени будут отличаться только перестановками во второй (нижней) строке:
При решении задач часто бывает удобно использовать для подстановок запись, не являющуюся канонической, однако поскольку любая подстановка может быть приведена к каноническому виду путем перестановки столбцов, то результирующий ответ задачи принято приводить в каноническом виде.
Тождественная подстановка.
Заметим, что сокращенная запись цикла сводится к перечислению множества элементов, которые циклически переходят друг в друга.
В качестве Упражнения 1 представьте подстановку из таблицы в виде композиции независимых циклов.
Пример выполнения практического задания (вариант № 30 (II):
В качестве Упражнения 2 запишите в виде таблицы подстановку, записанную в виде независимых циклов, как показано в таблице ниже:
Пример выполнения практического задания (вариант № 30):
