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-циклом
π ( c i ) = c i + 1 для i = 1, ..., n − 1 и π ( c n ) = c 1 .
Соответствующий цикл π записывается как ( c 1 c 2 ... c n ); это выражение не является единственным, поскольку c 1 может быть выбран в качестве любого элемента орбиты.
Размер 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] Таким образом, π = (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 неподвижными точками. Основную статью по этой теме см. в rencontres numbers .
Характеристики
(1) Для каждого j < 0 или j > k : f ( k , j ) = 0.
(2) ф (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 ( k − 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.
