Циклы перестановок

Исходная упорядоченная совокупность 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 1

- число перестановок циклового класса (k)

? Как найти число перестановок, имеющих единичных, двоичных и т.д.

1. Выберем произвольную перестановку класса (k) и переставим все элементы всеми возможными n! способами.

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

	I. Не отличаются с токи зрения циклового класса друг от друга все циклы, в которые входит одинаковое число одинаковых элементов.		II. Относительное расположение циклов несущественно (с точки зрения циклового класса).

I. С точки зрения циклового класса не отличаются друг от друга все циклы, в которые входит одинаковое число одинаковых элементов.

Т.к. цикл может начаться с любого из r входящих в него элементов, то можно получить r дубликатов этого цикла.

		r элементов r дубликатов

1 2 3 4 5 6

2 1 4 3 6 5

2

т.к.

Общее число дубликатов для перестановок

II. Относительное расположение циклов не существенно с точки зрения циклового класса

Если число циклов равно , то их можно переставить = Ч.Д. Г

Дата добавления: 2014-01-04