AOP_Tom3 (1021738), страница 25

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 25)

Мы могли бы описать этот цикл словегно, сказав что-нибудь наподобие "г1 переходит в 6,переходит в 4, переходит в г1, переходит в ... переходит в И и возвращается обратно'. Заметим,что эти обобщенные циклы не обладают всеми свойствами обычных циклов: (хг хз... х,) необязательно то же самое, что н (хг...х„хг). В разделе 1.3.3 мы выяснилн, что каждую перестанонку множества можно единственным с точностью до порядка сомножителей образом представить в виде произведения непересекающихся циклов, где "произведение" перестановок определяется законом композиции.

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

Равенство (5) дает один способ представления с а 6 г1 д и 6 г1 а гг' в виде соединительного произведения более коротких перестановок. Рассмотрим общую задачу о нахождении всех разложений я = о т Д данной перестановки л. Для этого полезно проанализировать конкретную перестановку, например оказаться над д, значит, перестановка а должна содержать хотя бы одну букву Н.

Если взглянуть теперь на крайнее слева Н в верхней строке а, то можно точно так же увидеть, что оно должно оказаться над д; значит, в а должны содержаться, по меньшей мере, две буквы д. Посмотрев на второе д, видим, что а содержит также Ь. Единственное предположение о том, что а есть левый сомножитель я, содержащий букву о, приводит к такому промежуточному результату: о Ь Н Н (13) Продолжая рассуждать точно так же, обнаружим, что буква Ь в верхней строке (13) должна оказаться над с, и т. д. В конце концов, этот процесс вновь приведет нас к букве о, и мьг сможем, если захотим, отождествить ее с первой буквой а. Такое рассуждение, по существу, доказывает, что любой левый сомвожптель а в разложении перестановки (12), содержащий о, имеет вид (0 и ь с и ь ь с а) т а', где а' -- некоторая перестановка. (Ълобно записывать о не в начале, а в конце цикла; это допустимо, поскольку буква о только одна.) Аналогично, если бы мы предположили, что а содержит букву ь, то вывели бы, что а = (с ы и ь) та", где а" — некоторая перестановка.

В общем случае эти рассуждения показывают, что если есть какое-нибудь разложение а т,9 = я, где а содержит данную букву у, то существует единственный цикл вида (14) (хг ... х„у), п>0, х,,...,хяфу, который является левым сомножителем в разложении перестановки а. Такой цикл легко отыскать, зная я и у; это самый короткий левый сомножитель в разложении перестановки я, содержащий букву у. Из сказанного следует теорема. Теорема А.

Пусть элементы мультимножества М линейно упорядочены отношением "<". Каждая перестановка и мультпмножества М имеет единственное представление в виде соединительного произведения я = (хм... Хин уг) т (х21... хзязуз) т ' ' ' т (хгг ° хгп уг) ~ ~ 6 (16) удовлетворяющее следующим двум условиям; и у,<х,. при1<1<пн 1<1<6 (16) Уг < Уг « ..' Уг (Иными слонами, в каждом цикле последний элемент меньше любого другого и последние элементы циклов образуют неубывающую последовательность.) Доказательсгпео. При и = е получим требуемое разложение, положив 1 = О. В противном случае пусть уг — минимальный элемент в я; определим (хгг ...

хаги Уг)— самый короткий левый сомножитель разложения и, содержащий уы как в рассмотренном примере. Теперь я = (хм ... хим уг) т р., где р — некоторая перестановка; применив индукцию по длине перестановки, можем написать Р (ХМ Хзяэ У2) Т ' ' " Т (ХГГ ° ° ° 'Сви УГ) где условия (16) выполнены. Тем самым доказано существование такого разложения. Докажем единственность разложения (15), удовлетворяющего условиям (16). Ясно, что 1 = О тогда и только тогда, когда и — нуль-перестановка е.

