Перестановка - Permutation

Каждая из шести строк представляет собой перестановку трех разных шаров.

В математика, а перестановка из набор это, грубо говоря, объединение его членов в последовательность или линейный порядок, или, если набор уже заказан, перестановка его элементов. Слово «перестановка» также относится к действию или процессу изменения линейного порядка упорядоченного набора.^[1]

Перестановки отличаются от комбинации, которые являются выборками некоторых элементов набора независимо от порядка. Например, записывается как кортежи, существует шесть перестановок множества {1,2,3}, а именно: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) и (3,2,1). Это все возможные порядки этого трехэлементного набора. Анаграммы слов с разными буквами также являются перестановками: буквы уже упорядочены в исходном слове, а анаграмма - это перестановка букв. Изучение перестановок конечные множества это важная тема в области комбинаторика и теория групп.

Перестановки используются почти во всех областях математики и во многих других областях науки. В Информатика, они используются для анализа алгоритмы сортировки; в квантовая физика, для описания состояний частиц; И в биология, для описания РНК последовательности.

Количество перестановок п отдельные объекты п факториал, обычно пишется как п!, что означает произведение всех положительных целых чисел, меньших или равных п.

Технически перестановка набор S определяется как биекция от S себе.^[2][3] То есть это функция от S к S для которого каждый элемент встречается ровно один раз как образ ценность. Это связано с перестановкой элементов S в котором каждый элемент s заменяется на соответствующий ж(s). Например, указанная выше перестановка (3,1,2) описывается функцией ${ displaystyle alpha}$ определяется как:

${ Displaystyle альфа (1) = 3, четырехъядерный альфа (2) = 1, четырехъядерный альфа (3) = 2}$.

Совокупность всех перестановок множества образуют группа называется симметричная группа набора. Групповая операция - это сочинение (выполнение двух данных перегруппировок подряд), что приводит к другой перегруппировке. Поскольку свойства перестановок не зависят от природы элементов набора, часто это перестановки набора ${ Displaystyle {1,2, ldots, п }}$ которые рассматриваются для изучения перестановок.

В элементарной комбинаторике k-перестановки, или частичные перестановки, являются упорядоченными аранжировками k отдельные элементы, выбранные из набора. Когда k равно размеру набора, это перестановки набора.

В популярной головоломке Кубик Рубика изобретен в 1974 г. Эрне Рубик, каждый поворот граней головоломки создает перестановку цветов поверхности.

История

Перестановки называются гексаграммы использовались в Китае в И Цзин (Пиньинь: И Цзин) еще в 1000 г. до н.э.

Аль-Халиль (717–786), Арабский математик и криптограф написал Книга криптографических сообщений. Он содержит первое использование перестановки и комбинации, чтобы перечислить все возможные арабский слова с гласными и без них.^[4]

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

Произведением умножения начала и увеличения арифметического ряда на единицу и продолженного до количества знаков будут вариации числа с конкретными цифрами.^[5]

В 1677 г. Фабиан Стедман описал факториалы при объяснении количества перестановок колоколов в изменить звонок. Начиная с двух колоколов: «первый, два следует признать, что они меняются двояко », что он иллюстрирует, показывая 1 2 и 2 1.^[6] Затем он объясняет, что с тремя колокольчиками «из трех должно быть получено трижды по две фигурки», что снова проиллюстрировано. Его объяснение включает в себя «отбросьте 3, и 1.2 останется; отбросьте 2, и 1.3 останется; отбросьте 1, и 2.3 останется».^[7] Затем он переходит к четырем колокольчикам и повторяет аргумент отвержения, показывающий, что будет четыре разных набора из трех. По сути, это рекурсивный процесс. Он продолжает с пятью колокольчиками, используя метод «отбрасывания», и составляет итоговые 120 комбинаций.^[8] Здесь он сдается и замечает:

Природа этих методов такова, что изменения одного числа включают изменения всех меньших чисел ... до такой степени, что кажется, что полный Звук изменений одного числа формируется путем объединения завершенных Звонков на всех меньших числах. в одно целое тело;^[9]

Стедман расширяет рассмотрение перестановок; он продолжает рассматривать количество перестановок букв алфавита и лошадей из 20 конюшен.^[10]

Первый случай, когда, казалось бы, не связанные друг с другом математические вопросы изучались с помощью перестановок, произошел около 1770 года, когда Жозеф Луи Лагранж при изучении полиномиальных уравнений заметил, что свойства перестановок корни уравнения связаны с возможностями его решения. Это направление работы в конечном итоге привело к работе Эварист Галуа, в Теория Галуа, который дает полное описание того, что возможно и что невозможно в отношении решения полиномиальных уравнений (с одним неизвестным) радикалами. В современной математике существует множество подобных ситуаций, в которых понимание проблемы требует изучения определенных перестановок, связанных с ней.

Определение

В математических текстах принято обозначать перестановки строчными греческими буквами. Обычно либо ${ displaystyle alpha}$ и ${ displaystyle beta}$, или ${ displaystyle sigma, tau}$ и ${ displaystyle pi}$ используются.^[11]

Перестановки можно определить как биекции из множества S на себя. Все перестановки набора с п элементы образуют симметричная группа, обозначенный ${ displaystyle S_ {n}}$, где групповая операция является функциональная композиция. Таким образом, для двух перестановок ${ displaystyle pi}$ и ${ displaystyle sigma}$ в группе ${ displaystyle S_ {n}}$, выполняются четыре групповые аксиомы:

1. Закрытие: Если ${ displaystyle pi}$ и ${ displaystyle sigma}$ находятся в ${ displaystyle S_ {n}}$ тогда так ${ displaystyle pi sigma.}$
2. Ассоциативность: Для любых трех перестановок ${ Displaystyle пи, сигма, тау в S_ {п}}$, ${ Displaystyle ( пи сигма) тау = пи ( сигма тау).}$
3. Идентичность: Существует тождественная перестановка, обозначенная ${ displaystyle operatorname {id}}$ и определяется ${ displaystyle operatorname {id} (x) = x}$ для всех ${ displaystyle x in S}$. Для любого ${ Displaystyle sigma в S_ {п}}$, ${ displaystyle operatorname {id} sigma = sigma operatorname {id} = sigma.}$
4. Обратимость: Для каждой перестановки ${ displaystyle pi in S_ {n}}$, Существует ${ displaystyle pi ^ {- 1} in S_ {n}}$ так что ${ displaystyle pi pi ^ {- 1} = pi ^ {- 1} pi = operatorname {id}.}$

