Циклы и фиксированные точки - Cycles and fixed points

16 бит Код Грея перестановка грамм
умноженный с перестановка с обращением битов B

грамм имеет 2 фиксированные точки, 1 2-тактный и 3 4 цикла
B имеет 4 фиксированные точки и 6 2 цикла
ГБ имеет 2 фиксированные точки и 2 7 циклов

п * (1,2,3,4)^Т = (4,1,3,2)^Т

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

В математика, то циклы из перестановка π конечного набор S соответствовать биективно к орбиты подгруппы, порожденной π игра актеров на S. Эти орбиты подмножества из S что можно записать как {c₁, ..., c_л }, такие что

π(c_я) = c_{я + 1} за я = 1, ..., л - 1, и π(c_л) = c₁.

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

Размер л орбиты называется длиной соответствующего цикла; когда л = 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.а) Каждый цикл длины 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.а) Если мы хотим элемент 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 элемент.

Некоторые ценности

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

Значение ж(k, j) подсчитывает количество перестановок k элементы с точно j фиксированные точки. Основную статью по этой теме см. номера rencontres.

Характеристики

(1) Для каждого j <0 или j > k : ж(k, j) = 0.

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

(3) Для каждого k > 1 и k ≥ j ≥ 0, ж(k, j) = ж(k − 1, j − 1) + ж(k − 1, j)·(k − 1  − j) + ж(k − 1, j + 1)·(j + 1)

Причины свойств

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

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

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

(3.c) Мы можем выбрать один из ж(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 (k-i)!}$

Пример: ж(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} (k-i)!}$

Пример: ж(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 е (к, 0) = (к-1) (е (к-1,0) + е (к-2,0))}$

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

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

${ Displaystyle е (к, 0) = к! сумма _ {я = 2} ^ {к} (- 1) ^ {я} / я!}$

Пример: ж(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 е (к, 0) приблизительно к! / е}$

где е Число Эйлера ≈ 2.71828

Смотрите также

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

Примечания

Рекомендации

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