{l,2,...,fi} равно числу диаграмм, которые можно сформировать из элементов {1,2,..., п). Например, из {1, 2, 3, 4} можно сформировать ровно 10 диаграмм:

Это соответствует 10 инволюциям (2). Такая связь между инволюциями и диаграммами отнюдь не очевидна, и, по-видимому, не существует простого способа ее доказательства. Доказательство, которое мы обсудим, включает -интересный алгоритм построения диаграмм, обладающий и другими неожиданными свойствами; он основан на особой процедуре вставки в диаграмму новых элементов.

Предположим, например, что нужно вставить элемент 8 в диаграмму

Метод, которым мы будем пользоваться, состоит в том, чтобы сначала поместить 8 в 1-ю строку, в клетку, ранее занимаемую 9, поскольку 9 - наименьший из элементов этой строки, больших 8. Элемент 9 "вытесняется" вниз, в строку 2, где он замещает 10. Затем 10 "вытесняет" 13 из 3-й строки в 4-ю и, поскольку в 4-й строке нет большего элемента, чем 13, процесс завершается добавлением 13 в правый конец строки 4. Наша диаграмма (4) преобразовалось в

В алгоритме I содержится точное описание этого процесса и доказательство того, что он всегда сохраняет свойства диаграммы.

Алгоритм I {Вставка в диаграмму). Пусть Р = (Pij) - диаграмма целых положительных чисел, ах - целое положительное число, не содержащееся в Р. Этот алгоритм преобразует Р в другую диаграмму, содержащую х наряду с исходными элементами Р. Новая диаграмма имеет ту же форму, что и старая, но на пересечении строки S и столбца t появился новый элемент, где s иЬ - величины, определяемые алгоритмом.

(В этом алгоритме замечания в круглых скобках предназначены для доказательства его правильности, поскольку по индукции легко проверить, что эти замечания справедливы и что массив Р продолжает оставаться диаграммой на протяжении всего процесса. Для удобства будем предполагать, что диаграмма ограничена нулями сверху и слева и символами "оо" - справа и снизу, так что элемент pij определен при всех i,j > 0. Если ввести отношение

а<Ь тогда и только тогда, когда

а <Ъ или а = Ь = О, или а = Ь = оо,

то неравенства для диаграммы можно выразить в удобной форме:

pij = О тогда и только тогда, когда г = О или j = 0; piipi(}+i) и piip(i+i)3 при всех i,j > 0. Утверждение "х 0 Р" означает, что либо х = оо, либо х ф pij ни при каких i,j > 0.)

11. [Ввести X.] Присвоить г <- 1, xi х и присвоить j наименьшее значение, такое,

что pij = 00.

12. [Найти Xj+i.] (В этот момент p(i-i)j < Х{ < pij и Xj 0 Р.) Если Xj < Pi(j i), то уменьшить j на 1 и повторить этот шаг. В противном случае присвоить Xi+l i- pij nrii- j.

13. [Заменить элементом х<.] (Теперь Pt(j-i) < а;» < Xj+i = pij Pi(j+i), p(i-i)j <

Xi < Xi+i = pij < p(i+l)j КП= j.) Присвоить pij <- Xi.

14. [xi+i = 00?] (Теперь pi(j-i) < pij = Xj < Xj+i puj+i), p{i-i)j < pij = Xi < Xj+i < p(i+i)j, Ti = j и Xj+i p.) Если Xi+i Ф oo, TO увеличить г на 1 и вернуться к шагу 12.