В общем, композиция двух перестановок не является коммутативный, это, ${ displaystyle pi sigma neq sigma pi.}$

Как биекция множества самому себе, перестановка - это функция, которая выполняет перестановка набора, а не перестановка сама по себе. Более старая и более элементарная точка зрения состоит в том, что перестановки - это сами перестановки. Чтобы различать эти два идентификатора, активный и пассивный иногда ставятся перед термином перестановка, тогда как в старой терминологии замены и перестановки используются.^[12]

Перестановка может быть разложена на одно или несколько непересекающихся циклы, это орбиты, которые находятся путем многократного отслеживания применения перестановки к некоторым элементам. Например, перестановка ${ displaystyle sigma}$ определяется ${ Displaystyle sigma (7) = 7}$ имеет 1 цикл, ${ Displaystyle (, 7 ,)}$ а перестановка ${ displaystyle pi}$ определяется ${ Displaystyle pi (2) = 3}$ и ${ Displaystyle pi (3) = 2}$ имеет 2 цикла ${ Displaystyle (, 2 , 3 ,)}$ (подробнее о синтаксисе см. § Обозначение цикла ниже). В общем, цикл длины k, то есть состоящий из k элементов, называется k-цикл.

Элемент в 1-цикле ${ Displaystyle (, х ,)}$ называется фиксированная точка перестановки. Перестановка без неподвижных точек называется психическое расстройство. 2-циклы называются транспозиции; такие перестановки просто меняют два элемента, оставляя остальные неизменными.

Обозначения

Поскольку запись перестановок поэлементно, то есть как кусочно функций, является громоздким, было изобретено несколько обозначений для их более компактного представления. Обозначение цикла является популярным выбором для многих математиков из-за его компактности и того факта, что он делает структуру перестановки прозрачной. Это обозначение, используемое в данной статье, если не указано иное, но другие обозначения все еще широко используются, особенно в прикладных областях.

Двухстрочная запись

В Коши с двухстрочная запись,^[13] один перечисляет элементы S в первом ряду, и для каждого свое изображение под ним во втором ряду. Например, конкретная перестановка множества S = {1,2,3,4,5} можно записать как:

${ displaystyle sigma = { begin {pmatrix} 1 & 2 & 3 & 4 & 5 2 & 5 & 4 & 3 & 1 end {pmatrix}};}$

это значит, что σ удовлетворяет σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3, и σ(5) = 1. Элементы S могут появляться в любом порядке в первой строке. Эту перестановку можно также записать как:

${ displaystyle sigma = { begin {pmatrix} 3 & 2 & 5 & 1 & 4 4 & 5 & 1 & 2 & 3 end {pmatrix}},}$

или

${ displaystyle sigma = { begin {pmatrix} 5 & 1 & 4 & 3 & 2 1 & 2 & 3 & 4 & 5 end {pmatrix}}.}$

Однострочное обозначение

Если есть «естественный» порядок элементов S,^[а] сказать ${ displaystyle x_ {1}, x_ {2}, ldots, x_ {n}}$, то это используется для первой строки двухстрочной записи:

${ displaystyle sigma = { begin {pmatrix} x_ {1} & x_ {2} & x_ {3} & cdots & x_ {n} sigma (x_ {1}) & sigma (x_ {2}) & sigma (x_ {3}) & cdots & sigma (x_ {n}) end {pmatrix}}.}$

В этом предположении можно опустить первую строку и записать перестановку в однострочная запись так как

${ Displaystyle ( sigma (x_ {1}) ; sigma (x_ {2}) ; sigma (x_ {3}) ; cdots ; sigma (x_ {n}))}$,

то есть упорядоченное расположение С.^[14][15] Следует проявлять осторожность, чтобы отличать однострочные обозначения от обозначение цикла описано ниже. В математической литературе принято опускать круглые скобки для однострочных обозначений и использовать их для обозначений циклов. Однострочную запись также называют слово представление перестановки.^[16] В приведенном выше примере будет 2 5 4 3 1, поскольку естественный порядок 1 2 3 4 5 будет принят для первой строки. (Обычно эти записи разделяются запятыми, только если некоторые из них состоят из двух или более цифр.) Эта форма более компактна и часто встречается в elementary комбинаторика и Информатика. Это особенно полезно в приложениях, где элементы S или перестановки должны сравниваться как больше или меньше.

Обозначение цикла

Обозначение цикла описывает эффект многократного применения перестановки к элементам набора. Он выражает перестановку как произведение циклы; поскольку различные циклы непересекающийся, это называется «разложением на непересекающиеся циклы».^[b]

Чтобы записать перестановку ${ displaystyle sigma}$ в обозначении цикла поступают следующим образом:

