при этом другие метки так, как в алгоритме S, и помещая метки 1, 2, . . на освободившиеся места. Покажите, что эта операция, если ее многократно применять к двойственной системе меток с обратным отношением порядка для чисел, дает исходную систему меток; исследуйте другие свойства этой операции.

31. [НМЗО] Пусть жп -число способов такого размещения п взаимно неатакующих ладей на шахматной доске размером п х п, что расположение не меняется при отражении доски относительно обеих главных диагоналей. В результате получим Ж4 = 6. (От инволюций же требуется симметрия только относительно одной из главных диагоналей. Похожая задача рассматривалась в упр. 5.1.3-19.) Найдите асимптотическое поведение Хп-

32. [НМ21] Докажите, что („ - среднее значение X", если X является нормальной случайной величиной с математическим ожиданием 1 и дисперсией 1.

33. [М25] (О. Митчелл (О. Mitchell), 1881.) Верно ли утверждение:

Д(а1,а2,...,ат)/Д(1,2,...,т) является целым числом, если oi, 02, ..., От - также целые числа.

34. [25] (Т. Накаяма (Т. Nakayama), 1940.) Докажите, что если форма диаграммы включает уголок длиной об, она содержит и уголок длиной а.

► 35. [30] (А. П. Хиллман (А. Р. Hillman) и Р. М. Грассл (R. М. GrassI), 1976.) Размещение неотрицательных целых чисел pij по ячейкам диаграммы, которая имеет ячеек в строке i и nj ячеек в столбце j, называется плоским разбиением т, если = пг и

Pn>--->Pini, Pij > >Pn!j, где 1 < г < nl, 1 < j < ni.

Оно же называется обратным плоским разбиением, если вместо сформулированных выше выполняются условия

Pii < •• <Ршо P\j < <Pnj, где 1 < i < ni, 1 <i < nj.

Рассмотрите следующий алгоритм, который выполняет обратные плоские разбиения данной формы и формирует другой массив чисел qij, имеющий ту же форму.

G1. [Инициализация.] Присвоить qtj О, I < j < Щ и I < i < nl. Затем присвоить

G2. [Поиск ненулевой ячейки.] Если Pn>j > О, присвоить i nj, к j и перейти к шагу G3, В противном случае, если j < п\, увеличить j на 1 и повторить этот шаг. Б противном случае остановить процесс (массив р теперь обнулен).

G3. [Уменьшение р.] Уменьшить р* на 1.

G4. [Переход вверх или вправо,] Если i > 1 и P{i-i)k > ptk, уменьшить г на 1 и вернуться к шагу G3, Б противном случае, если к < nt, увеличить Л на 1 и вернуться к шагу 03.

G5. [Увеличение q.] Увеличить qij на 1 и вернуться к шагу G2.

Разработайте алгоритм, который восстанавливает значения р по значениям q, и тем самым докажите, что описанное выше построение определяет взаимно однозначное соответствие между обратным плоским разбиением т и рещением уравнения

m = hijqij ,

где числа hij - длины уголков формы.

36. [НМ27] (P. П. Стэнли (R. P. Stanley), 1971.) (a) Докажите, что количество обратных плоских разбиений т на данной форме равно [z] 1 / (1 - z), где числа hij - суть длины уголков формы. (Ь) Выведите из этого результата теорему Н. [Указание. Задумайтесь, к чему асимптотически приближается количество разбиений при т -> оо.]

37. [М20] (П. А. Мак-Магон , 1912.) Какова производящая функция для любого плоского разбиения? (Коэффициент при z" должен быть общим числом разбиений тп, если форма диаграммы неограниченна.)

► 38. [МЗО] (Грин (Greene), Ниенхьюз (Nijenhuis), Вильф (Wilf), 1979.) Можно построить прямой ациклический граф на ячейках Г любой данной формы диаграммы следующим образом. Пусть дуги исходят из каждой ячейки к другим ячейкам в этом уголке; внещняя степень ячейки (г, j) будет тогда dij = hij - 1, где hij равно длине уголка. Предположим, мы построили некоторый случайный путь на этом диграфе, выбрав случайным образом начальную ячейку {i,j), и случайно выбирали следующие дуги до тех пор, пока не оказались в угловой ячейке, из которой нет выхода. Каждый случайный выбор выполняется равновероятно.

a) Пусть (а, Ь) - угловая ячейка Г и пусть I = {го, • •, ik} и J = {jo,. ,ji} - множества строк и столбцов, причем io < < ik = а и jo < < ji = Ь. Диграф содержит (*) путей, множества строк и столбцов которых суть I и J; пусть Р{1, J) - вероятность выбора определенного случайного пути. Докажите, что Р{1, J) = \/{ndib di ibdajo daji i), где п - \Т\.

b) Пусть /(Г) = n\/Y\hij. Докажите, что случайный путь заверщается в угловой ячейке (а,Ь) с вероятностью /(Г \ {(а, Ь)}) (Г).

