Представление перестановок в циклической форме.

Во многих приложениях удобно представлять перестановки в циклической форме.

Пример. Разложение перестановки на циклы.

Пусть f=<5 7 3 1 6 4 2>=, тогда эту перестановку можно записать так

Представление f в виде циклов
1à5à6à4

2à7

Каждый цикл выписан на отдельной строчке. Внутри цикла следующим выписывается элемент перестановки, являющийся образом в f текущего, т. е. xàf(x). Образ последнего элемента совпадает с первым. В этом примере первым в каждом цикле выписан элемент с наименьшим номером внутри цикла, a циклы расположены в порядке возрастания первых элементов

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

Пусть перестановка f содержит k циклов следующего вида:

, для i=1,...,k,

Каждому такому циклу соответствует перестановка fi = [], называемая также циклом длины ni, которая определяется следующим образом:

fi()=,...,fi()=; fi(x)=x для xÏ {}.

Перестановку f можно представить в виде суперпозиции циклов

f = .

Например, f = <7 5 1 4 2 3 6>, тогда f = [1,7,6,3]×[2,5]×[4].

Замечание. 1. Элементы внутри одного цикла можно циклически переставлять местами.

Например: [1,7,6,3]=[7,6,3,1]=[6,3,1,7]=[3,1,7,6].

 

Теорема 1. Общее число циклов во всех n! перестановках

n-го порядка равно n!´Hn, где Hn=.

Доказательство. Пусть все n! перестановок записаны в циклической форме. Зафиксируем i, 1£i£n, и рассмотрим, сколько циклов длины i встречается во всех этих перестановках.

Заметим, что конкретный цикл [a1,...,ai] встречается в (n-i)! перестановках, так как это число способов, которыми можно переставить оставшиеся n-i элементов. Число различных возможных циклов [a1,...,ai] есть n´(n-1)´¼´(n-i)/i, так как элемент a1 можно выбрать n способами, элемента a2 - (n-1) способами и т. д.; а среди n´(n-1)´¼´(n-i+1) циклов из a1,...,ai фиксированных элементов появляется i раз, как [а1,...,аi], [a2,...,ai,a1],...,[ai,a1,...,ai-1]. Поэтому общее число циклов из i элементов во всех n! перестановках есть n´(n-1)´¼´(n-i+1)/i, взятое (n-i)! раз, т. е. n!/i.

Суммируя по всем i, получаем общее число циклов во всех n! перестановках =n!´Hn.

Определение. Будем говорить, что перестановка, представленная в виде разложения на циклы, находится в канонической форме, если:

а) обязательно записываются все циклы;

б) в каждом цикле первым записывается элемент с наименьшим значением;

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

Например, f=[3 1 6 7]×[5 4] представляется как [4 5]×[2]×[1 6 7 3].

Скобочная структура в канонической форме может быть опущена, так как первым элементам циклов соответствуют левосторонние минимумы ( ak, i£k£n, является левосторонним минимумом f, если ak<ai, 1£i<k).

В приведенном примере перестановка f может быть записана как (4 5 2 1 6 7 3), где круглые скобки указывают, что перестановка представлена в канонической циклической форме.

Упражнение. Пусть f=<a1 ... an>, g=(a1 ... an),n¹1. Докажите, что f¹g.

Рассмотрим производящую функцию Сn(t)=, определяющую число перестановок n-го порядка, имеющих k циклов, т. е. С(n,k) определяет число перестановок n-го порядка, имеющих k циклов. Тогда

C(0,0)=1,

C(n,0)=0, при n>0,

C(n,k)=0, при к>n,

Для n>0, C(n,k)=С(n-1,k-1)+(n-1)C(n-1,k) или Cn(t)=(t+n-1)Cn-1(t).

Докажем последнее утверждение.

Все ниже рассматриваемые перестановки представлены в канонической циклической форме. Заметим, что если максимальное число в такой перестановке расположено на первом месте, то оно образует отдельный цикл (так как оно является левосторонним минимумом и следующее за ним число также левосторонний минимум). Если же оно расположено на любом другом месте, то оно входит в какой-то цикл длины, большей единицы. Перестановка n-го порядка, содержащая k циклов, может быть получена либо добавлением n на первое место в перестановку (n-1)-го порядка, содержащую k-1 цикл, либо добавлением n в перестановку(n-1)-го порядка, содержащую k циклов, на любое место со второго до n-го.