1. Напишите открывающую скобку, затем выберите произвольный элемент Икс из ${ displaystyle S}$ и запишите это: ${ Displaystyle (, х}$
2. Затем проследите орбиту Икс; то есть запишите его значения при последовательном применении ${ displaystyle sigma}$: ${ Displaystyle (, х , сигма (х) , сигма ( сигма (х)) , ldots}$
3. Повторяйте, пока значение не вернется к Икс и запишите закрывающую скобку, а не Икс: ${ Displaystyle (, х , сигма (х) , сигма ( сигма (х)) , ldots ,)}$
4. Теперь продолжаем с элементом у из S, еще не записано, и действуйте таким же образом: ${ Displaystyle (, х , сигма (х) , сигма ( сигма (х)) , ldots ,) (, у , ldots ,)}$
5. Повторяйте, пока все элементы S пишутся циклами.

Так как для каждого нового цикла начальная точка может быть выбрана по-разному, в целом существует множество различных обозначений цикла для одной и той же перестановки; в приведенном выше примере:

${ Displaystyle { begin {pmatrix} 1 & 2 & 3 & 4 & 5 2 & 5 & 4 & 3 & 1 end {pmatrix}} = (, 1 , 2 , 5 ,) (, 3 , 4 ,) = (, 3 , 4 ,) (, 1 , 2 , 5 ,) = (, 3 , 4 ,) (, 5 , 1 , 2 ,).}$

1-циклы часто опускаются из обозначения цикла, при условии ясности контекста; для любого элемента Икс в S не появляется ни в одном цикле, неявно предполагается ${ Displaystyle sigma (х) = х}$.^[17] В перестановка идентичности, состоящий только из 1-циклов, можно обозначить одним 1-циклом (x), цифрой 1,^[c] или по мне бы.^[18][19]

Удобная особенность обозначения цикла состоит в том, что можно найти инверсию перестановки, просто изменив порядок элементов в циклах перестановки. Например

${ Displaystyle [(, 1 , 2 , 5 ,) (, 3 , 4 ,)] ^ {- 1} = (, 5 , 2 , 1 ,) (, 4 , 3 ,)}$

Обозначение канонического цикла (a.k.a. стандартная форма)

В некоторых комбинаторных контекстах полезно зафиксировать определенный порядок элементов в циклах и самих (непересекающихся) циклов. Миклош Бона называет следующие варианты упорядочивания обозначение канонического цикла:

• в каждом цикле самый большой элемент указан первым
• циклы отсортированы по увеличение порядок их первого элемента

Например, (312) (54) (8) (976) - это перестановка в канонической записи цикла.^[20] Обозначение канонических циклов не исключает одноцикловых.

Ричард П. Стэнли называет тот же выбор представления «стандартным представлением» перестановки.^[21] и Мартин Айгнер использует термин «стандартная форма» для того же самого понятия.^[16] Сергей Китаев также использует терминологию «стандартной формы», но меняет оба варианта; то есть каждый цикл сначала перечисляет свой наименьший элемент, а циклы сортируются в порядке убывания их наименьшего элемента, то есть первых элементов.^[22]

Состав перестановок

Есть два способа обозначить композицию двух перестановок. ${ Displaystyle sigma cdot pi}$ это функция, которая отображает любой элемент Икс из набора ${ Displaystyle сигма ( пи (х))}$. К аргументу применяется самая правая перестановка,^[23]из-за способа написания приложения функции.

поскольку функциональная композиция является ассоциативный, как и операция композиции для перестановок: ${ Displaystyle ( сигма пи) тау = сигма ( пи тау)}$. Следовательно, произведения более двух перестановок обычно пишутся без добавления скобок для выражения группировки; они также обычно пишутся без точки или другого знака для обозначения композиции.

Некоторые авторы предпочитают, чтобы первым действовал крайний левый фактор,^[24][25][26]но для этого перестановки должны быть записаны в правильно аргумента, часто как показатель степени, где σ действующий на Икс написано Икс^σ; тогда продукт определяется как Икс^{σ · π} = (Икс^σ)^π. Однако это дает другой правило умножения перестановок; в этой статье используется определение, в котором сначала применяется самая правая перестановка.

Другое использование термина перестановка

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

k-перестановки п

Более слабое значение термина перестановка, иногда используемый в текстах по элементарной комбинаторике, обозначает те упорядоченные расположения, в которых ни один элемент не встречается более одного раза, но без требования использования всех элементов из данного набора. Это не перестановки, за исключением особых случаев, а естественные обобщения концепции упорядоченного расположения. Действительно, это использование часто включает в себя рассмотрение устройств фиксированной длины.k элементов, взятых из заданного набора размеров пдругими словами, эти k-перестановки п различные упорядоченные расположения k-элементное подмножество п-набор (иногда называют вариации или договоренности в более старой литературе^[d]). Эти объекты также известны как частичные перестановки или как последовательности без повторов, термины, которые избегают путаницы с другим, более распространенным значением слова «перестановка». Количество таких ${ displaystyle k}$-перестановки ${ displaystyle n}$ обозначается по-разному такими символами как ${ Displaystyle P_ {k} ^ {n}}$, ${ displaystyle _ {n} P_ {k}}$, ${ displaystyle ^ {n} P_ {k}}$, ${ displaystyle P_ {n, k}}$, или ${ Displaystyle P (п, к)}$, а его значение выражается произведением^[27]

${ Displaystyle P (п, к) = underbrace {п CDOT (п-1) CDOT (п-2) CDOTS (п-к + 1)} _ {к mathrm {факторы}}}$,

который равен 0, когда k > п, а в противном случае равно

${ displaystyle { frac {n!} {(n-k)!}}.}$

Продукт хорошо определен без предположения, что ${ displaystyle n}$ является целым неотрицательным числом и также имеет значение вне комбинаторики; он известен как Символ Поххаммера ${ Displaystyle (п) _ {к}}$ или как ${ displaystyle k}$-я падающая факторная мощность ${ displaystyle n ^ { underline {k}}}$ из ${ displaystyle n}$.

Это использование термина перестановка тесно связан с термином сочетание. А k-элементная комбинация п-набор S это k подмножество элементов S, элементы которых не заказываются. Взяв все k подмножества элементов S и упорядочивая каждую из них всеми возможными способами, получаем все k-перестановки S. Номер k-комбинации п-набор, C(п,k), поэтому связано с количеством k-перестановки п от:

${ displaystyle C (n, k) = { frac {P (n, k)} {P (k, k)}} = { frac { tfrac {n!} {(nk)!}} { tfrac {k!} {0!}}} = { frac {n!} {(nk)! , k!}}.}.}$

Эти числа также известны как биномиальные коэффициенты и обозначаются ${ Displaystyle { binom {п} {к}}}$.

Перестановки с повторением

Заказанные аранжировки п элементы набора S, где допускается повторение, называются п- пары. Иногда их называют перестановки с повторением, хотя в целом они не являются перестановками. Их еще называют слова по алфавиту S в некоторых контекстах. Если набор S имеет k элементов, количество п-конечники S является ${ displaystyle k ^ {n}.}$Нет ограничений на то, как часто элемент может появляться в п-tuple, но если наложены ограничения на частоту появления элемента, эта формула больше не действует.

Перестановки мультимножеств

Перестановки мультимножеств

Если M конечный мультимножество, потом перестановка мультимножества упорядоченное расположение элементов M в котором каждый элемент встречается столько раз, сколько его кратность в M. An анаграмма слова, имеющего несколько повторяющихся букв, является примером перестановки мультимножества.^[e] Если кратности элементов M (взяты в некотором порядке) ${ displaystyle m_ {1}}$, ${ displaystyle m_ {2}}$, ..., ${ displaystyle m_ {l}}$ и их сумма (то есть размер M) является п, то количество перестановок мультимножества M дается полиномиальный коэффициент,^[28]

${ displaystyle {n select m_ {1}, m_ {2}, ldots, m_ {l}} = { frac {n!} {m_ {1}! , m_ {2}! , cdots , m_ {l}!}} = { frac { left ( sum _ {i = 1} ^ {l} {m_ {i}} right)!} { prod _ {i = 1} ^ {l} {m_ {i}!}}}.}$

Например, количество различных анаграмм слова MISSISSIPPI составляет:^[29]

${ displaystyle { frac {11!} {1! , 4! , 4! , 2!}} = 34650}$.

А k-перестановка мультимножества M последовательность длины k элементов M в котором появляется каждый элемент в несколько раз меньше или равно его множественность в M (элемент номер повторения).

Круговые перестановки

Перестановки, если их рассматривать как аранжировки, иногда называют линейно упорядоченный договоренности. В этих механизмах есть первый элемент, второй элемент и так далее. Если, однако, объекты расположены по кругу, этого выделенного порядка больше не существует, то есть в расположении нет «первого элемента», любой элемент можно рассматривать как начало расположения. Расположение предметов по кругу называется круговые перестановки.^[30][f] Их можно формально определить как классы эквивалентности обычных перестановок объектов, для отношение эквивалентности генерируется перемещением последнего элемента линейной конструкции вперед.

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

     1           4   4   3       2   1     2           3

Круговое расположение следует читать против часовой стрелки, поэтому следующие два не эквивалентны, поскольку никакое вращение не может привести друг к другу.

     1          1   4   3      3   4     2          2

Количество круговых перестановок набора S с участием п элементы есть (п – 1)!.

Свойства

Количество перестановок п отдельные объекты п!.

Номер п-перестановки с k непересекающиеся циклы - это беззнаковый Число Стирлинга первого рода, обозначаемый c(п, k).^[31]

Тип перестановки

Циклы перестановки разбивают множество ${ displaystyle S_ {n}}$ поэтому длины циклов перестановки ${ displaystyle sigma}$ сформировать раздел из п называется тип цикла из ${ displaystyle sigma}$. В типе цикла есть «1» для каждой фиксированной точки σ, «2» для каждой транспозиции и так далее. Тип цикла ${ Displaystyle бета = (, 1 , 2 , 5 ,) (, 3 , 4 ,) (6 , 8 ,) (, 7 ,)}$ есть (3,2,2,1), который иногда в более компактной форме записывается как [1¹2²3¹].

Общая форма ${ displaystyle [1 ^ { alpha _ {1}} 2 ^ { alpha _ {2}} dotsm n ^ { alpha _ {n}}]}$, где ${ displaystyle alpha _ {1}, ldots, alpha _ {n}}$ - количество циклов соответствующей длины. Количество перестановок определенного типа равно^[32]

${ displaystyle { frac {n!} {1 ^ { alpha _ {1}} 2 ^ { alpha _ {2}} dotsm n ^ { alpha _ {n}} alpha _ {1}! alpha _ {2}! dotsm alpha _ {n}!}}}$.

Сопрягающие перестановки

В общем, составление перестановок, записанных в нотации цикла, не следует легко описываемому образцу - циклы композиции могут отличаться от составляемых. Однако структура цикла сохраняется в частном случае сопряжение перестановка ${ displaystyle sigma}$ другой перестановкой ${ displaystyle pi}$, что означает формирование продукта ${ displaystyle pi sigma pi ^ {- 1}}$. Вот, ${ displaystyle pi sigma pi ^ {- 1}}$ это сопрягать из ${ displaystyle sigma}$ и его обозначение цикла может быть получено, взяв обозначение цикла для ${ displaystyle sigma}$ и применяя ${ displaystyle pi}$ ко всем записям в нем.^[33] Отсюда следует, что две перестановки сопряжены именно тогда, когда они имеют один и тот же тип.

Порядок перестановки

Порядок перестановки ${ displaystyle sigma}$ это наименьшее положительное целое число м так что ${ Displaystyle sigma ^ {m} = mathrm {id}}$. Это наименьший общий множитель длины его циклов. Например, порядок ${ Displaystyle (, 1 , 3 , 2) (, 4 , 5 ,)}$ является ${ Displaystyle 2 cdot 3 = 6}$.

Четность перестановки

Каждую перестановку конечного множества можно выразить как произведение транспозиций.^[34]Хотя может существовать много таких выражений для данной перестановки, все они содержат четное или нечетное количество транспозиций. Таким образом, все перестановки можно классифицировать как четным или нечетным в зависимости от этого числа.

Этот результат можно расширить, присвоив знак, написано ${ displaystyle operatorname {sgn} sigma}$, к каждой перестановке. ${ displaystyle operatorname {sgn} sigma = + 1}$ если ${ displaystyle sigma}$ даже и ${ displaystyle operatorname {sgn} sigma = -1}$ если ${ displaystyle sigma}$ странно. Тогда для двух перестановок ${ displaystyle sigma}$ и ${ displaystyle pi}$

${ displaystyle operatorname {sgn} ( sigma pi) = operatorname {sgn} sigma cdot operatorname {sgn} pi.}$

Это следует из того ${ displaystyle operatorname {sgn} left ( sigma sigma ^ {- 1} right) = + 1.}$

Матричное представление

Составление перестановок соответствует умножению матриц перестановок.

Можно представить перестановку {1, 2, ..., п} как п×п матрица. Есть два естественных способа сделать это, но только один, для которого умножение матриц соответствует умножению перестановок в том же порядке: это тот, который ассоциируется с σ матрица M чья запись M_я,j равно 1, если я = σ(j) и 0 в противном случае. Результирующая матрица имеет ровно одну запись 1 в каждом столбце и в каждой строке и называется матрица перестановок.
Вот список этих матриц для перестановок 4 элементов. В Стол Кэли справа показаны эти матрицы для перестановок трех элементов.

Лемма Фоата о переходе

Между однострочным и каноническим циклическим обозначением существует взаимосвязь. Рассмотрим перестановку ${ Displaystyle (, 2 ,) (, 3 , 1 ,)}$, в канонической записи цикла, если мы удалим скобки цикла, мы получим перестановку ${ Displaystyle (2,3,1)}$ в однострочном обозначении. Foata лемма о переходе устанавливает природу этого соответствия как биекции на множестве п-перестановки (себе).^[35] Ричард П. Стэнли называет эту переписку фундаментальная биекция.^[21]

Позволять ${ displaystyle f}$ преобразование со стиранием скобок. Обратное ${ Displaystyle д = е (р)}$ немного менее интуитивно понятен. Начиная с однострочной записи ${ displaystyle q = q_ {1} q_ {2} cdots q_ {n}}$, первый цикл в канонической записи цикла должен начинаться с ${ displaystyle q_ {1}}$. Пока следующие элементы меньше, чем ${ displaystyle q_ {1}}$, мы находимся в одном цикле. Второй цикл начинается с наименьшего индекса ${ displaystyle j}$ такой, что ${ displaystyle q_ {j}> q_ {1}}$. Другими словами, ${ displaystyle q_ {j}}$ больше, чем все остальное слева от него, поэтому его называют максимум слева направо. Каждый цикл в канонической нотации цикла начинается с максимума слева направо.^[35]

Например, в однострочном обозначении ${ displaystyle (3,1,2,5,4,8,9,7,6)}$, 5 - первый элемент больше 3, поэтому первый цикл должен быть ${ Displaystyle (, 3 , 1 , 2 ,)}$. Тогда 8 - следующий элемент больше 5, поэтому второй цикл ${ Displaystyle (, 5 , 4 ,)}$. Поскольку 9 больше 8, ${ Displaystyle (, 8 ,)}$ сам по себе цикл. Наконец, 9 больше, чем все остальные элементы справа, поэтому последний цикл равен ${ Displaystyle (, 9 , 7 , 6 ,)}$.

Как первое следствие, количество n-перестановок с ровно k максимумы слева направо также равны беззнаковым Число Стирлинга первого рода, ${ Displaystyle с (п, к)}$. Кроме того, отображение Фоаты требует п-перестановка с k-слабые излишества п-перестановки с k − 1 восхождения.^[35] Например, (2) (31) = 321 имеет два слабых выхода (при индексах 1 и 2), тогда как ж(321) = 231 имеет одно восхождение (по индексу 1, то есть от 2 до 3).

Перестановки полностью упорядоченных множеств

В некоторых приложениях элементы переставляемого набора будут сравниваться друг с другом. Для этого необходимо, чтобы набор S имеет общий заказ чтобы можно было сравнить любые два элемента. Множество {1, 2, ..., п} полностью упорядочен обычным отношением «≤» и поэтому это наиболее часто используемый набор в этих приложениях, но в целом подойдет любой полностью упорядоченный набор. В этих приложениях вид упорядоченного расположения перестановки необходим, чтобы говорить о позиции в перестановке.

Есть ряд свойств, которые напрямую связаны с общим заказом S.

Подъемы, спуски, забеги и бега

An восхождение перестановкиσ из п любая позиция я < п где следующее значение больше текущего. То есть, если σ = σ₁σ₂...σ_п, тогда я это восхождение, если σ_я < σ_я+1.

Например, перестановка 3452167 имеет восхождения (в позициях) 1, 2, 5 и 6.

Аналогично спуск это позиция я < п с участием σ_я > σ_я+1так что каждый я с участием ${ Displaystyle 1 Leq я <п}$ либо восхождение, либо спускσ.

An восходящий бег перестановки - это непустая возрастающая непрерывная подпоследовательность перестановки, которая не может быть расширена ни на одном конце; он соответствует максимальной последовательности последовательных восхождений (последний может быть пустым: между двумя последовательными спусками еще есть восходящий пробег длиной 1). В отличие от возрастающая подпоследовательность перестановки не обязательно является смежным: это возрастающая последовательность элементов, полученная в результате перестановки путем исключения значений в некоторых позициях. Например, перестановка 2453167 имеет восходящие пробеги 245, 3 и 167, в то время как она имеет возрастающую подпоследовательность 2367.

Если в перестановке k - 1 спуск, значит это должно быть объединение k восходящие пробеги.^[36]

Количество перестановок п с участием k восхождения (по определению) Число Эйлера ${ displaystyle textstyle left langle {n atop k} right rangle}$; это также количество перестановок п с участием k спусков. Однако некоторые авторы определяют число Эйлера ${ displaystyle textstyle left langle {n atop k} right rangle}$ как количество перестановок с k восходящие пробеги, что соответствует k − 1 спусков.^[37]

Избыточность перестановки σ₁σ₂...σ_п это индекс j такой, что σ_j > j. Если неравенство не строгое (т.е. σ_j ≥ j), тогда j называется слабое превосходство. Номер п-перестановки с k excedances совпадает с количеством п-перестановки с k спусков.^[38]

Инверсии

в 15 головоломка цель состоит в том, чтобы расположить квадраты в порядке возрастания. Начальные позиции с нечетным числом инверсий решить невозможно.^[39]

An инверсия перестановкиσ пара (я,j) позиций, в которых элементы перестановки расположены в обратном порядке: я < j и σ_i > σ_j.^[40] Итак, спуск - это просто инверсия в двух соседних позициях. Например, перестановка σ = 23154 имеет три инверсии: (1,3), (2,3), (4,5) для пар элементов (2,1), (3,1), (5,4).

Иногда инверсия определяется как пара значений (σ_я,σ_j) сам, чей порядок обратный; это не имеет значения для количество инверсий, и эта пара (обратная) также является инверсией в указанном выше смысле для обратной перестановки σ⁻¹. Количество инверсий - важная мера того, в какой степени элементы перестановки неупорядочены; это то же самое для σ и для σ⁻¹. Чтобы привести перестановку с k инверсии в порядок (то есть преобразовать его в тождественную перестановку), последовательно применяя (правое умножение на) смежные транспозиции, всегда возможно и требует последовательности k такие операции. Более того, любой разумный выбор соседних транспозиций будет работать: достаточно выбрать на каждом шаге транспозицию я и я + 1 где я - это спуск перестановки, которая была изменена до сих пор (так что транспозиция удалит этот конкретный спуск, хотя может создать другие спуски). Это так, потому что применение такой перестановки уменьшает количество инверсий на 1; пока это число не равно нулю, перестановка не является тождеством, поэтому она имеет по крайней мере один спуск. Пузырьковая сортировка и вставка сортировки можно интерпретировать как отдельные экземпляры этой процедуры, чтобы упорядочить последовательность. Между прочим, эта процедура доказывает, что любая перестановка σ может быть записано как произведение смежных транспозиций; для этого можно просто обратить любую последовательность таких транспозиций, которая преобразует σ в личность. Фактически, перечисляя все последовательности смежных транспозиций, которые преобразовали бы σ в тождество, получаем (после обращения) полный список всех выражений минимальной длины записи σ как продукт смежных транспозиций.

Количество перестановок п с участием k инверсии выражаются числом Махона,^[41] это коэффициент Икс^k в расширении продукта

${ displaystyle prod _ {m = 1} ^ {n} sum _ {i = 0} ^ {m-1} X ^ {i} = 1 left (1 + X right) left (1+ X + X ^ {2} right) cdots left (1 + X + X ^ {2} + cdots + X ^ {n-1} right),}$

который также известен (с q заменен на Икс) как q-факториал [п]_q! . Расширение продукта появляется в Ожерелье (комбинаторика).

Перестановки в вычислениях

Нумерация перестановок

Один из способов представить перестановки п целым числом N с 0 ≤N < п!, при условии, что даны удобные методы для преобразования числа в представление перестановки в виде упорядоченного расположения (последовательности). Это дает наиболее компактное представление произвольных перестановок и особенно привлекательно в вычислениях, когда п достаточно мал, чтобы N может содержаться в машинном слове; для 32-битных слов это означает п ≤ 12, а для 64-битных слов это означает п ≤ 20. Преобразование может быть выполнено через промежуточную форму последовательности чисел. d_п, d_п−1, ..., d₂, d₁, где d_я неотрицательное целое число меньше, чем я (можно опустить d₁, поскольку он всегда равен 0, но его наличие облегчает описание последующего преобразования в перестановку). Тогда первый шаг - просто выразить N в факториальная система счисления, что является лишь частным смешанный корень представление, где для чисел до п! основания для последовательных цифр п, п − 1, ..., 2, 1. Второй шаг интерпретирует эту последовательность как Код Лемера или (почти то же самое) в виде инверсионной таблицы.

Диаграмма Роте для ${ Displaystyle sigma = (6,3,8,1,4,9,7,2,5)}$

σя я	1	2	3	4	5	6	7	8	9	Код Лемера
1	×	×	×	×	×	•				d9 = 5
2	×	×	•							d8 = 2
3	×	×		×	×		×	•		d7 = 5
4	•									d6 = 0
5		×		•						d5 = 1
6		×			×		×		•	d4 = 3
7		×			×		•			d3 = 2
8		•								d2 = 0
9					•					d1 = 0
Инверсионный стол	3	6	1	2	4	0	2	0	0

в Код Лемера для перестановкиσ, число d_п представляет выбор, сделанный для первого семестраσ₁, число d_п−1 представляет собой выбор, сделанный на второй срокσ₂ среди оставшихся п − 1 элементы набора и т. д. Точнее, каждый d_п+1−я дает количество остальной элементы строго меньше срока σ_я. Поскольку эти оставшиеся элементы обязательно появятся в качестве более позднего срока σ_j, цифра d_п+1−я считает инверсии (я,j) с привлечением я как меньший индекс (количество значений j для которого я < j и σ_я > σ_j). В инверсионный стол дляσ довольно похоже, но здесь d_п+1−k считает количество инверсий (я,j) где k = σ_j появляется как меньшее из двух значений, указанных в обратном порядке.^[42] Обе кодировки могут быть визуализированы п отп Диаграмма Роте^[43] (названный в честь Генрих Август Роте ), в котором точки на (я,σ_я) отметьте элементы перестановки и крестиком в (я,σ_j) отмечает инверсию (я,j); по определению инверсий крест появляется в любом квадрате, стоящем перед точкой (j,σ_j) в своем столбце и перед точкой (я,σ_я) в своем ряду. Код Лемера перечисляет количество крестов в последовательных строках, а таблица инверсии перечисляет количество крестов в последовательных столбцах; это просто код Лемера для обратной перестановки, и наоборот.

Чтобы эффективно преобразовать код Лемера d_п, d_п−1, ..., d₂, d₁ в перестановку упорядоченного множества S, можно начать со списка элементов S в порядке возрастания, а для я увеличивается с 1 до п набор σ_я к элементу в списке, которому предшествует d_п+1−я другие и удалите этот элемент из списка. Чтобы преобразовать инверсионную таблицу d_п, d_п−1, ..., d₂, d₁ в соответствующую перестановку, можно пройти числа из d₁ к d_п при вставке элементов S от наибольшего к наименьшему в изначально пустую последовательность; на шаге с помощью числа d из инверсионной таблицы элемент из S вставлен в последовательность в том месте, где ему предшествует d элементы уже присутствуют. В качестве альтернативы можно обрабатывать числа из таблицы инверсии и элементы S оба в обратном порядке, начиная с ряда п пустые слоты, и на каждом шаге размещаем элемент из S в пустой слот, которому предшествует d другие пустые слоты.

Преобразование последовательных натуральных чисел в факториальную систему счисления дает эти последовательности в лексикографический порядок (как и в случае с любой смешанной системой счисления с основанием системы счисления), и дальнейшее преобразование их в перестановки сохраняет лексикографический порядок при условии использования интерпретации кода Лемера (с использованием таблиц инверсии каждый получает другой порядок, где каждый начинает со сравнения перестановок по место их записей 1, а не значением их первых записей). Сумма чисел в представлении факториальной системы счисления дает количество инверсий перестановки, а четность этой суммы дает подпись перестановки. Более того, позиции нулей в таблице инверсии дают значения максимумов перестановки слева направо (в примере 6, 8, 9), а позиции нулей в коде Лемера - это позиции правого - минимумы слева (в примере позиционирует 4, 8, 9 значений 1, 2, 5); это позволяет вычислить распределение таких экстремумов среди всех перестановок. Перестановка с кодом Лемера d_п, d_п−1, ..., d₂, d₁ имеет восхождение п − я если и только если d_я ≥ d_{я + 1}.

Алгоритмы генерации перестановок

При вычислении может потребоваться сгенерировать перестановки заданной последовательности значений. Методы, лучше всего приспособленные для этого, зависят от того, нужны ли какие-то случайно выбранные перестановки или все перестановки, и, в последнем случае, требуется конкретный порядок. Другой вопрос: нужно ли учитывать возможное равенство записей в данной последовательности; если это так, следует только генерировать различные перестановки мультимножества последовательности.

Очевидный способ генерировать перестановки п заключается в генерации значений для Код Лемера (возможно, используя факториальная система счисления представление целых чисел до п!) и преобразовать их в соответствующие перестановки. Однако последний шаг, хотя и несложный, сложно реализовать эффективно, поскольку он требует п операции, каждая из которых - выбор из последовательности и удаление из нее в произвольной позиции; очевидных представлений последовательности в виде массив или связанный список, оба требуют (по разным причинам) около п²/ 4 операции для выполнения преобразования. С участием п вероятно, будет довольно маленьким (особенно если требуется генерация всех перестановок), что не является большой проблемой, но оказывается, что как для случайной, так и для систематической генерации есть простые альтернативы, которые работают значительно лучше. По этой причине не представляется полезным, хотя определенно возможным, использование специальной структуры данных, которая позволила бы выполнить преобразование из кода Лемера в перестановку в О(п журнал п) время.

Случайная генерация перестановок

Для создания случайные перестановки данной последовательности п значений, не имеет значения, применяется ли случайно выбранная перестановка п к последовательности, либо выбирает случайный элемент из набора различных (мультимножеств) перестановок последовательности. Это потому, что даже если в случае повторяющихся значений может быть много различных перестановок п которые приводят к одной и той же перестановочной последовательности, количество таких перестановок одинаково для каждого возможного результата. В отличие от систематической генерации, которая становится невозможной для больших п из-за роста числа п!, нет оснований предполагать, что п будет маленьким для случайной генерации.

Основная идея генерации случайной перестановки - это случайное генерирование одного из п! последовательности целых чисел d₁,d₂,...,d_п удовлетворение 0 ≤ d_я < я (поскольку d₁ всегда равен нулю, его можно опустить) и преобразовать его в перестановку через биективный переписка. Для последнего соответствия можно интерпретировать (обратную) последовательность как код Лемера, и это дает метод генерации, впервые опубликованный в 1938 г. Рональд Фишер и Фрэнк Йейтс.^[44]Хотя в то время компьютерная реализация не была проблемой, этот метод страдает от описанной выше трудности эффективного преобразования кода Лемера в перестановку. Это можно исправить, используя другое биективное соответствие: после использования d_я выбрать элемент среди я оставшиеся элементы последовательности (для уменьшения значений я), вместо того, чтобы удалять элемент и уплотнять последовательность, сдвигая вниз следующие элементы на одно место, одно свопы элемент с последним оставшимся элементом. Таким образом, элементы, оставшиеся для выбора, образуют последовательный диапазон в каждый момент времени, даже если они могут не появляться в том же порядке, что и в исходной последовательности. Преобразование последовательности целых чисел в перестановки несколько сложно, но можно увидеть, что каждая перестановка производится точно одним способом, путем немедленного индукция. Когда выбранный элемент оказывается последним оставшимся элементом, операцию обмена можно не выполнять. Это происходит не достаточно часто, чтобы гарантировать проверку условия, но последний элемент должен быть включен среди кандидатов в выборку, чтобы гарантировать, что все перестановки могут быть сгенерированы.

Результирующий алгоритм генерации случайной перестановки а[0], а[1], ..., а[п − 1] можно описать следующим образом в псевдокод:

для я от п вниз 2 делать    dя ← случайный элемент из {0, ..., я − 1 }    своп а[dя] и а[я − 1]

Это можно совместить с инициализацией массива а[я] = я следующим образом

для я от 0 к п−1 делать    dя+1 ← случайный элемент из {0, ..., я }    а[я] ← а[dя+1]    а[dя+1] ← я

Если d_я+1 = я, первое присвоение скопирует неинициализированное значение, но второе будет перезаписывать его правильным значением я.

Однако алгоритм Фишера-Йейтса не является самым быстрым алгоритмом для генерации перестановки, поскольку алгоритм Фишера-Йейтса по сути является последовательным алгоритмом, и процедуры «разделяй и властвуй» могут достичь того же результата параллельно.^[45]

Генерация в лексикографическом порядке

Есть много способов систематически генерировать все перестановки заданной последовательности.^[46]Один классический, простой и гибкий алгоритм основан на поиске следующей перестановки в лексикографический порядок, если он существует. Он может обрабатывать повторяющиеся значения, и в этом случае он генерирует каждую отдельную перестановку мультимножества один раз. Даже для обычных перестановок это значительно эффективнее, чем создание значений для кода Лемера в лексикографическом порядке (возможно, с использованием факториальная система счисления ) и преобразование их в перестановки. Он начинается с сортировки последовательности в (слабо) увеличение порядка (что дает его лексикографически минимальную перестановку), а затем повторяет переход к следующей перестановке, пока она будет найдена. Метод восходит к Нараяна Пандит в 14 веке в Индии, и его часто открывали заново.^[47]

Следующий алгоритм лексикографически генерирует следующую перестановку после данной перестановки. Он изменяет данную перестановку на месте.

1. Найдите самый большой индекс k такой, что а[k] < а[k + 1]. Если такого индекса не существует, перестановка является последней перестановкой.
2. Найдите самый большой индекс л больше k такое, что а[k] < а[л].
3. Поменять местами значение а[k] с тем из а[л].
4. Обратить последовательность из а[k + 1] до последнего элемента включительно а[п].

Например, учитывая последовательность [1, 2, 3, 4] (которая находится в порядке возрастания), и учитывая, что индекс равен с нуля, шаги следующие:

1. Показатель k = 2, потому что 3 помещается в индекс, удовлетворяющий условию наибольшего индекса, который все еще меньше а[k + 1], что равно 4.
2. Показатель л = 3, потому что 4 - единственное значение в последовательности, которое больше 3, чтобы удовлетворять условию а[k] < а[л].
3. Ценности а[2] и а[3] меняются местами, чтобы сформировать новую последовательность [1,2,4,3].
4. Последовательность после k-показатель а[2] в последний элемент перевернут. Поскольку только одно значение находится после этого индекса (3), последовательность в этом случае остается неизменной. Таким образом меняется лексикографический преемник начального состояния: [1,2,4,3].

Следуя этому алгоритму, следующая лексикографическая перестановка будет [1,3,2,4], а 24-я перестановка будет [4,3,2,1], и в этой точке а[k] < а[k + 1] не существует, что означает, что это последняя перестановка.

Этот метод использует около 3 сравнений и 1,5 перестановки на перестановку, амортизируемых по всей последовательности, не считая начальной сортировки.^[48]

Генерация с минимальными изменениями

В качестве альтернативы описанному выше алгоритму Алгоритм Штейнхауса – Джонсона – Троттера, генерирует упорядочение всех перестановок данной последовательности со свойством, что любые две последовательные перестановки в ее выходе отличаются заменой двух соседних значений. Такой порядок перестановок был известен английским звонарем 17-го века, среди которых он был известен как «простые изменения». Одним из преимуществ этого метода является то, что небольшое количество изменений от одной перестановки к другой позволяет реализовать метод за постоянное время на перестановку. То же самое может также легко сгенерировать подмножество четных перестановок, опять же за постоянное время на перестановку, пропуская все остальные перестановки вывода.^[47]

Альтернативой Steinhaus – Johnson – Trotter является Алгоритм кучи,^[49] сказал Роберт Седжвик в 1977 году - самый быстрый алгоритм генерации перестановок в приложениях.^[46]

На следующем рисунке показаны выходные данные всех трех вышеупомянутых алгоритмов для генерации всех перестановок длины. ${ displaystyle n = 4}$, и шести дополнительных алгоритмов, описанных в литературе.

Упорядочивание всех перестановок длины ${ displaystyle n = 4}$ генерируется разными алгоритмами. Перестановки обозначены цветом, где   1,   2,   3,   4.^[50]

1. Лексикографическая упорядоченность;
2. Алгоритм Штейнхауса – Джонсона – Троттера;
3. Алгоритм кучи;
4. Алгоритм перестановки звезды Эрлиха:^[47] на каждом шаге первая запись перестановки заменяется более поздней записью;
5. Алгоритм разворота префикса Закса:^[51] на каждом шаге префикс текущей перестановки переворачивается для получения следующей перестановки;
6. Алгоритм Савады-Вильямса:^[52] каждая перестановка отличается от предыдущей либо циклическим сдвигом влево на одну позицию, либо заменой первых двух записей;
7. Алгоритм Корбетта:^[53] каждая перестановка отличается от предыдущей циклическим сдвигом влево некоторого префикса на одну позицию;
8. Одноколейный заказ:^[54] каждый столбец представляет собой циклический сдвиг других столбцов;
9. Однодорожечный код Грея:^[54] каждый столбец представляет собой циклический сдвиг других столбцов, плюс любые две последовательные перестановки отличаются только одной или двумя перестановками.

Меандрические перестановки

Меандрические системы дать начало меандрические перестановки, специальное подмножество альтернативные перестановки. Альтернативная перестановка множества {1, 2, ..., 2п} это циклическая перестановка (без неподвижных точек), так что цифры в циклической форме записи чередуются между нечетными и четными целыми числами. Меандрические перестановки полезны при анализе вторичной структуры РНК. Не все альтернативные перестановки являются меандрическими. Была использована модификация алгоритма Хипа для генерации всех альтернативных перестановок порядка п (то есть длины 2п) без генерации всех (2п)! перестановки.^{[55][ненадежный источник? ]} Генерация этих альтернативных перестановок необходима до того, как они будут проанализированы, чтобы определить, являются ли они меандрическими или нет.

Алгоритм рекурсивный. В следующей таблице показаны этапы процедуры. На предыдущем шаге были сгенерированы все альтернативные перестановки длины 5. Три копии каждого из них имеют цифру «6», добавленную к правому концу, а затем применяется другое транспонирование, включающее эту последнюю запись, и предыдущую запись в четной позиции (включая идентичность, то есть без транспонирования).

Приложения

Перестановки используются в перемежитель компонент обнаружение и исправление ошибок алгоритмы, такие как турбокоды, Например Долгосрочное развитие 3GPP стандарт мобильной связи использует эти идеи (см. техническую спецификацию 3GPP 36.212^[56]В таких приложениях возникает вопрос о быстрой генерации перестановок, удовлетворяющих определенным желаемым свойствам. Один из методов основан на перестановочные многочлены. Также в качестве основы для оптимального хеширования при хешировании уникальной перестановки.^[57]

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

Заметки

использованная литература

Список используемой литературы

• Богарт, Кеннет П. (1990), Вводная комбинаторика (2-е изд.), Харкорт Брейс Йованович, ISBN  978-0-15-541576-8
• Бона, Миклош (2004), Комбинаторика перестановок, Чепмен Холл-CRC, ISBN  978-1-58488-434-7
• Бона, Миклош (2012), Комбинаторика перестановок (2-е изд.), CRC Press, ISBN  978-1-4398-5051-0
• Бруальди, Ричард А. (2010), Вводная комбинаторика (5-е изд.), Прентис-Холл, ISBN  978-0-13-602040-0
• Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы, Издательство Кембриджского университета, ISBN  978-0-521-45761-3
• Кармайкл, Роберт Д. (1956) [1937], Введение в теорию групп конечного порядка, Дувр, ISBN  978-0-486-60300-1
• Фрали, Джон Б. (1976), Первый курс абстрактной алгебры (2-е изд.), Литература: Эддисон-Уэсли, ISBN  0-201-01984-1
• Герштейн, Ларри Дж. (1987), Дискретная математика и алгебраические структуры, W.H. Фриман и Ко, ISBN  978-0-7167-1804-8
• Холл, Маршалл-младший. (1959), Теория групп, MacMillan
• Хамфрис, Дж. Ф. (1996), Курс теории групп, Издательство Оксфордского университета, ISBN  978-0-19-853459-4
• Кнут, Дональд (1973), Сортировка и поиск, Искусство программирования, 3 В этой книге код Лемера (без использования этого имени) упоминается как вариант C₁,...,C_п инверсионных таблиц в упражнении 5.1.1–7 (стр. 19) вместе с двумя другими вариантами.
• Кнут, Дональд (2005), Генерация всех кортежей и перестановок, Искусство программирования, 4, Эддисон – Уэсли, ISBN  978-0-201-85393-3 Буклет 2, первая печать.
• Маккой, Нил Х. (1968), Введение в современную алгебру, исправленное издание, Бостон: Аллин и Бэкон, LCCN  68015225
• Неринг, Эвар Д. (1970), Линейная алгебра и теория матриц (2-е изд.), Нью-Йорк: Wiley, LCCN  76091646
• Ротман, Джозеф Дж. (2002), Продвинутая современная алгебра, Прентис-Холл, ISBN  978-0-13-087868-7
• Стедман, Фабиан (1677), Campanalogia, Лондон Издатель указан как "W.S." который мог быть Уильямом Смитом, возможно, действующим как агент Общество молодежи колледжа, которому адресовано общество «Посвящение». В цитатах оригинальная длинная буква «S» была заменена современной короткой «s».
• Седьмой новый университетский словарь Вебстера, Спрингфилд: Компания G. & C. Merriam, 1969

дальнейшее чтение

• Биггс, Норман Л. (2002), Дискретная математика (2-е изд.), Oxford University Press, ISBN  978-0-19-850717-8
• Фоата, Доминик; Шутценбергер, Марсель-Поль (1970), Теория "Геометрика полиномов Эулериан", Конспект лекций по математике, 138, Берлин, Гейдельберг: Springer-Verlag, ISBN  978-3-540-04927-2. Ссылка ведет на свободно доступную перепечатанную (LaTeX'ed) и исправленную версию текста, первоначально опубликованную Springer-Verlag.
• Кнут, Дональд (1998), Сортировка и поиск, Искусство программирования, 3 (Второе изд.), Эддисон – Уэсли, ISBN  978-0-201-89685-5. Раздел 5.1: Комбинаторные свойства перестановок, стр. 11–72.
• Седжвик, Роберт (1977). «Методы генерации перестановок». Опросы ACM Computing. 9 (2): 137–164. Дои:10.1145/356689.356692. S2CID  12139332.

внешние ссылки

• «Перестановка», Энциклопедия математики, EMS Press, 2001 [1994]