8. Полное разложение на простые множители имеет вид (d) j {b с d) j (Ь) j {а d Ь с) j (а b) j {b с d) j (d); оно единственно, поскольку никакие два соседние сомножители не коммутируют. Таким образом, имеется восемь решений с а = е, (d), (d) j(bcd), ....

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

Пусть р ~ ст означает, что р коммутирует с ст. Следующее условие необходимо и достаточно для единственности разложения в указанном смысле:

р а ~ т и р -< (т т влечет за собой р т.

Доказательство. Если бы р ~ ст ~ г, р Ч ст Ч г и р / г, то существовало бы два разложения ajrjp = Tjpja; значит, условие необходимо. Обратно, для того чтобы показать, что оно достаточно для единственности, предположим, что pi j j рп = ffi j т <Тп - два различных разложения, удовлетворяющих условию. Можно считать, что cti -< pi и, следовательно, cti = рк для некоторых fc > 1; далее, cti ~ pj при 1 < j < fc. Поскольку Рк-1 ~ CTi = Рк, то рк-1 -< CTi; следовательно, fc > 2. Пусть j таково, что cti -< pj и pi -< cti при j < i < fc. Тогда из pj+\ ~ cti ~ pj и pj+i -< cti -< pj следует, что pj+i ~ pj; отсюда получается pj -< pj+i, a это - противоречие.

Таким образом, если на множестве простых перестановок S задано отношение порядка, удовлетворяющее указанному выше условию, и если известно, что все простые множители перестановки тг принадлежат 5, то можно заключить, что тг имеет единственное разложение указанного типа. Такое условие выполняется, например, когда 5 представляет собой множество циклов в (29).

Но множество всех простых перестановок нельзя упорядочить таким образом. Если, скажем, (а Ь) Ч (d е), то придется предположить, что

(а Ь) <{de)y (b с) Ч (е о) X (с d) Ч (а Ь) X (d е),

а это - противоречие. (См. также ахедующее упражнение.)

11. Наша цель - показать, что если р(1)... p{t) есть перестановка множества {1,...,(}, то перестановка Xpi)... Xpt) топологически рассортирована тогда и только тогда, когда Стр(1)т

• Tpi,t) = (Гц- jfTt, ч что если Xpji)... Xpjj) и 2;,(i)... Xqt) - различные топологические сортировки, то CTp(j) <Tq(j) при некотором j. Первое свойство следует из того, что Xpi) может быть первым в топологической сортировке тогда и только тогда, когда Стр(1) коммутирует с CTp(i) i,... ,cti (ho отлично от него), а из этого условия следует, что ар(2) т

• • КрСО = <7iT- • •TCTp(i) iTCTp(i)4.iT- • - jcrt и можно использовать индукцию. Второе свойство вытекает из того, что если j - наименьший индекс, при котором p{j) ф q{j) (пусть для определенности p{j) < q{j)), и справедливо Xpj) Xgj) по определению топологической сортировки, то CTp(j) не имеет общих букв с ст,().

Для того чтобы получить произвольное частичное упорядочение, положим, что цикл CTfc состоит из всех упорядоченных пар таких, что Xi -< Xj и либо i = fc, либо j = fc;

эти упорядоченные пары входят в цикл в произвольном порядке в качестве отдельных элементов цикла. Так, для частичного упорядочения xi Ч Х2, хз Ч Х4, xi ч Х4 циклы были бы следующими: cti = ((1, 2)(1,4)), стг = ((1,2)), стз = ((3,4)), Ст4 = ((1,4)(3,4)).

12. Никаких других циклов образовать нельзя хотя бы потому, что исходная перестановка не содержит столбцов ". Если (abed) встречается s раз, то цикл (а Ь) должен встретиться А - г - S раз, поскольку имеется всего А - г столбцов I и только два вида циклов вносят вклад в эти столбцы.

13. Используя двухстрочное представление, сначала поместите А - t столбцов вида f, затем - оставшиеся t букв а во вторую строку и буквы Ь, а также все остальные буквы.

14. Поскольку в двухстрочном представлении перестановки тг" элементы под любой буквой всегда располагаются в порядке неубывания, то не всегда выполняется равенство (7Г~)~ = 7Г, но всегда справедливо ((7Г~)~)~ = п~. При любых а и/3 имеет место тождество

(см. упр. 5-2).

Для данного мультимножества, все различные буквы которого суть xi < ••• < Хт, можно охарактеризовать все перестановки, обратные самим себе, приняв во внимание, что каждая из них имеет единственное разложение на простые множители вида /3i т • • • т Рт, где fij состоит из О или более простых множителей (xj) т • • т ij) т (xjXki) j -j (xjXk,), j < ki < < kt- Например, (a) j (a b) i (a b) j (b c) j (c) - перестановка, обратная самой себе. Следовательно, число обратных самим себе перестановок мультимножества {т - а, п- Ь} равно min(m, п) -Ь 1, а соответствующее число для {I- а, тп Ь, п с) есть число решений системы неравенств х + у<1, x + z<m, у + г<пв неотрицательных целых числах X, у, Z. Число обратных самим себе перестановок множества рассматривается в разделе 5.1.4.

Количество перестановок мультимножества (ni Х1,...,Пт • х„,), имеющих в своем двухстрочном представлении mj вхождений столбца р., есть fli Htj "и •• Столько же существует перестановок, в двухстрочной нотации которых содержится пу вхождений I.. Следовательно, должен существовать другой, лучший способ определения обратной перестановки мультимножества. Например, если разложение на простые множители мультимножества 7Г есть CTi JCT2 т • • , как в теореме С, можно определить тг" = ст" j • • • jo- тоГ j где (xi... х„)~ = {х„... Xl).

