Теорема А. Существует взаимно однозначное ссютветствие между множеством всех перестановок множества {1,2,...,п} и множеством всех упорядоченных пар диаграмм (Р, Q), где Р hQ - диаграммы одинаковой формы из элементов {1,2,...,п}.

(Пример к этой теореме содержится в приведенном ниже доказательстве.)

Доказательство. Удобнее доказать несколько более общий результат. По произвольному двухстрочному массиву

91 92 •• дп\ qi<q2<-<qn, ,Pi Р2 •• PnJ pi,P2,-.,Pn разл!

различны,

построим две соответствующие диаграммы Р к Q, где Р состоит из элементов {р1,--,Рп}, а Q - из элементов {qi,...,qn}, причем Р п Q имеют одинаковую форму.

Пусть Р и Q вначале пусты. При г = 1, 2, ..., п (именно в таком порядке) выполним следующую операцию: вставим pi в диаграмму Р при помощи алгоритма I; затем установим Qt qi, где s nt определяют вновь заполненную позицию в Р.

Например, если задана перестановка (72953) действуем следующим образом:

Вставка 7: Вставка 2:

Вставка 9:

Вставка 5:

(12)

Значит, пара диаграмм (P,Q), соответствующая перестановке (72953) иет вид

Из построения ясно, что Р nQ всегда имеют одну форму. Кроме того, поскольку элементы всегда добавляются на границу Q и в порядке возрастания, то Q - диаграмма.

Обратно, если заданы две диаграммы одинаковой формы, то соответствующий двухстрочный массив (11) можно построить так. Пусть элементами Q являются

Пусть также р, есть элемент х, который удаляется из Р по алгоритму D с использованием значений sat, таких, что Qst = 9i, причем г = п, ..., 2, 1 (именно в таком порядке).

Например, если применить это построение к диаграмме (13) и производить вычисления, обратные (12), до тех пор, пока Р не исчерпается, то получится массив

( 1 3 5 6 81 V7 2 9 5 3/-

Поскольку алгоритмы I и D взаимно обратны, взаимно обратны и описанные здесь два построения; таким образом, требуемое взаимно однозначное соответствие установлено.

Соответствие, определенное в доказательстве теоремы А, обладает множеством поразительных свойств, и теперь мы приступим к выводу некоторых из них. Убедительная просьба к читателю: прежде чем двигаться дальше, выполните упр. 1, чтобы освоить методику построений.

Как только элемент вытеснен из строки 1 в строку 2, он уже не влияет на строку 1; кроме того, строки 2, 3, ... строятся из последовательности "вытесненных" элементов так же, как строки 1, 2, ... строятся из исходной перестановки. Это наводит на мысль о том, что на построение в теореме А можно взглянуть иначе, обращая внимание лишь на первые строки Р и Q. Например, перестановка (72953) вызывает следующие действия над строкой 1 [ср. с (12)]:

1: Вставить 7, присвоить Qn 1.

3: Вставить 2, вытеснить 7.

5: Вставить 9, присвоить Q12 <- 5. (14)

6: Вставить 5, вытеснить 9.

8: Вставить 3, вытеснить 5.

Таким образом, первая строка Р - это 2 3, а первая строка Q - это 1 5. Кроме того, остальные строки Р nQ составляют диаграммы, соответствующие "вытесненному" двухстрочному массиву

/о с о\

(15)

/3 6 8\ V7 9 5J •

Чтобы понять, как строится строка 1, проанализируем элементы, попадающие в некоторый заданный столбец этой строки. Будем говорить, что пара {qi,Pi) принадлежит классу t двухстрочного массива

fqi 92 • • Чп\ 91 < 92 < • • • < gn, ,jg.

\pi р2 ... PnJ Pi,P2,--,Pn различны,

если после применения алгоритма I последовательно к pi,P2) • ,Pi, начиная с пустой диаграммы Р, оказывается, что р, = Ри- (Напомним, что алгоритм I всегда вставляет данный элемент в 1-ю строку.)

Легко видеть, что {qi,Pi) принадлежит классу 1 тогда и только тогда, когда pi имеет г - 1 инверсий, т. е. тогда и только тогда, когда pi = min{pi,P2) • ,Pi} - "левосторонний минимум" Если в массиве (16) вычеркнуть столбцы класса 1, то получится двухстрочный массив

такой, что пара {q,p) принадлежит классу t относительно (17) тогда и только тогда, когда она принадлежит классу t + l относительно массива (16). Операция перехода от (16) к (17) соответствует удалению крайней слева позиции строки 1. Это дает систематический способ определения классов. Например, в перестановке (72953) левосторонними минимумами являются элементы 7 и 2, так что класс 1 - это {(1,7), (3,2)}; в оставшемся массиве (953) все элементы минимальны, так что класс 2 - это {(5,9), (6,5), (8,3)}. В "вытесненном" массиве (15) класс 1 - это {(3,7), (8,5)}, а класс 2 - {(6,9)}.

Для любого фиксированного t элементы класса t можно так пометить

(9ti,Pn),-.-,(Qtii,,PiJ, чтобы выполнялись неравенства

Ян <qh < < 9u.

Pn>Pi,>->Pi„

поскольку в процессе выполнения алгоритма вставки позиция диаграммы Ри принимает убывающую последовательность значений Pi, ., Pi- В конце построения

Pu=Pu, Qu = 9n, (19)

а вытесненный двухстрочный массив, которым определяются строки 2, 3, ... диаграмм Р к Q, содержит столбцы

(Яп Я Qi. ) (20)

\Рн Ph Ph-lJ

и другие столбцы, аналогичным образом полученные из других классов.

Эти рассуждения приводят нас к простому методу вычисления Р nQ вручную (см. упр. 3), а также предоставляют средства для доказательства одного весьма неожиданного результата.

Теорема В. Если в построении из теоремы А перестановка

/1 2 ... .\

\ai 02 ... а„ у

соответствует диаграмме {P,Q), то обратная ей перестановка соответствует диаграмме {Q,P).

Это довольно удивительный факт, потому что в теореме А диаграммы Р п Q формируются совершенно разными способами и обратная перестановка получается в результате весьма причудливой перетасовки столбцов двухстрочного массива.

Доказательство. Предположим, имеется двухстрочный массив (16); поменяв местами его строки и рассортировав столбцы так, чтобы элементы новой верхней строки расположились в порядке неубывания, получим "обратный" массив

Р2 • Рп

Я2 Яп,

(р[ р, ... рЛ Pi < Р2 < < Рп,

/91 92 • • Яп\ - (Р1

\Р1 Р2 Рп) \Я1

Я1 «2 ••• 9пУ различны.