c) Покажите, что результат (Ь) доказывает теорему Н и предоставляет способ формирования случайной диаграммы формы Г, причем все диаграммы /(Г) равновероятны.

39. [М38] (И. М. Пак, А. В. Стояновский, 1992.) Пусть Р - массив (щ,..., п„), который заполнен некоторой перестановкой множества целых чисел {1,..., п}, п = ni -- • • • -- Пт-Следующая процедура, которая аналогична алгоритму "просеивания", описанному в разделе 5.2.3, может быть использована для преобразования Р в диаграмму. Она также определяет массив Q такой же формы, который может послужить для комбинаторного доказательства теоремы Н.

Р1. [Цикл по {i,j)] Выполнить щаги Р2 и РЗ для каждой ячейки {i,j) массива в обратном лексикографическом порядке (т. е. снизу вверх и справа налево в каждой строке), затем прекратить выполнение процедуры.

Р2. [Обработать Р в (i,j).] Присвоить К <- Ру и выполнить алгоритм S (см. ниже).

РЗ. [Изменение Q.] Присвоить Qik <- Qi(*;+i) + l Для j < А: < s и присвоить Qis i- i - r. I

Ниже описан тот же алгоритм, что и алгоритм S Шуценберже, но щаги S1 и S2 слегка .модифицированы - распространены на более общий случай.

S1. [Инициализация.] Присвоить г <- г, s <- j.

S2. [Выполнено?] Если К < P(r+i)s и АГ Pr(s+i), присвоить Ргз К и завершить процесс.

(Алгоритм S предполагает особый случай: i = I, j = I, К = оо.)

Например, алгоритм Р обрабатывает массив формы (3,3,2) следующим образом, если просматривать содержимое массивов Р и Q в начале каждого щага Р2, причем значения Pij выделены полужирным шрифтом:

Окончательный результат имеет вид

а) Если Р - это просто массив 1 х п, алгоритм Р сортирует его и превращает в

Какой вид при этом будет иметь массив Q?

b) Ответьте на тот же вопрос, но в случае, если Р имеет вид п х 1, а не 1 х п.

c) Докажите, что в общем случае получим

-bij < Qij < Tij,

где bij - число ячеек, расположенных ниже ячейки (г, j), и nj - число ячеек справа от нее. Таким образом, число возможных значений Qij в точности равно hij - размеру (г, j)-ro уголка.

d) Теорема Н будет доказана по построению, если мы сможем показать, что алгоритм Р определяет однозначное соответствие между п! способами заполнения исходной формы и парами результирующих массивов (Р, Q), где Р есть диаграмма, а элементы в Q удовлетворяют условиям п. (с). Значит, желательно найти процедуру, обратную алгоритму Р. Для каких исходных перестановок алгоритм Р сформирует массив Q = (о ~о) формы 2x2?

e) Какую исходную перестановку алгоритм Р преобразует в массивы

f) Разработайте алгоритм, обратный по отношению к алгоритму Р, задавая любую пару массивов (Р, <Э), таких, что Р - диаграмма, а Q удовлетворяет условиям п. (с). [Указание. Постройте ориентированное дерево, вершины которого - ячейки а дуги -

ihj) -+ [hj - 1), если Puj-i) > P(i-iy; {hi) -+ (г - 1,Я. если Puj-i) < P(i-i)j-