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

16-битная перестановка кода Грея G,
умноженная на перестановку B с инверсией битов,

G имеет 2 фиксированные точки, 1 2-цикл и 3 4-цикла
B имеет 4 фиксированные точки, а 6 2-тактных
GB имеет 2 фиксированные точки и 2 7-цикла

P * (1,2,3,4) ^T = (4,1,3,2) ^T

Перестановка четырех элементов с 1 фиксированной точкой и 1 3-циклом

В математике , то циклы из более перестановок П конечного множества S соответствуют уплотняется к орбитам подгруппы , порожденной л , действующим на S . Эти орбиты являются подмножествами из S , которые могут быть записаны как {  C ₁ , ...,  гр _л  }, что

π ( c _i ) = c _{i + 1} для i = 1, ..., l  - 1 и π ( c _l ) = c ₁ .

Соответствующий цикл π записывается как ( c ₁ c ₂ ... c _n ); это выражение не уникально, так как c ₁ может быть выбран как любой элемент орбиты.

Размер орбиты l называется длиной соответствующего цикла; когда l  = 1, единственный элемент на орбите называется фиксированной точкой перестановки.

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

${\ displaystyle \ pi = {\ begin {pmatrix} 1 & 6 & 7 & 2 & 5 & 4 & 8 & 3 \\ 2 & 8 & 7 & 4 & 5 & 3 & 6 & 1 \ end {pmatrix}} = {\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 4 & 1 & 3 & 5 & end 8 & 7 & pmatrix \ end 8 & 7 & pmatrix$

- перестановка, отображающая 1 в 2, 6 в 8 и т. д. Тогда можно написать

π = (1 2 4 3) (5) (6 8) (7) = (7) (1 2 4 3) (6 8) (5) = (4 3 1 2) (8 6) (5) ( 7) = ...

Здесь 5 и 7 - неподвижные точки π , поскольку π (5) = 5 и π (7) = 7. Типично, но не обязательно, в таком выражении не записывать циклы длины один. ^[1] Таким образом, π = (1 2 4 3) (6 8) было бы подходящим способом выразить эту перестановку.

Существуют различные способы , чтобы написать перестановку в виде списка своих циклов, но число циклов и их содержание приведены в разделе о S на орбиты, и они, следовательно , одинаково для всех таких выражений.

Подсчет перестановок по количеству циклов [ править ]

Беззнаковое число Стирлинга первого рода s ( k ,  j ) подсчитывает количество перестановок k элементов ровно с j непересекающимися циклами. ^{[2] [3]}

Свойства [ править ]

(1) Для любого k > 0: s ( k ,  k ) = 1.

(2) Для любого k > 0: s ( k , 1) = ( k  - 1) !.

(3) Для любого k > j > 1 s ( k ,  j ) = s ( k  - 1, j  - 1) +  s ( k  - 1,  j ) · ( k  - 1)

Причины для свойств [ править ]

(1) Есть только один способ построить перестановку k элементов с k циклами: каждый цикл должен иметь длину 1, поэтому каждый элемент должен быть фиксированной точкой.

(2.a) Каждый цикл длины k можно записать как перестановку числа 1 в k ; есть k ! этих перестановок.

(2.b) Существует k различных способов записать данный цикл длины k , например (1 2 4 3) = (2 4 3 1) = (4 3 1 2) = (3 1 2 4).

(2.c) Наконец: s ( k , 1) = k ! / K = ( k  - 1) !.

(3) Есть два разных способа построить перестановку из k элементов с j циклами:

(3.a) Если мы хотим, чтобы элемент k был фиксированной точкой, мы можем выбрать одну из s ( k  - 1,  j  - 1) перестановок с k  - 1 элементами и j  - 1 циклами и добавить элемент k как новый цикл длиной 1.

(3.b) Если мы хотим, чтобы элемент k не был фиксированной точкой, мы можем выбрать одну из s ( k  - 1,  j ) перестановок с k  - 1 элементами и j циклами и вставить элемент k в существующий цикл перед один из k  - 1 элементов.

Некоторые значения [ править ]

Подсчет перестановок по количеству фиксированных точек [ править ]

Значение f ( k ,  j ) подсчитывает количество перестановок k элементов с ровно j неподвижными точками. Для основной статьи по этой теме см. Номера контактов .

Свойства [ править ]

(1) Для любого j <0 или j > k  : f ( k ,  j ) = 0.

(2) f (0, 0) = 1.

(3) Для любого k > 1 и k ≥ j ≥ 0 f ( k ,  j ) = f ( k  - 1,  j  - 1) + f ( k  - 1,  j ) · ( k  - 1 -  j ) + f ( к  - 1,  j  + 1) · ( j  + 1)

Причины для свойств [ править ]

(3) Существует три различных метода построения перестановки из k элементов с j неподвижными точками:

(3.a) Мы можем выбрать одну из  перестановок f ( k  - 1,  j - 1) с k  - 1 элементами и j  - 1 фиксированной точкой и добавить элемент k в качестве новой фиксированной точки.

(3.b) Мы можем выбрать одну из перестановок f ( k  - 1,  j ) с k  - 1 элементами и j неподвижными точками и вставить элемент k в существующий цикл длины> 1 перед одним из ( k  - 1) -  j элементов.

(3.c) Мы можем выбрать одну из  перестановок f ( k  - 1,  j + 1) с k  - 1 элементом и j  + 1 неподвижными точками и присоединить элемент k с одной из j  + 1 неподвижных точек к циклу длина 2.

Некоторые значения [ править ]

Альтернативные вычисления [ править ]

${\ displaystyle f (k, 1) = \ sum _ {i = 1} ^ {k} (- 1) ^ {i + 1} {k \ choose i} i (ki)!}$

Пример: f (5, 1) = 5 × 1 × 4! - 10 × 2 × 3! + 10 × 3 × 2! - 5 × 4 × 1! + 1 × 5 × 0!

= 120 - 120 + 60 - 20 + 5 = 45.

${\ displaystyle f (k, 0) = k! - \ sum _ {i = 1} ^ {k} (- 1) ^ {i + 1} {k \ choose i} (ki)!}$

Пример: f (5, 0) = 120 - (5 × 4! - 10 × 3! + 10 × 2! - 5 × 1! + 1 × 0!)

= 120 - (120-60 + 20-5 + 1) = 120-76 = 44.

Для каждого k > 1:

${\displaystyle f(k,0)=(k-1)(f(k-1,0)+f(k-2,0))}$

Пример: f (5, 0) = 4 × (9 + 2) = 4 × 11 = 44.

Для каждого k > 1:

${\displaystyle f(k,0)=k!\sum _{i=2}^{k}(-1)^{i}/i!}$

Пример: f (5, 0) = 120 × (1/2 - 1/6 + 1/24 - 1/120).

= 120 × (60/120 - 20/120 + 5/120 - 1/120) = 120 × 44/120 = 44

${\displaystyle f(k,0)\approx k!/e}$

где e - число Эйлера ≈ 2,71828

См. Также [ править ]

• Циклическая перестановка
• Обозначение цикла

Заметки [ править ]

Ссылки [ править ]

• Бруальди, Ричард А. (2010), Вводная комбинаторика (5-е изд.), Прентис-Холл, ISBN 978-0-13-602040-0
• Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы , Cambridge University Press, ISBN 0-521-45761-0
• Герштейн, Ларри Дж. (1987), Дискретная математика и алгебраические структуры , WH Freeman and Co., ISBN 0-7167-1804-9