Покажем, что эта операция соответствует взаимной замене Р и Q в построении из теоремы А.

В упр. 2 наши замечания об определении классов переформулированы таким образом, что класс, к которому относится пара {qi,pi), не зависит от того факта, что элементы Qi,Qa, • • •,9п расположены в порядке возрастания. Поскольку результирующие условия симметричны относительно q п р, операция (21) не нарушает структуру классов; если {q,p) принадлежит классу t относительно (16), то {р,д) принадлежит классу t относительно (21). Поэтому, если разместить элементы последнего класса t так, чтобы

Ph < < Pi2 < Pii.)

> • • • > 9i2 > Qii.

(22)

TO no аналогии с (18) получим

Рп = qir, Qit = Pii.

как в (19), a столбцы

Ч 9u

(23)

(24)

войдут в вытесненный массив, как в (20). Следовательно, первые строки Р nQ меняются местами. Кроме того, вытесненный двухстрочный массив для (21) является обратным по отношению к вытесненному двухстрочному массиву для (16), так что доказательство завершается применением индукции по числу строк в диаграмме.

Следствие. Количество диаграмм, которые можно сформировать из элементов {1,2,..., п}, равно капичеству инволюций множества {1,2,..., п}.

Доказательство. Если тг - инволюция, соответствующая паре диаграмм {P,Q), то 7г = 7г~ соответствует паре {Q,P). Следовательно, Р = Q. Обратно, если тг - какая-либо перестановка, соответствующая паре {Р,Р), то тг" тоже соответствует паре {Р,Р); отсюда тг = тг". Таким образом, существует взаимно однозначное соответствие между инволюциями тг и диаграммой Р.

Ясно, что элемент в левом верхнем углу диаграммы всегда наименьший. Это наводит на мысль о возможном способе сортировки множества чисел. Сначала можно составить из них диаграмму, многократно применяя алгоритм I, и в результате наименьший элемент окажется в углу, Затем этот наименьший элемент удаляется, а остальные элементы переразмещаются так, чтобы образовалась другая диаграмма; потом удаляется новый минимальный элемент и т. д.

Поэтому давайте посмотрим, что происходит, когда мы удаляем угловой элемент из диаграммы

(25)

После удаления 1 на освободившееся место необходимо поставить 2. Затем можно поднять 4 на место 2, однако 10 нельзя поднять на место 4; на это место можно

подвинуть 9, а потом 12 - на место 9. В общем случае приходим к следующей процедуре.

Алгоритм S (Удаление углового элемента). Этот алгоритм удаляет элемент из левого верхнего угла диаграммы Р и перемещает остальные элементы так, чтобы сохранились свойства диаграммы. Далее используются те же обозначения, что и в алгоритмах I и D.

51. [Начальная установка.] Присвоить г 1, si- 1.

52. [Выполнено?] Если Prs = оо, то процесс завершен.

53. [Сравнить.] Если P(r+i)s Pr(s+i), то перейти к шагу S5. (Сравниваем элементы справа и снизу от свободного места и передвигаем меньший из них.)

54. [Сдвиг влево.] Присвоить Prs <- Pr(s+i), s s + 1 к вернуться к шагу S3.

55. [Сдвиг вверх.] Присвоить Prs <- P(r+i)s, г <- г + 1 и вернуться к шагу S2.

Легко доказать, что после удаления с помощью алгоритма S углового элемента Р по-прежнему является диаграммой (см. упр. 10). Таким образом, применяя алгоритм S до тех пор, пока Р не исчерпается, можно прочитать его элементы в порядке возрастания. К сожалению, этот алгоритм сортировки оказывается не столь эффективным, как другие алгоритмы, которые нам еще предстоит рассмотреть. Минимальное время его работы пропорционально п; аналогичные алгоритмы, использующие вместо диаграмм деревья, затрачивают время порядка nlogn.

Хотя алгоритм S в приложении к сортировке и не отличается особой эффективностью, он обладает некоторы.ми очень интересными свойствами.

Теорема С (М. П. Шуценберже (М. Р. Schiitzenberger)). Если Р - диаграмма, построенная, как в теореме А, из перестановки ai ог ... а„, н если

щ = min{ai,a2,...,a„},

го алгоритм S преобразует Р в диаграмму, соответствующую перестановке oi... Oj-i ai+i...a„.

Доказательство. См. упр. 13.

Давайте после применения алгоритма S поместим на вновь освободившееся место Prs удаленный элемент, ио отобразим его курсивом, указав таким образом, что на самом деле элемент не является частью диаграммы. Применив, например, эту процедуру к диаграмме (25), мы получим

а выполнив такую же процедуру еще два раза, получим

Продолжая до тех пор, пока все элементы не будут удалены, получим конфигурацию

(26)

имеющую ту же форму, что и исходная диаграмма (25). Эту конфигурацию можно назвать двойственной диаграммой, потому что она похожа на диаграмму с той лишь разницей, что применяется "двойственное отношение порядка" (> и < поменялись ролями). Обозначим двойственную диаграмму, полученную из Р таким способом, через P.

Диаграмма Р определяется из единственным образом. В самом деле, исходную диаграмму можно получить из Р* при помощи того же алгоритма, но изменив на обратные отношения порядка и роли обычных и представленных курсивом элементов, поскольку Р - двойственная диаграмма. Например, применив к (26) два шага этого алгоритма, получим

В конце концов, опять получается диаграмма (25)! Этот замечательный результат - одно из следствий нашей следующей теоремы.

Теорема D (К. Шенстед (С. Schensted), М. П. Шуценберже (М. Р. Schiitzenberger)). Пусть

(Я1 Я2 ... Яп\ (27)

\Р1 Р2 PnJ

представляет собой двухстрочный массив, соответствующий паре диаграмм {Р, Q).

а) Если пользоваться двойственным (обратным) отношением порядка для д, но не для р, то двухстрочный массив

(28)

Чп \Рп

Р2 Р1

9Л PiJ

соответствует паре [P,{Q)).