Введение
В математике циклы перестановки конечного множества S биективно соответствуют орбитам подгруппы, порожденной действием на S. Эти орбиты являются подмножествами S, которые могут быть записаны как {x₁, x₂, ..., xₙ}, так что для 1 ≤ i ≤ n, и соответствующий цикл записывается как (c₁ c₂ ... cₙ); это выражение не является единственным, так как c₁ может быть выбран в качестве любого элемента орбиты. Размер n орбиты называется длиной соответствующего цикла; когда n = 1, единственный элемент на орбите называется неподвижной точкой перестановки. Перестановка определяется заданием выражения для каждого из ее циклов, и одно из обозначений для перестановок состоит в записи таких выражений друг за другом в некотором порядке. Например, пусть будет перестановка, которая отображает 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 2 4 3)(6 8) является подходящим способом записи этой перестановки. Существуют различные способы записи перестановки в виде списка ее циклов, но число циклов и их содержимое определяется разбиением S на орбиты, и поэтому они одинаковы для всех таких выражений.
In mathematics, the cycles of a permutation of a finite set S correspond bijectively to the orbits of the subgroup generated by acting on S. These orbits are subsets of S that can be written as , such that
for 1=i = 1, , n − 1, and
The corresponding cycle of is written as ( c1 c2 cn ); this expression is not unique since c1 can be chosen to be any element of the orbit. The size n of the orbit is called the length of the corresponding cycle; when 1=n = 1, the single element in the orbit is called a fixed point of the permutation. A permutation is determined by giving an expression for each of its cycles, and one notation for permutations consist of writing such expressions one after another in some order. For example, let
be a permutation that maps 1 to 2, 6 to 8, etc. Then one may write
= ( 1 2 4 3 ) ( 5 ) ( 6 8 ) (7) = (7) ( 1 2 4 3 ) ( 6 8 ) ( 5 ) = ( 4 3 1 2 ) ( 8 6 ) ( 5 ) (7) =
Here 5 and 7 are fixed points of , since (5) = 5 and (7)=7. It is typical, but not necessary, to not write the cycles of length one in such an expression. Thus, = (1 2 4 3)(6 8), would be an appropriate way to express this permutation. There are different ways to write a permutation as a list of its cycles, but the number of cycles and their contents are given by the partition of S into orbits, and these are therefore the same for all such expressions.
Подсчет пермутаций по количеству циклов
Неподписанное число Стирлинга первого рода, s(k, j), подсчитывает количество перестановок из k элементов, имеющих ровно j непересекающихся циклов.
Подсчет пермутаций по количеству фиксированных точек
Значение 1=f(k, j) подсчитывает количество перестановок из k элементов, имеющих ровно j неподвижных точек. Подробная информация об этом приведена в статье о числах Ренконтра.
Альтернативные расчеты
Уравнения Примеры Для каждого k > 1: Для каждого k > 1: где e — число Эйлера ≈ 2.71828