§ 6. ПОРЯДОК ПЕРЕСТАНОВКИ

Для каждого преобразования можно рассмотреть его степени; степенью преобразования называется произведение

где — натуральное число. Далее будем обозначать его

Из определения степени преобразования вытекают такие равенства:

Положим также для каждого преобразования

Для перестановок (произвольных биекций) понятие степени можно обобщить и на случай целых отрицательных чисел, положив

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

Если — некоторая перестановка на множестве то для каждого целого также есть перестановка на М. Таких перестановок лишь конечное число, т. е. в последовательности не все перестановки разные.

Пусть для некоторых натуральных чисел выполняется равенство . Тогда

откуда , т. е. для каждой перестановки , где М — конечное множество, найдется по меньшей мере одно натуральное число s, такое, что Наименьшее из таких натуральных чисел называется порядком перестановки

Степени циклической перестановки находят по формуле

Это равенство можно толковать так.

Если какая-нибудь шестерня, которая имеет зубцов, поворачивается вокруг своего центра, то, занумеровав зубцы числами и зафиксировав некоторое начальное положение зубцов, ее повороты можно однозначно описывать перестановками на множестве Циклическая, перестановка

очевидно, описывает поворот на угол (зубец с номе ром 1 встает на место зубца с номером 2 и т. д.).

Не нарушая общности, будем считать, что шестерня поворачивается по часовой стрелке. Чтобы повернуть шестерню на угол надо k раз осуществить поворот на угол в одном направлении, так что перестановка отвечает такому положению шестерни, когда на месте первого зубца стоит 6-й, на месте второго и т. д. Если шестерню повернуть раз вокруг центра на угол то она займет начальное положение. Таким образом, для каждого цикла выполняется равенство

При этом для натуральных чисел, меньших , это равенство невозможно. Для перестановки описывают повороты шестерни на углы против часовой стрелки.

По доказанному в предыдущем параграфе произвольную перестановку можно разложить в произведение попарно взаимно простых циклов:

Для любых номеров произведение перестановок не зависит от порядка множителей. Пользуясь этим, степень перестановки для каждого целого можно записать так:

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

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

Порядок является очень важной характеристикой перестановки. Чисел , таких, что для произвольной перестановки существует много, но все они делятся на порядок перестановки.

Докажем это методом от противного. Допустим, что существует такое натуральное число k, для которого справедливо равенство

причем k не делится на порядок перестановки По определению порядка перестановки поэтому

Тогда имеем . Но

Таким образом,

Однако и мы пришли к противоречию, которое и доказывает сформулированное утверждение.

Выведем теперь правило для нахождения порядка произвольной перестановки. Прежде всего, заметим, что произведение нескольких взаимно простых перестановок может равняться тождественной перестановке лишь тогда, когда каждая из перестановок единична. Это вытекает из того, что произведение взаимно простых перестановок действует на каждую свою подвижную точку так, как действует на нее та перестановка для которой эта точка является подвижной. Поэтому из равенства (1) получаем, что тогда и только тогда, когда одновременно

Если перестановки есть циклы длины соответственно, т. е. имеют порядки наименьшее число , для которого одновременно выполняются все равенства (2), равняется, очевидно, наименьшему общему кратному чисел .

Следовательно, мы доказали, что порядок перестановки которая раскладывается в произведение циклов длиною есть наименьшее общее кратное чисел

Пример. Пусть

Разложим в произведение циклов:

Отсюда .

Упражнения

1. Найти порядок каждой из перестановок:

2. Найти порядки всех перестановок на множестве из 6 элементов.

3. Какой наивысший порядок могут иметь перестановки на множестве из 10 элементов?

4. Найти перестановку, обратную к циклу

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

6. Сколько существует перестановок порядка на множестве из 8 элементов?

7. Вывести формулу для нахождения порядка перестановки, пользуясь механическим толкованием действия возведения в степень.

8. Если — простое число, то для каждого перестановка есть цикл длины если число — составное, то эта перестановка будет циклом для чисел взаимно простых с и произведением циклов одинаковой длины в ином случае. Доказать это.

9. Доказать, что для каждой перестановки которая раскладывается в произведение l циклов одинаковой длины s, найдется цикл длины и натуральное число такое, что Единственный ли такой цикл?

10. 12 мальчиков перебрасываются разноцветными мячами, каждый из них бросает свой мяч всегда одному и тому же партнеру, все мячи бросаются одновременно, и никакие два мальчика не бросают мяч одному игроку. Через какое наименьшее число ходов игры все мячи окажутся в руках тех же мальчиков, что и в начале?

11. Колода из 36 карт тасуется - следующим образом. Колода берется лицевой стороной вниз в левую руку и карты сверху по одной перекладываются в правую руку, причем в правой руке они поочередно кладутся то сверху, то снизу тех карт, которые к этому моменту уже скопились в правой руке. Сколько раз нужно повторить такую перетасовку, чтобы в колоде был восстановлен первоначальный порядок?

12. Какое наименьшее число перегруппировок тридцати физкультурников (см. упр. 12 § 3) нужно осуществить, чтобы в шеренге был восстановлен начальный порядок? Какой ответ получится в случае, когда физкультурников 36?