Доминик Фоата (Dominique Foata) и Гуо-Ню Хан (Guo-Niu Han) пришли к выводу, что было бы желательно определить обращение таким образом, чтобы тг и тг" имели равное число обращений, поскольку производящая функция для обращений, дающих числа n,j, есть Hi ni\z/Ylij иг (- УР- 1)- Однако, как нам кажется, не существует естественного способа определить инволюцию, обладающую таким свойством.

15. См. теорему 2.3.4.2D. После удаления одной дуги ориентированного графа должно оставаться ориентированное дерево.

16. Если Xl < Х2 < • • •, то элементы таблицы инверсий для разных Xj должны иметь вид bji < ••• < bjnj, где bjnj (число инверсий для крайнего справа элемента Xj) не больше, чем Hj+i -f- nj+2 -I- • • •. Таким образом, производящая функция для j-й части таблицы инверсий есть производящая функция для разбиений не более чем на щ частей, причем никакая часть не превосходит nj+i + nj+2 + • Производящая функция для разбиений не более чем на т частей, где никакая часть не превосходит п, равна г-номиальному коэффициенту {"m")z, что довольно просто доказывается по индукции; это также можно доказать с помощью одного из остроумных умозаключений, принадлежащих Ф. Франклину (F. Franklin) [см. Атег. J. Math. 5 (1882), 268-269; см. также Polya, Alexanderson, Elemente der Mathematik 26 (1971), 102-109]. Перемножив производящие функции при j = 1, 2, ... , можно получить искомую формулу для обращения перестановок мультимножеств, которую опубликовал Мак-Магон в Ргос. London Math. Soc. (2) 15 (1916), 314-321.

17. Пусть hniz) = (n!j)/Ti!, тогда желаемая вероятностная производящая функция имеет вид g{z) = hn (z)/hni {z)h„.2 i) " • Среднее от hn (z) равно (j) в соответствии с соотношением 5.1.1-(12), отсюда среднее значение для д равно

К0-("з)-(:)->1<"--"--=-)-5g»-

Аналогично дисперсия равна

(п(т1 - 1)(2т1 + 5) - niim - 1)(2т11 +5)----)

= i(n-n?-ni-...) + (n-n?-ni-...).

18. Да, верно. Построения из упр. 5.1.1-25 очевидным образом распространяются и на этот случай. Можно также обобщить доказательство, которое приведено в разделе 5.1.1-(14), построив взаимно однозначное соответствие между совокупностями т элементов (gii-.-igm), где Qj - мультимножество, которое содержит Uj неотрицательных целых чисел, с одной стороны, и упорядоченными парами совокупностей п элементов ((ai,..., а„), (pi,... ,Рп)), где 01... а„ - перестановка мультимножества {тц • 1,..., Пт т} и pi > • • > Рп > О, с другой стороны. Это соответствие, как и прежде, определяется путем назначения всем элементам Qj нижнего индекса j; оно удовлетворяет условию

S(gi) + • + S(gm) = ind(ai ... а„) + (pi + • +р„),

где S(gj) означает сумму элементов мультимножества Qj. [Дальнейшее обобщение методики, использованной в этом доказательстве и выводе соотношения 5.1.3-(8), приводится в работе D. Е. Knuth, Math. Сотр. 24 (1970), 955-961. См. также исчерпывающее исследование Richard Р. Stanley, Memoirs Amer. Math. Soc. 119 (1972).]

19. (a) Пусть S = {ct I a - простая перестановка, ст - левый множитель в разложении тг}. Если S состоит из к элементов, то левые множители А в разложении перестановки тг такие, что р{Х) ф О есть не что иное, как ровно 2* соединительных произведений подмножеств множества S (см. доказательство теоремы С); следовательно, ХА(А) = Ylesif)) ~ > следовательно, р{(т) = -1 и S непусто. (Ь) Ясно, что e{ii... in) = pi) = О, если ij = ik при некотором j ф к. В противном случае e{ii... г„) = (-1), где ii ... г„ имеет г инверсий; это ровно (-1), где s - число четных циклов перестановки ii ... in, что, в свою очередь, равно (-1)""*", где t - число циклов перестановки h ... г„.

20. (а) Соотношение, очевидно, следует из определения соединительного произведения. (Ь) По определению

det(bij) = €(n ...im)blii .-.bmi™.

l<it,...,tm<m

Полагая bij = 6ij - aijXj и применяя результат упр. 19, (b), получим

Xii...Xi„p{Xi...Xi„)lixi...Xi„),

я>0 l<ii ,...,in <m

поскольку (тг), как правило, равно нулю.

(с) Используйте результат упр. 19, (а) и покажите, что DjG = l, если рассматривать произведения всевозможных элементов х как перестановки некоммутативных переменных, учитывая естественное алгебраическое соглашение {а + 0)тк = атк + рк.

Сжатое толкование этого комбинаторного доказательства и похожие доказательства других важных теорем даны Д. Зильбергером [D. Zeilberger, Discrete Math. 56 (1985), 61-72].

21- ПГ=1 (""""nt"") если положить ПА, = О при < О, поскольку существует {""nt"") способов вставить элементы т в такую перестановку мультимножества {щ 1,..., Пт-i • (т-1)}.

22. (а) Перестановка слева направо 1{п) существует в Ро(0*1" .. .t") для некоторого fc; но вместо перестановки 1{п) рассмотрим ее двухстрочное представление, в котором О размещен последним, а не первым в верхней строке. Число к элементов О в 1{п) и г(7г) равно числу столбцов в двухстрочном представлении тг, для которых j < t < к; это также