При 6 > О из (16) следует, что у, —. минимальный элемент перестановки и что (хм ... х, ю 1гл)— самый короткий левый сомножнтель, содержащий ул. Поэтому (хы ... хом уг) определяется однозначно; доказательство единственности такого представления завершается применением индукции и законов сокращения (7). в Например, "каноническое" разложение перестановки (12), удовлетворяющее данным условиям, таково: (й г1 Ь с И Ь Ь с а) г (Ь а) т (с И 6) т (г(), (17) еслиа<Ь<с<й. Важно отметить„что на самом деле в этом определении можно отбросить скобки и знаки операции г и зто не приведет к неоднозначности! В конце каждого цикла появляется наименыпий из оставшихся элементов. Таким образом, наше построение связывает с исходной перестановкой т .= д 6 с 6 с а с а' а г1 г1 6 Ь 6 гл перестановку л' = г1 И Ь с а 6 Ь с а Ь а с г1 6 г1.

Если в двухстрочном представлении т содержится столбец вида,", где х < р, то в связанной с и' перестановке присутствует соответствующая пара соседних элементов ... у т.... Так, в нашем примере в содержит три столбца вида лл, трижды встречается пара а'6. Вообще, из этого построения вытекает замечательная теорема. Теорема В. Пугль М вЂ” мчльтпмножество. Существует взаимно однозначное соответствие лгежду перестановкалш ЛХ, такое, что если т соответствует и', то выполняются следующие условлгя: а) крайний слева элемент я' равен крайнему слева элементу г; Ь) для всех пар участвующих в перестановке элел~еггтов (х,у), таких, что х < у„ число вхождений столбца ~ ~в двухстрочное представление перестановки т равно числу случаев, когда в перестановке т'элемент х следует непосредственно за у. В Если М вЂ” множество, то это, по существу, "нестандартное соответствие", которое обсуждалось в конце раздела 1.3.3, с незначительными изменениями.

Более общий результат теоремы В полезен прн подсчете числа перестановок специальных типов, поскольку часто проще решить задачу с ограничениями, наложенными на двухстрочное представление, чем эквивалентную задачу с ограничениями на пары соседних элементов. П. А. Мак-Магон (Р. А. МасМаЬоп) рассмотрел задачи этого типа в своей выдающейся книге СошЬЬ1алогу Апа1угйв 1 (СаплЬП68е Пп1т. Ргевв, 1915), 168 — 186. Он дал конструктивное доказательство теоремы В в частном случае, когда М содержит элементы лишь двух различных типов, скажем а и 6: его построение для этого случая, по существу, совпадает с приведенным здесь, но представлено и совершенно ином виде.

Для случая трех различных элементов а, Ь, с Мак-Магон дал сложное неконструктивное доказательство теоремы В; общий случай впервые доказал Фоата (Гаага) (ель Сотргев йепг1ив АсасГ. Бо'. Раггв 258 (1964), 1672 — 1675!. В качестве нетривиального примера применения теоремы В найдем число строк букв а, Ь, с, содержащих ровно А вхождений буквы а; В вхождений буквы 6: С вхождений буквы г; Ь вхождений пары стоящих рядом букв са: вхождений пары стоящих рядом букв с6; т вхождений пары стоящих рядом букв Ьа. (> 8) Из теоремы следует, что это то же вида А самое, что найти число двухстрочных массивов Ь ... Ь « .

и В-1 Ь'э Се<э Буквы а можно расположить во второй строке способами. после этого буквы 6 можно разместить в оставшихся позициях <пособами. Остальные свободные места нужно заполнить буквами с; следовательно, искомое число равно (20) Вернемся к вопросу о нахождении всех разложений данной перестановки. Существует ли такой объект, как "простая" перестановка, которая не разлагается на множители, отличные от нее самой и с? Обсуждение, предшествующее теореме А, немедленно приводит к выводу о том, что нереста<<овна будет простой то<;та и только тогда, когда ояа являеэтя циклам без повторяюн<пхся элементов.

В случае, если перестановка является таким циклом< наше рассуждение доказывает, что не существует левых множителей, кроме е и самого цикла. Если же перестановка содержит повторяющийся элемент у, то в< егда можно выделить нетривиальный цикл в качестве левого сомножителя, в котором элемент у встречается всего лишь однажды.

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

Теорема С. Каждую перестановку мультнмножества можно записать в впдс произведения а'>тает" тггг, 1>б, (21) где и — циклы, нс содержащие повторягощпхгя элементов. Это представление единственное в том гэгысте, что два любых таюгх представлен>>я одной и той жс перестановки можно преобразовать одно я другое, последовательно меняя мсстамп соседние непересекающиеся циклы.

Термин "нспересекак>щиеся циклы" относится к циклам, не имеющим общих элементов. В качестве примера можно проверить, что перестановка 6 а а с г1 Ь с разлагается на множители ровно пятью способами: (а Ь) т (а) т (с гХ) т (Ь с) = (а Ь) т (с г1) т (а) т (Ь с) = (а 6) т (с В) т (Ь с) т (а) = (с И) т (а 6) т (Ь с) т (и) = (с г1) т (а Ь) т (а) т (6 с). (22) Доказательство. Нужно установить, что выполняется сформулированное в теореме свойство единственности. Применим индукцию по длине перестановки; тогда достаточно доказать, что если Р и гт — два различных цикла, не содержащих повторяющихся элементов, и Рта =птВ: то р и а — непересекающиеся циклы и а=птВ, В=ртВ, где  — некоторая перестановка.

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

Список файлов книги