в этой формуле для G будем рассматривать тг как произведение переменных х. Наг пример, при m = 2 имеем

G = l+Xil/{xi)+X2lix2)+XlXlu{xiXi)+XiX2U{xiX2)+X2XlU{x2Xl)+X2X2l{x2X2)-\----

= l+xiaii +X2a22+xlali+xiX2aua22+xiX2a2iai2 + xlal2-\----•

Таким образом, коэффициент при а:" • • х в G равен сумме Y1 i) по всем перестановкам 7Г мультимножества {гц Х1,...,Пт Хт}- Нетрудно видеть, что этот коэффициент равен также коэффициенту при a:"... х в выражении

(ацХ! Н-----h aimm)" (021X1 Н-----\- а2тХтУ {dmlXl Н-----h UmmXm)""

Цель данного упражнения - доказать формулу

а = 1/D, где D = det

/1 - aiiXl -0122:2 ... -Olmm \

-02ia:i 1 - 0222:2 -а2тХт

\ -Omll -Om2a:2 .. "i- - ЯттХт

которую П. А. Мак-Магон (Р. А. MacMahon) в своей книге Combin&tory Amdysis 1 (1915), разд. 3, назвал "основной теоремой" Например, если Оу = 1 при всех г и j, то эта формула дает

G = 1/(1 - {Xl + Х2 + + Хт))

И коэффициент при a;7... оказывается равным (niH-----ЫтУ-/п1!... Пт!, как и должно

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

a) 1/(7гтр) = и{п)и{р);

b) в обозначениях из упр. 19 D = кр{7т)и{п), где сумма берется по всем перестановкам 7г из множества {xi,... ,Хт};

c) из (а) и (Ь) следует D G = I.

21. [М21] Пусть заданы ni, ..., Пт и d > 0. Сколько перестановок oi 02 ... о„ мультимножества {nil,... ,пттп] удовлетворяют условию Oj+i > Oj-dnpn 1 < j < n = шН-----ЬПт?

22. [МЗО] Пусть P(a:" .. -х) означает множество всех возможных перестановок мультимножества {п1 -Xl,... ,Пт Хт} И пусть Pq{xq° х" ... xJJT ) - подмножество Р{хд°х1 . . . х), в котором первые по элементов не равны хо.

