Как обычно, через "Т" обозначена операция транспонирования строк и столбцов;

- диаграмма, а (Q) - двойственная диаграмма, поскольку элементы q расположены в обратном порядке.

b) Если пользоваться двойственным отношением порядка для р, но не для q, то двухстрочный массив (27) соответствует паре ((Р-),(5).

c) Если пользоваться двойственным отношением порядка как для р, так и для q, то двухстрочный массив (28) соответствует паре {P,Q).

Доказательство. Простое доказательство этой теоремы неизвестно. То, что случай (а) соответствует паре (Р,Х), где X - некоторая двойственная диаграмма, доказано в упр. 5; следовательно, по теореме В случай (Ь) соответствует паре {Y, Q) для некоторой двойственной диаграммы Y nY должна иметь ту же форму, что и Р.

Пусть Pi = min{pi,... ,Pn}; так как Рг - "наибольший" элемент при двойственном отношении порядка, то он оказывается на границе У и не вытесняет никаких элементов при построении из теоремы А. Таким образом, если последовательно вставлять элементы pi,... ,pi-i,pi+i,... ,рп, применяя двойственное отношение порядка, то получится Y - {pi}, т. е. Y, из которой удален элемент pi. По теореме С, если последовательно вставлять элементы рх,... ,... ,р„, применяя обычное отношение порядка, построим диаграмму d(P), которая получается путем применения к Р алгоритма S. Индукция по п дает Y - {pi} - (d{P)). Но поскольку