Следствие. Учитывая, что C1(t)=t, получаем

Cn(t)=t(t+1)…(t+n-1).

 

Цикловые классы (типы).

Определение. Будем говорить, что перестановка PÎ{1,2,…,n} имеет тип <>, если P имеет k1 циклов длины 1, имеет k2 циклов длины 2, и т. д. Заметим, что = n.

Пусть С(k1, k2,…, kn) есть число перестановок из n элементов типа k=<>.

Выясним, какова формула, определяющее общее число таких перестановок. Для того чтобы найти эту формулу выберем произвольную перестановку типа k и переставим ее элементы всеми возможными n! способами. Имеется две причины, в силу которых не все получившиеся в результате этой операции перестановки оказываются различными: (а) все циклы, в которых входят одни и те же элементы в одном и том же циклическом порядке, не отличаются друг от друга; (b) относительное расположение циклов в перестановке несущественно.

Как уже отмечалось, r-цикл может начинаться с любого из входящих в него r элементов, и, следовательно, имеется возможность (в силу a) получить r дубликатов этого цикла. Общее число дубликатов составит . Далее, если число r-циклов равно kr, то их можно переставлять kr! способами, поэтому (в силу b) окажется дубликатов k1!· k2!·…· kn!.

Следовательно,

С(k1, k2,…, kn)=, где k1 +2k2+…+nkn=n. (1)

Примеры.

1. Шесть перестановок из трех элементов распадаются на три цикловых классов следующим образом:

тип перестановки число
<> (123); (132)
<> (12)(3); (13)(2); (1)(23)
<> (1)(2)(3)

2. Число перестановок типа <> равно n!/n= (n-1)!

Эта формула проверяется с помощью следующего соображения: в n-цикле первым элементом по условию является 1, а для расстановки оставшихся n-1 элементов существует (n-1)! возможностей.

3. Единственная перестановка типа <> совпадает с тождественной перестановкой.

 

Производящая функция чисел С(k1, k2,…, kn) должна иметь вид многочлена от многих переменных, так как n видов циклов должны независимыми. Этот факт выражается соотношением

Сn(t1, t2,…, tn)=ΣС(k1, k2,…, kn)

Следовательно, с учетом (1)

Сn(t1, t2,…, tn)= (2)

Сумма (2) берется по всем неотрицательным целым числам от k1 до kn таким, что k1 +2k2+…+nkn=n, или, что то же самое, по всем разбиением числа n. Функция Сn(t1, t2,…, tn) называется цикловым индикатором (указателем) симметрической группы.

Для первых значений n имеем:

С1(t1) =t1

С2(t1, t2)=+t2

С3(t1, t2, t3)=+3t1t2+2t3

С4(t1, t2, t3, t4)= +6t2+3+8t1t2+6t4

Удобно принять С0=1.

Из сопоставления соотношений (2) и (6) следует

Сn(t1, t2,…, tn)=An(1; t1, t2, 2! t3,…, (n-1)!tn)=

= Yn(t1, t2, 2! t3,…, (n-1)!tn) (3)

Последнее выражение является следствием соотношения (2а) при соответствующем изменении буквенных обозначений. В силу (5), это то самое, что и основное порождающее тождество:

exp(uC)= (t1, t2,…, tn)un/n!= exp(ut1+u2t2/2+u3t3/3+…) (3a)

весьма удобное для дальнейшей работы.

 

Свойства Сn(t1, t2,…, tn)

1. Сn(1, 1,…, 1)= n!

Это согласуется с (3а), так как

exp(ut1+u2t2/2+u3t3/3+…) =exp(log(1-u)-1 )=(1-u)-1 =1+u+u2+…

2. (тождество Коши)

следует из 1, учитывая (2)

3.Введенная ранее производящая функция числа перестановок n-го порядка Cn(t) может быть получена из Сn(t1, t2,…, tn), если все tr приравнять t, т.е.

Сn(t)=Сn(t, t,…, t)

Следовательно, из (3а) имеем

exp(uC(t))= = exp(t(u+u2/2+u3/3+…) = exp(t·log(1-u)-1=(1-u)-t=

=1+ (4)

что согласуется с ранее полученными результатами для Сn(t).