Рис. 5. Уголки и длины уголков.

(6,3), (5,3), (4,5), (3,7), (2,7) и заканчивающимся в клетке (1,7). Аналогично j-я строка содержит все длины уголков nj+m-j, ..., 1, кроме {uj +m - j) - (п), ..., {uj +m-j) - {uj+i +m-j - 1). Отсюда следует, что произведение длин всех уголков равно

(П1+ТП-1)!(П2 + ТП-2)!...Пт!

А{п1+т-1,П2 + т-2,.. .,Пт)

Это выражение входит в формулу (34). Итак, мы получили результат, который в работе J. S. Frame, G. de В. Robinson, R. М. Thrall, Canadian J. Math. 6 (1954), 316-324, сфомулирован в виде теоремы.

Теорема Н. Количество диаграмм данной формы, составленных из элементов {1,2,..., п}, равно п!, деленному на произведение длин уголков.

Такая лаконичная формулировка заслуживает и лаконичного доказательства. Мы приведем нестрогое рассуждение, основанное на эвристике. Каждый элемент диаграммы - минимальный в своем уголке; если заполнить клетки диаграммы случайным образом, то вероятность того, что в клетке (г, j) окажется минимальный элемент соответствующего уголка, есть величина, обратная длине уголка. Перемножение этих вероятностей по всем i и j приводит к формулировке теоремы Н. Однако такое рассуждение ошибочно, поскольку эти события отнюдь не являются независимыми! Все известные доказательства теоремы Н, основанные на комбинаторных свойствах уголков, были некорректны вплоть до 1992 года (см. упр. 39), хотя и предлагалось несколько непрямых доказательств (см. упр. 35, 36 и 38).

Существует интересная связь между теоремой Н и перечислением деревьев, которое рассматривалось в главе 2.Мы видели, что бинарным деревьям с п узлами соответствуют перестановки, которые можно получить с помощью стека, и что этим перестановкам соответствуют последовательности oi аг ... а2п п литер S и п литер Х, такие, что количество литер S никогда не бывает меньше количества литер X, если читать последовательность слева направо (см. упр. 2.2.1-3 и 2.3.1-6). Подобным последовательностям естественным образом сопоставляются диаграммы формы (п,п); в 1-ю строку помещаются индексы i, такие, что а = S, а во 2-ю строку - индексы, при которых а = X. Например, последовательности

SSSXXSSXXSXX

соответствует диаграмма

Условие, налагаемое на столбцы, удовлетворяется в такой диаграмме в том и только том случае, когда при чтении слева направо число литер X никогда не превышает числа литер S. По теореме Н количество всевозможных диаграмм формы (п,п) равно

(2п)! . (п + 1)!п!

следовательно, таково же число бинарных деревьев, что согласуется с формулой 2.3.4.4-{14). Более того, если воспользоваться диаграммой формы (п, т) при п>т, то при помощи этого рассуждения можно решить и более обшую "задачу о баллотировке", рассмотренную в ответе к упр. 2.2.1-4. Таким образом, теорема Н в качестве простых частных случаев включает в себя некоторые весьма сложные задачи о перечислении.

Всякой диаграмме А формы (п, п) из элементов {1,2,..., 2п} соответствуют две диаграммы {Р, Q) одинаковой формы. Следующий способ построения такого соответствия предложен Мак-Магоном [Combinatory Analysis 1 (1915), 130-131]. Пусть Р состоит из элементов {!,...,п}, расположенных так, как в А, а Q получается, если взять остальные элементы А, повернуть всю конфигурацию на 180° и заменить п + 1, п + 2, ..., 2п значениями п, п - 1 соответственно. Например, диаграмма (37) распадается на

после поворота и перенумерации имеем

(38)

Наоборот, каждой паре диаграмм одинаковой формы, состоящих из п элементов и из не более чем двух строк, соответствует диаграмма формы (п, п). Следовательно (из упр. 7), число перестановок oi 02 ... а„ множества {1,2,..., п}, не содержащих убывающих подпоследовательностей а, > Cj > яри i < j < к, равно числу бинарных деревьев с п узлами. Интересное взаимно однозначное соответствие между такими перестановками и бинарными деревьями, установленное более прямым способом, чем тот окольный путь через, алгоритм I, которым воспользовались мы, нашел Д. Ротем [см. D. Rotem, Inf. Ргос. Letters 4 (1975), 58-61]; аналогично существует довольно прямое соответствие между бинарными деревьями и перестановками, не содержащими подпоследовательностей Cj > Ck > di при i < j < к (см. упр. 2.2.1-5).

Число способов заполнения диаграммы формы (6,4,4,1), очевидно, равно числу способов разметки вершин ориентированного графа

числами {1,2,..., 15} так, чтобы метка вершины и была меньше метки вершины и, если и V. Иначе говоря, оно равно числу способов топологической сортировки частичного упорядочения (39), как в разделе 2.2.3.

В общем случае можно сформулировать эту же задачу для произвольного ориентированного графа, не содержащего ориентированных циклов. Было бы хорошо, если бы существовала какая-нибудь простая формула, обобщающая теорему Н для произвольного графа, однако не все графы обладают такими приятными свойствами, как графы, соответствующие диаграммам. Другие классы ориентированных графов, для которых задача о разметке вершин имеет простое решение, частично обсуждаются в упражнениях в конце этого раздела. Там также приводятся упражнения, в которых показано, что для некоторых вариантов ориентированных графов не существует простой формулы, соответствующей теореме Н. Например, число способов разметки вершин не всегда является делителем п!.

Завершим наши исследования подсчетом общего числа диаграмм, которые можно сформировать из п различных элементов. Обозначим это число через <„. Как вытекает из следствия теоремы В, i„ равно числу инволюций множества {1,2,..., п}. Перестановка обратна самой себе тогда и только тогда, когда ее представление с помощью циклов состоит только из единичных циклов (неподвижных точек) и циклов из двух элементов (транспозиций). Поскольку в i„ i из i„ инволюций (п) - неподвижная точка, а в i„ 2 из них (j п) - цикл из двух элементов при некотором фиксированном j < п, то получаем формулу

tn = tn-l + (П - l)tn-2 , (40)

которую вывел Роте в 1800 годудля получения таблицы значений i„ при малых п. Значения для п > О равны 1, 1, 2, 4, 10, 26, 76, 232, 764, 2 620, 9 496, ....

Рассмотрим другой способ. Пусть имеется к циклов из двух элементов и {п-2к) единичных циклов. Существует (2") способов выбора неподвижных точек, и полиномиальный коэффициент (2А:)!/(2!)* равен числу способов упорядочения остальных элементов в к различимых транспозиций. Разделив на к\, чтобы сделать эти транспозиции неразличимыми, получим

L"/2J ,

tn=Ztn{k), М)=(„ 2,),2.,,- (41)

К сожалению, насколько это известно, такую сумму уже нельзя упростить (если только не принимать во внимание использование полиномов Эрмита г"2~"/х хНп{-г/у/2) в качестве отсчетов). Поэтому, для того чтобы лучше понять поведение величины tn, мы применим два косвенных подхода.

a) Можно найти производящую функцию

J2tnz"/n\e+/ (42)

(см. упр. 25).

b) Можно определить асимптотическое поведение величины i„. Это поучительная задача, и ее решение содержит несколько общих методов, которые будут полез-