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

Подстановки 2

Подстановки 2

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

Подстановки 2

листок 2Д / декабрь 2004

Листок состоит из двух частей. Первая часть посвящена поня­тию четности подстановки. С его помощью удается, в частности, решить классическую задачу об игре в пятнашки. Во второй части в основном обсуждается возведение подстановок в степень и порядок перестановки. В дополнительных задачах листка появляется понятие сопряженных подстановок.

Одной из целей изучения подстановок является подготовка к аб­страктной теории групп: с одной стороны, подстановки дают важный (но доступный) пример группы, с другой — часть рассуждений из этого листка без существенных изменений переносится на случай произвольной группы. Поработав с конкретной, достаточно содер­жательной группой, можно почувствовать дух теории групп. После этого абстрактное определение группы будет более понятным и есте­ственным. Да и вообще, по теореме Кэли любая конечная группа есть подгруппа группы подстановок, так что даже формально все богат­ство теории конечных групп можно увидеть на группах подстановок.

Определение 1. Пусть дана подстановка (1 2''' п ). Беспорядком на-

/-к                              зывается пара (к,1), 1^к<1^п, такая что ]к> _/'г. Подстановка                    ж

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

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

Задача 0. Определим четность подстановки, записанной в произ­вольной форме, как четность суммы беспорядков в верхней и нижней строках. Докажите, что тем самым получится эквивалентное опре­деление (т. е. все подстановки, являющиеся четными (нечетными) по определению 1, будут также являться четными (нечетными) по новому определению и наоборот).