a) Задав число t, 1 < t < т, найдите однозначное соответствие между Р(1" ... т"") и множеством всех упорядоченных пар перестановок, которые соответственно принадлежат Ро(0*1ч ... (п«) и Ро(0*(( -Ь 1)"+1 ... т""), для некоторого к > 0. [Указание. Для каждого тг = oi...o„ 6 P(li ... m""") положите, что (тг) - перестановка, полученная путем замены ( -Ь 1, ..., тп значением О и удаления всех О на последних т+1 + - +Пт позициях; аналогично положите, что г(7г) - перестановка, полученная путем замены 1, ..., ( значением О и удаления всех О на первых ni Н-----hnt позициях.]

b) Докажите, что число перестановок Po(0"°l" ... т""*), имеющих в двухстрочном представлении pj столбцов ° и qj столбцов j, равно

Р(дГ .. • х-уГ"" • • • Ут--"") Р(Г • • • xvry"-" ут-"-)

Ро(0"о1ч .. .т"-")!

с) Пусть wi, Wm, zi, Zm - комплексные числа на единичной окружности. Определите вес w{n) перестановки тг 6 Р(1"... т""*) как произведение весов ее столбцов в двухстрочном представлении, где вес столбца 1 равен Wj/wk, если j и к

оба < ( или оба > (, в противном случае вес равен Zjjzk- Докажите, что сумма ги(7г) по всем тг € Р(1" ... т"™) равна

fcP(n<,-fc)!(n>,-fc)!...........=

<V\I \pr,

k\ {n<t -fc)!(n>t -fc)! y-/nl /пт\/ту (Wrn Y

fri ni\...nml \pi) "\pm)\Zl ) " \ Zm )

где n<t означает ni H-----hnt, n>t означает щ+1 Н-----hn и внутреннее суммирование

выполняется по всем (pi,... ,рш), таким, что p<t = pyt = к.

23. [М23] Цепочку ДНК можно рассматривать как слово четырехбуквенного алфавита. Предположим, мы скопировали цепочку ДНК и полностью разложили ее на однобуквенные составляющие, а затем случайным образом их вновь объединили. Докажите, что, если поместить полученную таким образом цепочку вслед за исходной, число позиций, в которых эти две цепочки будут отличаться, с большей вероятностью будет четным, чем нечетным. [Указание. Примените к этому случаю результат предыдущего упражнения.]

24. [27] Рассмотрим некоторое отношение R, которое может существовать между двумя неупорядоченными парами букв; если {ю, ж}Д{у, г}, мы говорим, что {ги,х} сохраняет {у, г}, в противном случае {wx} перемещает {у, г].

Операция транспозиции " f применительно к R меняет у z или f у в зависимости от того, сохраняет или перемещает пара {w,x} пару {г/, г}, полагая, что w ф х п у ф z; если W = х или у = г, то транспозиция всегда формирует f .

Операция сортировки двухстрочного массива (J ) применительно к R находит наибольшее Xj, такое, что Xj > Xj+i, и транспонирует (взаимно переставляет) столбцы j и J + 1 до тех пор, пока не установится xi < < Хп. (Мы не ставим условия, чтобы yi .. .уп представляло собой перестановку х\ .. .Хп.)

a) Для данного (J Zll) докажите, что для каждого х 6 {xi,... ,Хп} существует единственное у е {yi,... ,2/n}, такое, что sort(j; = iVvl 1/0 некоторых

х2,У2,...,х,у.

b) Обозначим через (J :;: )®{%\ ;;: %\) результат сортировки (J f J l\) применительно к R. Например, если R всегда истинно, @ является просто сопоставлением, если R всегда ложно, @ представляет собой включающее произведение у- Обобщите теорему А - докажите, что любая перестановка тг мультимножества М имеет единственное представление вида

тг = (хц . . . Х1„1 yi) @ ((Х21 . . . Х2п2 У2) @ • • @ (хп . . . Xtn, Vt)) ,

удовлетворяющее (16), если переопределить цикл таким образом: в (11) вместо (xi Х2 ... Хп) подставить (х2 ... х„ xi). Например, пусть {w, x}R{y, z] означает, что w, х, у и Z различны. Из этого, в свою очередь, следует, что разложение выражения (12) по аналогии с выражением (17) есть

(ddbca) @ {(сЬЬа) @ {(cdb) @ ({db) @ (d)))).

(Операция @ отнюдь не всегда следует закону ассоциативности; скобки в обобщенном разложении следует раскрывать справа налево.)

*5.1.3. Серии

В главе 3 была проанализирована длина неубывающих серий в перестановке и показано, что этот параметр позволяет проверить случайность последовательности. Если поместить вертикальные черточки до и после перестановки oi ог ... а„, а также между Qj и Oj+i, когда aj > a+i, то сериями будут называться серии, ограниченные парами черточек. Например, в перестановке

3 5 71 6 8 942

имеется четыре серии. В разделе 3.3.2G были найдены среднее число серий длины к в случайной перестановке множества {1,2,... ,п} и ковариацня числа серий длины j и длины к. Серии важны при изучении алгоритмов сортировки, так как они представляют упорядоченные серии данных. Поэтому-то мы теперь вновь вернемся к вопросу о сериях. Обозначим через

число перестановок множества {1,2,...,п}, имеющих ровно к нисходящих серий aj > Oj+i и к + I восходящих серий. Такие числа возникают и в других контекстах; их обычно называют числами Эйлера, потому что Эйлер проанализировал их в своей знаменитой книге Institutiones Calculi Differentialis (St. Petersburg: 1755, 485-487) после того, как впервые использовал несколькими годами ранее [Comment. Acad. Sci. Imp. Petrop. 8 (1736), 147-158, §13]; их следует отличать от чисел Эйлера Е„, о которых идет речь в упр. 5.1.4-23. Угловые скобки в () напоминают символ ">", который присутствует в определении убывания. Конечно, {) также равно числу перестановок, в которых имеется к возрастаний aj < Oj+i.

Из любой данной перестановки множества {!,...,п - 1} можно образовать п новых перестановок, вставляя элемент п во все возможные места. Если в исходной перестановке содержалось к нисходящих серий, то ровно к + 1 новых перестановок будут иметь к нисходящих серий; в остальных п - 1-к перестановках будет по /с -ь 1 серий, поскольку всякий раз, когда п вставляется не в конец существующей серии, число нисходящих серий увеличивается на единицу. Например, из перестановки 312 45 можно получить шесть перестановок

631245, 361245, 316245, 312645, 3 12465, 312456.

Все эти перестановки, кроме второй и последней, содержат по две нисходящие серии вместо одной исходной. Отсюда имеем рекуррентное соотношение

где целое п > О и к также целое. Условимся, что

°)=4о, (3)

т. е. будем считать, что в нуль-перестановке (пустой перестановке) не содержатся нисходящие серии. Читатель, возможно, найдет небезынтересным сравнение (2) с рекуррентным соотношением для чисел Стирлинга [формулы 1.2.6-(46)]. В табл. 1 приведены числа Эйлера для малых п.

В табл. 1 можно заметить некоторые закономерности. По определению имеем