5.8. Циклы перестановок
Исходная упорядоченная совокупность n элементов. Воздействуем на нее оператором.
( 1 2 3 4 5 )
( 2 5 4 3 1 )
Воздействие оператора представим записью
(1, 2, 5) (3, 4)
Это означает 1 2 3 4
2 5 4 3
5 1
Последовательность связанных между собой переходов называется циклом.
Циклы, содержащие один элемент называются единичными. Циклы, содержащие два элемента - двоичными. Три – троичными, и т.д.
Перестановка может быть содержать
единичных
циклов
двоичных
циклов
троичных
циклов
…
n-ичных
циклов
Совокупность
чисел
определяют цикловой класс (или просто
класс)
связь
с числом n
Для нашего примера имеем:
1
-
число перестановок циклового класса
(k)
? Как найти число перестановок, имеющих единичных, двоичных и т.д.
Выберем произвольную перестановку класса (k) и переставим все элементы всеми возможными n! способами.
Д
ве
причины, в силу которых не все получившиеся
в результате этой операции перестановки
оказываются различными.
I.
Не отличаются с токи зрения циклового
класса друг от друга все циклы, в которые
входит одинаковое число одинаковых
элементов.
II.
Относительное располо-жение циклов
несуществен-но (с точки зрения циклово-го
класса).
С точки зрения циклового класса не отличаются друг от друга все циклы, в которые входит одинаковое число одинаковых элементов.
Т. к. цикл может начаться с любого из r входящих в него элементов, то можно получить r дубликатов этого цикла.
4
3
r
элементов
r
дубликатов
2
1
2 3 4 5 6
5
2 1 4 3 6 5
1
6
т.к.
Общее
число дубликатов для перестановок
Относительное расположение циклов не существенно с точки зрения циклового класса
Если
число циклов равно
,
то их можно переставить
= Ч.Д. Г
Общее число дубликатов
где
,
следовательно
1 2 3 4 5 6
2 1 4 3 6 5
1 3 5
2 4 6
Относительно первого фактора:
Имеем
Общее количество
дубликатов для перестановок
Относительно расположения циклов общее количество дубликатов
Т.е. из «3-х» переставить «3»
Общее количество перестановок будет
Пример. Разобьем на цикловые классы перестановки из 3-х элементов.
1
,2,3 
(1)
(2) (3) ***
Цикл. класс (3,0,0)
1
Цикл. класс (1,1,0)
,3,2 
(1),
(2,3) **
3
,2,1 
(1,3),
(2) **
2
,1,3 
(1,2),
(3) **
3
Цикл. класс (0,0,1)
,1,2 
(1,3,2)
*
2
,3,1 
(1,2,3)
*
*
(3*1=3)
**
(1+2*1=3)
***
(3*1+2*0+3*0=3)