и что она подчиняется законам сокращения

п ja = тт JР влечет за собой а = /3, ajTT = /3 J7T влечет за собой а - (3.

Существует "единичный элемент"

aje - e-[a = a, (8)

где б - нуль-перестановка, "расположение в ряд" элементов пустого множества. Закон коммутативности, вообще говоря, не выполняется (см. упр. 2), тем не менее

Q т /5 = /3 т а, если Q и не содержат общих букв. (9)

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

{Xi Х2 ... Хп) (10)

перестановку, двухстрочное представление которой получается путем устойчивой сортировки столбцов

fxi Х2 ... л:,Л

\а;2 хз ... xi J по верхним элементам. Например,

(d Ь d d а с а а b d\ faaabbcdddd

{dbddacaabd) =

\bddacaabdd) \cabddabdad

так что перестановка (4) фактически является циклом. Мы могли бы описать этот цикл словесно, сказав что-нибудь наподобие "li переходит в Ь, переходит в d. переходит в d, переходит в ... переходит в d и возвращается обратно" Заметим, что эти обобщенные циклы не обладают всеми свойствами обычных циклов: {xi Х2 Хп) - необязательно то же самое, что и {х2 - XnXi). В рагзделе 1.3.3 мы выяснили, что каждую перестановку множества .можно единственны.м с точностью до порядка сомножителей образом представить в виде произведения непересекающихся циклов, где "произведение" перестановок определяется законом композиции. Легко видеть, что проязведенне непересекающялхя цлклов - то же самое, что их соединительное нроизведение; это наводит на мысль о том, что можно будет обобщить гюлученные ранее результаты, если найти единственное (в каком-то смысле) представление и для произвольной перестановки мультимножества в виде соединительного произведения циклов. В действительности существует, по крайней мере, два естественных способа сделать это, и каждый из них имеет важные приложения. Равенство (5) дает один способ представления cabddabdads виде соединительного произведения более коротких перестановок. Рассмотрим общую задачу о нахождении всех разложений к = ajP данной перестановки тт. Для этого полезно проанализировать конкретную перестановку, напри.мер

{а а Ь Ь Ь Ь Ь с с с d d d d d\ , .

(12)

7Г =

dbcbcacdaddbb b d

Если можно записать тг в виде ajf3, где а содержит, по крайней мере, одну букву а, то крайнее слева а в верхней строке двухстрочного представления а должно

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

fa Ь d d \

dd b "у

(13)

Продолжая рассуждать точно так же, обнаружим, что буква 6 в верхней строке (13) должна оказаться над с, и т. д. В конце концов, этот процесс вновь приведет нас к букве а, и мы сможем, если захотим, отождествить ее с первой буквой а. Такое рассуждение, по существу, доказывает, что любой левый сомножитель а в разложении перестановки (12), содержащий а, имеет вид {d d Ь с d b Ь с а) j а, где а - некоторая перестановка. (Удобно записывать а не в начале, а в конце цикла; это допустимо, поскольку буква а только одна.) Аналогично, если бы мы предположили, что а содержит букву 6, то вывели бы, что а = {с d d b)ja", где а" - некоторая перестановка. В общем случае эти рассуждения показывают, что если есть какое-нибудь разложение aj/3 = тг, где а содержит данную букву у, то существует единственный цикл вида

{х1...х„у), п > О, Х1,...,Хп7У, (14)

который является левым сомножителем в разложении перестановки а. Такой цикл легко отыскать, зная п и у; это самый короткий левый сомножитель в разложении перестановки тг, содержащий букву у. Из сказанного следует теорема.

Теорема А. Пусть элементы мультимножества М линейно упорядочены отношением "<" Каждая перестановка тг мультимножества М имеет единственное представление в виде соединительного произведения

Tr = ixu...Xinyi)j(X21...X2n:,y2)T--jixn---Xtn,yt), t>0, (15)

удовлетворяющее следующим двум условиям:

У1 <У2 < <yt и уг < Xij при 1 < J < ni, 1 <i<t. (16)

(Иными словами, в каждом цикле последний элемент меньше любого другого и последние элементы циклов образуют неубывающую последовательность.)

Доказательство. При тг = б получим требуемое разложение, положив t - 0. В противном случае пусть yi - минимальный элемент в тг; определим {хц .. .ximyi) - самый короткий левый сомножитель разложения тг, содержащий yi, как в рассмотренном примере. Теперь тг = {хц ... xi„ yi)jp, где р - некоторая перестановка; применив индукцию по длине перестановки, можем написать

р = {Х21 . . . Х2т У2) Т • • • Т {ХП Xtnt У*), t > 1,

где условия (16) вьшолнены. Тем самым доказано существование такого разложения.

Докажем единственность разложения (15), удовлетворяющего условиям (16). Ясно, что t = О тогда и только тогда, когда тг - нуль-перестановка е. При t > О из (16) следует, что ух - минимальный элемент перестановки и что {хц ... ххщ yi) - самый короткий левый сомножитель, содержащий ух. Поэтому {хц ...ainiVi) определяется однозначно; доказательство единственности такого представления завершается применением индукции и законов сокращения (7).

Например, "каноническое" разложение перестановки (12), удовлетворяющее данным условиям, таково:

{ddbcdbbca)j{bn)T{cdb)j{d), (17)

если а < b < с < d.

Важно отметить, что на самом деле в этом определении можно отбросить скобки и знаки операции j и это не приведет к неоднозначности! В конце каждого цикла появляется наименьший из оставшихся элементов. Таким образом, наше построение связывает с исходной перестановкой

K = dbcbcacdaddbbbd

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

TT = ddbcdbbcabacdbd.

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

Теорема В. Пусть М - мультимножество. Существует взаимно однозначное соответствие между перестановками М, такое, что если тг соответствует тг, то выполняются следующие условия:

a) крайний слева элемент тг равен крайнему слева элементу тг;

b) для всех пар участвующих в перестановке элементов {х,у), таких, что х < у, число вхождений столбца в двухстрочное представление перестановки тг равно числу случаев, когда в перестановке тг элемент х следует непосредственно за у.

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

П. А. Мак-Магон (Р. А. MacMahon) рассмотрел задачи этого типа в своей выдающейся книге Combinatory Analysis 1 (Cambridge Univ. Press, 1915), 168-186. Он дал конструктивное доказательство теоремы В в частном случае, когда М содержит элементы лишь двух различных типов, скажем а и Ь; его построение для этого случая, по существу, совпадает с приведенным здесь, но представлено в совершенно ином виде. Для случая трех различных элементов а, 6, с Мак-Магон дал сложное неконструктивное доказательство теоремы В; общий случай впервые доказал Фоата (Foata) [см. Comptes Rendus Acad. Sci. Paris 258 (1964), 1672-1675].