за (с d), а {b с) не встречается сразу после {d а). Отсюда, используя результат упр. 13, получаем тождество

Е/Б\/ A-q~s \B + D-r-s-t\ [t jKA-r-s-tJK B-q-s )

{D - r -s)\ {A - q - s)\ s\ {q - A + r + s)\

Вынося из обеих частей множитель (л,) и несколько упрощая факториалы, приходим к сложному на вид пятипараметрическому тождеству биномиальных коэффициентов:

/B\/A-r-t\/B + D-r-s-t\D-A + q\/ A-q \ \t)\ s )\ D + q-r-t )\ D-r-s )\r + t-q)

B\fA-r-t\fB + D-r-s-t\fD-A + q\f A-q

A\ {B + D-A\ (B

Пспатьзуя тождество (27), можно выполнить суммирование по s, а затем легко вычислить получившуюся сумму по t. Таким образом, выполнив всю работу, мы не смогли обнаружить какое-либо тождество, которое мы бы еще не умели выводить. Но мы, по крайней мере, научились подсчитывать число перестановок определенного вида двумя различными способами, а эти методы подсчета - хорошая подготовка к решению задач, которые еще ждут нас впереди.

УПРАЖНЕНИЯ

1. [М05] Да или нет? Пусть Mi и Мг - мультимножества. Если а - перестановка Ml, а Р - перестановка Мг, то ау/З - перестановка Mi UM2.

2. [10] Соединительное произведение перестановок cadabnbddad представлено в (5); найдите соединительное произведение Ъ d d а d т с а d а Ъ, которое получается, если сомножители поменять местами.

3. [М13] Верно ли утверждение, обратное (9)? Иначе говоря, если перестановки а и 3 коммутативны относительно операции соединительного произведения, то следует ли из этого, что они не содержат общих букв?

4. [МП] Каноническое разложение перестановки (12) в соответствии с теоремой А при а < b < с < d задается формулой (17). Найдите каноническое разложение в случае, когда d < с <Ь < а.

5. [М23] В условии (Ь) теоремы В требуется, чтобы х было меньше у. Что будет, если ослабить это требование, заменив его требованием х < у?

6. [М15] Сколько существует цепочек, состоящих ровно из тп букв а и п букв Ь, таких, что ровно к букв b стоят непосредственно перед буквами а и нет никаких других букв, кроме а и Ь?

7. [М21] Сколько строк из букв а, Ь, с, удовлетворяющих условиям (18), начинаются с буквы а, с буквы Ь, с буквы с?

► 8. [20] Найдите все разложения перестановки (12) на два множителя а т/3.

9. [33] Напишите программы, которые формировали бы разложения заданной перестановки мультимножества, описанные в теоремах А и С.

► 10. [МЗО] Да или нет? Согласно теореме С разложение на простые множители не вполне однозначно, тем не менее можно следующим образом обеспечить единственность. "Существует линейное упорядочение Ч на множестве простых перестановок, такое, что каждая перестановка мультимножества имеет единственное разложение ffi т <72 т Т <7n на простые множители, удовлетворяющее условию ст; Ч at+i, если ffi коммутирует с ffi+i при 1 < г < п"

► 11. [М26] Пусть (71, (72, .., (7t - циклы без повторяющихся элементов. Определим частичное упорядочение -< на множестве t элементов {xi,... , xt}, полагая Xi Ч Xj, если г < j и (7, имеет, по крайней мере, одну общую букву с aj. Докажите следующую связь между теоремой С и понятием "топологическая сортировка" (раздел 2.2.3): число различных разложений перестановки сгпсг2т -jCt на простые множители равно количеству способов топологической сортировки данного частичного упорядочения. (Например, в соответствии с (22) существует пять способов топологической сортировки упорядочения ii Ч жг, жз Ч Х4, XI -< Ж4.) Обратно, если на множестве из t элементов задано какое-либо частичное упорядочение, то существует множество циклов {(7i, (72,. .., (7t}, которое определяет это частичное упорядочение указанным способом.

12. [М16] Покажите, что (29) есть следствие, вытекающее из предположения (28).

13. [М21] Докажите, что число перестановок мультимножества

{А а, В Ь, С с, D d, Е е, F f} ,

не содержащих пар стоящих рядом букв са и db, равно

Е/ D \ fA + B + E + F\ fA + B + C + E + F-t\ fC + D + E + F\ U-J I t A В A C,D,E,F )

14. [M30] Один из способов определить перестановку тг", обратную перестановке тг, который подсказан нам в других определениях этого раздела, - поменять местами строки двухстрочного Представления тг и так выполнить устойчивую сортировку столбцов, чтобы элементы верхней строки расположились в порядке неубывания. Например, если а < b < с < d, то из этого определения следует, что обратной перестановкой Kcabddabdad будет acdadabbdd.

Исследуйте свойства этой операции обращения; имеется ли, например, какая-нибудь простая связь между данной операцией и соединительным произведением? Можно ли подсчитать число перестановок, таких, что тг = 7Г~?

► 15. [М25] Докажите, что перестановка ai... мультимножества

{Ui Xi, П2 Х2, ,Пт Хт},

где XI < Х2 < < Хт и П1 + П2 + + Пт = т, является циклом тогда и только тогда, когда ориентированный граф с вершинами {х } и дугами из Xj в a„iH-

содержит ровно один ориентированный цикл. В таком случае число способов представления перестановки в виде цикла равно длине этого ориентированного цикла. Например, ориентированным графом, соответствующим перестановке

faaabbcccdd\ а»-

[dcbacaabdcj j,

а два способа представления перестановки в виде цикла имеют вид {baddcacabc)ii icaddcacbab).

16. [М35] В предыдущем разделе, формула 5.1.1~(8), мы нашли производящую функцию для инверсий перестановок в частном случае, когда в перестановке участвуют элементы множества. Покажите, что в общем случае перестановок мультимножества производящая функция для инверсий {пг Ж1,П2 • жг,...} равна "г-полиномиальному коэффициенту"

( " ) = , , где mU = n(l + z + ... + /-).

[Ср. с (3) и с определением г-номиальных коэффициентов в формуле 1.2.6-(40).]

17. [М24] С помощью производящей функции, найденной в упр. 16, вычислите среднее значение и дисперсию для числа инверсий в случайной перестановке мультимножества.

18. [МЗО] (П. А. Мак-Магон.) Индекс перестановки oi аз • • • Оп был определен в предыдущем упражнении; мы доказали, что число перестановок этого множества, имеющих данный индекс к, равно числу перестановок, имеющих к инверсий. Верно ли это для перестановок заданного мультимножества?

19. [НМ28] Определим функцию Мёбиуса р{п) перестановки тг: она равна О, если тг содержит повторяющиеся элементы, и (-1)* в противном случае, если тг - произведение к простых перестановок. (Ср. с определением обычной функции Мёбиуса; упр. 4.5.2-10.)

a) Докажите, что если тг / б, то

YW = о,

где сумма берется по всем перестановкам А, являющимся левыми сомножителями в разложении тг (т. е. по всем А, таким, что тг = Xjp, где р - некоторая перестановка).

b) Докажите, что если xi < Х2 < < Хт и тг = Xj Xj -Xj, где 1 < < m при 1<к<п,то

р(тг) = (-l)"6(iii2...Jn), где €(п 12 .. .i„) = sign

► 20. [НМЗЗ] (Д. Фоата.) Пусть (а) - произвольная матрица действительных чисел. Пользуясь обозначениями из упр. 19, (Ь), определим 1/(тг) = а;,л ... а;„у„ , где двухстрочное представление перестановки тг таково:

/ Xi Xi2 . . . Xi \

Эта функция полезна при вычислении производящих функций для перестановок мульти-.множества, потому что Ji(Tr), где сумма берется по всем перестановкам тг мультимножества

{Ш xi, . . . ,Пт Хт} ,

будет производящей функцией для числа перестановок, удовлетворяющих некоторым ограничениям. Например, если положить Oij = z при г = j и а = 1 при г / j, то ь(тг) - производящая функция для числа "неподвижных точек" (столбцов, в которых верхний и нижний элементы равны). Чтобы можно было исследовать Ji(Tr) для всех мультимножеств одновременно, рассмотрим функцию

С = тгК?г),

где сумма берется по всем тг из множества {х\,...,x}* всех перестановок мультимножеств, содержащих элементы xi,..., Хт, и посмотрим на коэффициенты при ж" ... х в G.