iPf-{Pi} = {diPff (29)

по определению операции 5, а У имеет ту же форму, что и (Р), должно иметь место равенство Y = (Р*).

Тем самым доказано утверждение (Ь); (а) получается в результате применения теоремы В. Последовательное применение (а) и (Ь) показывает, что случай (с) соответствует паре {{{P)fd(Qff), а это равно (P*,Q*), так как {Pf = {P) вследствие симметрии операции S по отношению к строкам и столбцам,

Эта теорема, в частности, устанавливает два удивительных факта, касающихся алгоритма вставки в диаграмму. Если в результате последовательной вставки различных элементов pi,..., Рп в пустую диаграмму получается диаграмма Р, то в результате вставки этих элементов в обратном порядке, p„,...,pi, получится транспонированная диаграмма Р. Если же мы не только станем вставлять элементы в порядке p„,...,pi, но и поменяем ролями > и <, а также О и оо, то получим двойственную диаграмму P. Настоятельно рекомендуем читателю проанализировать эти процессы самостоятельно на нескольких простых примерах. Необычная природа этих совпадений может вызвать подозрение о вмешательстве каких-то потусторонних сил. До сих пор неизвестно какое-либо простое объяснение подобных явлений; кажется, не существует простого способа доказать даже то, что случай (с) соответствует диаграмме той же формы, что и Р и Q, хотя метод характеристики классов, использованный в упр. 2, может послужить отправной точкой для дальнейших поисков.

Соответствие, устанавливаемое теоремой А, было найдено Ж. Б. Робинсоном (G. de В. Robinson) [American J. Math. 60 (1938), 745-760, §5] в несколько иной

и довольно туманной форме как часть решения весьма сложной задачи из теории групп. Он сформулировал теорему В без доказательства. Много лет спустя К. Шенстед независимо заново открыл это соответствие, которое сформулировал в терминах "вытеснения" т. е., по существу, в той же форме, которую использовали мы в алгоритме I. Шенстед также доказал часть теоремы D (а), касающуюся "Р" [см. Canadian J. Math. 13 (1961), 179-191]. В работе М. П. Шуценберже [Math. Scand. 12 (1963), 117-128] доказана теорема В и "(5"-часть теоремы D (а), из которой следуют (Ь) и (с). Это соответствие можно распространить и на перестановки мультимножеств; случай, когда pi,... ,р„ необязательно различны, рассмотрел Шенстед, а "максимальное" обобщение, когда и р, и q могут содержать повторяющиеся элементы, исследовано Кнутом [Pacific J. Math. 34 (1970), 709-727].

Обратимся теперь к родственному вопросу: сколько диаграмм, составленных из элементов {1,2,...,п}, имеют данную форму (п1,П2,... ,Пт), где ni + П2 + • • • + Пт = п? Обозначим это число через /(ni, Па,..., п); если параметры jij - произвольные целые числа, то функция / должна удовлетворять соотношениям

> п„ > 0;

(30) (31)

/(п1,П2,...,Пт) = О, если не ni > Па >

/(П1,П2,...,Пт,0) = /(П1,П2,...,Пт);

/(П1,П2,...,Пт) = /(П1-1,П2,...,Пт) -(-/(Пх, Па -1, . . ., П)

+ •• + /("!, Па,..., Пт-1),

если П1 > Па > • • • > Пт > 1. (32)

Рекуррентное соотношение (32) вытекает из того факта, что при удалении из диаграммы наибольшего элемента всегда снова получается диаграмма; например, количество диаграмм формы (6,4,4,1) равно /(5,4,4,1) + /(6,3,4,1) + /(6,4,3,1) + /(6,4,4,0) = /(5,4,4,1)4-/(6,4,3,1)-1-/(6,4,4), потому что всякая диаграмма формы (6,4,4,1) из элементов {1,2,..., 15} получается в результате вставки элемента 15 в подходящее место в диаграмме формы (5,4,4,1), (6,4,3,1) или (6,4,4). Изобразим это схематично:

(33)

функция /(п1,П2,... ,Пт), удовлетворяющая таким соотношениям, имеет до-ватьно простой вид:

/(п1,па,...,Пт) =

Д(п1 + т - 1, П2 + тп - 2, ..., Пт) п!

{щ+т-1)\{п2 + т-2)\ ...nj. при условии, что соблюдается соотношение

т + т - I > П2 + т - 2 > > Пт-

Здесь через Д обозначена функция "квадратный корень из дискриминанта"

: п [Xi-Xj). (35) l<i<i<m

Формулу (34) вывел Г. Фробениус [см. G. Frobenius Sitzungsberichte preuB. Akad. der Wissensdiaften (1900), 516-534, §3], изучая эквивалентную задачу теории групп; он использовал довольно глубокую аргументацию, опирающуюся на теорию групп. Комбинаторное доказательство независимо нашел Мак-Магон [см. MacMahon, Philosophical Trans. А209 (1909), 153-175]. Эту формулу можно доказать по индукции, так как (30) и (31) доказываются без труда, а формула (32) получается, если положить у = -1 в тождестве из упр. 17.

Из теоремы А в связи с этой формулой для числа диаграмм вытекает замечательное тождество. Взяв сумму по всевозможным формам диаграмм, получим

п!= т f{kiM...,k?

ki>k2>->k„>0 *1+*2Н-----\-к„-п

«:1>А;2> ••>*„>0

ki+k2+-+k„Sn

A{ki -Ь n - 1, А:2 -Ь n - 2, ..., к„) (A;i+n-l)!2 (A;2+n-2)!2 ...k„l

A{qi,q2,...,qn)

9i>92>->gn >0 9i+92+-+9n = (n+l)n/2

qn

отсюда

A(gi,g2,---,gn)

qi+q2+-+q„=(.n+l)n/2 91,92, ..,9n>0

912 9212

Qn

= 1.

(36)

В последней сумме отсутствуют неравенства qi > q2 > • > Яп, потому что слагаемые - симметричные относительно q функции, которые обращаются в О при qi = qj- Аналогичное тождество появляется в упр. 24.

Формулу для числа диаграмм можно представить в более привлекательной форме, если ввести понятие "уголок" В уголок, соответствующий клетке диаграммы, входит сама эта клетка плюс все клетки, расположенные в той же колонке снизу и в той же строке справа от нее. Например, заштрихованный участок на рис. 5 - это уголок, соответствующий клетке (2,3) строки 2 и столбца 3; он состоит из шести клеток. В каждой клетке на рис. 5 записана длина соответствующего ей уголка.

Если диаграмма имеет форму (ni,пг,... ,Пт), то длина самого длинного уголка равна П1-\-т-1. Дальнейший анализ длин уголков показывает, что строка 1 содержит все длины ni4-m-l, ni-)-m -2, 1, кроме (ni-)-m-l)-(nm), (щ--т-!)-(Пт-1-l-l), (п1-)-т-1)-(п2-1-т-2). Например, на рис. 5 длины уголков в 1-й строке суть 12, И, 10, ..., 1, за исключением 10, 9, 6, 3, 2; эти исключения соответствуют пяти несуществующим уголкам, начинающимся в несуществующих клетках