15. [Определить s, i\ Присвоить s *г- i, t *г- j v. закончить процедуру. (К этому моменту условия

РнФ оо и p(s+i)t = ps(t+i) = оо (8)

будут вьшолнены.)

Заметим, что данный алгоритм определяет "последовательность вытеснений"

X = Xl <; Х2 < • < Xs < Xs+i - оо, (9)

а также вспомогательную последовательность индексов столбцов

гх>Г2>--->г, = 1\ (10)

при этом элемент Pir, меняет свое значение Zj+i на ж,, 1 < г < s. Например, когда в диаграмму (4) вставлялся элемент 8, последовательность вытеснения имела вид 8, 9, 10, 13, 00, а вспомогательная последовательность - 4, 3, 2, 2. Мы могли бы переформулировать алгоритм так, чтобы он расходовал меньше временной памяти (необходимо хранить только текущие значения j, х» и Xj+i); последовательности (9) и (10) были введены с той лишь целью, чтобы можно бьшо доказать некоторые интересные особенности этого алгоритма.

Основное свойство алгоритма I, которым мы не преминем воспользоваться, состоит в том, что алгоритм можно "прокрутить" в обратном направлении: по заданным S и t, определенным на шаге 15, можно привести Р к исходному виду, найдя и удалив элемент х, который был вставлен. Рассмотрим, например, (5); пусть известно, что элемент 13 занимает позицию, которая раньше была пуста. Тогда элемент 13, наверное, был вытеснен вниз из 3-й строки числом 10, потому что 10 - наибольший элемент в этой строке, меньший 13; аналогично элемент 10, по-видимому, был вытеснен из 2-й строки числом 9, которое, в свою очередь, было вытеснено из 1-й строки числом 8. Таким образом, от (5) можно вернуться к (4). В следующем алгоритме подробно описан этот процесс.

Алгоритм D {Удаление из диаграммы). По заданной диаграмме Р и целым положительным числам S, t, удовлетворяющим условиям (8), этот алгоритм преобразует Р в другую диаграмму почти такой же формы, но с оо на пересечении столбца t и строки S. Найденный при этом элемент х удаляется из диаграммы Р.

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

D1. [Ввести S, t.] Присвоить j <-t,i<- s, Xs+i <- оо.

D2. [Найти а:».] (В этот момент pj < Xi+i < p(i+i)j и Xi+i p.) Если Pnj+i),< Xj+i, то увеличить j на 1 и повторить этот шаг. В противном случае присвоить Xi <- pij кп<- j.

D3. [Заменить элементом Xj+i.] (Теперь pi{j-i) < pij = < Xj+i pj+i),

p[i-l)j < pij Xi< Xi + i < p(i+l)j и Ti = j.) Присвоить pij <- Xi+1.

D4. [i = 1?] (Теперь puj-i) < Xi < Xi+i = pij < pi(j+i), p{i-i)j < Xi < Xi+i = pij < p{i+i)j и Tj = j.) Если i > 1, TO уменьшить i на 1 и вернуться к шагу D2.

D5. [Определить х.] Присвоить х <- xi п закончить процедуру. (Теперь О < х <

00.) I

Пояснения к алгоритмам I и D, заключенные в круглые скобки, не только полезны для доказательства того факта, что эти алгоритмы сохраняют структуру диаграммы, но и позволяют убедиться, что алгоритмы I и D взаимно обратны. Если сначала выполнить алгоритм I с данной диаграммой Р и некоторым целым положительным числом х Р, то он вставит х в Р и определит целые положительные числа S, t, удовлетворяющие условиям (8). Алгоритм D, примененный к полученному результату, восстановит значения х и первоначальный вид Р. Обратно, если сначала выполнить алгоритм D с данной диаграммой Р и некоторыми целыми положительными числами s, t, удовлетворяющими условиям (8), то он модифицирует Р, удалив некоторое целое положительное число х. Алгоритм I, примененный к полученному результату, восстановит значения s,t и первоначальный вид Р. Дело в том, что присвоения, приведенные в заключенных в скобки пояснениях к шагам 13 и D4, равно как и к шагам 14 и D3, совпадают и однозначно определяют значение j. Следовательно, вспомогательные последовательности (9), (10) одинаковы в обоих случаях.

Теперь мы подготовлены к доказательству основного свойства диаграммы.