AOP_Tom3 (1021738), страница 32
Текст из файла (страница 32)
[Сдвиг вверх.) Присвоить Р„, < — Р<,+мм г <- г+ 1 и вернуться к шагу Я2. $ Легка доказать, что после удаления с помощью алгоритма Я углового элемента Р по-прежнему является диаграммой (см. упр. 10). Таким образом, применяя алгоритм Я до тех пор, пока Р не исчерпается, можно прочитать его элементы в порядке возрастания. К сожалению, этот алгоритм сортировки оказывается ие столь эффективным, как другие алгоритмы, которые нам еще предстоит рассмотреть.
Минимальное время его работы пропорционалыю и'г; аналогичные алгоритмы, использующие вместо диаграмм деревья, затрачивают время порядка и 1ойп. Хотя алгоритм Я в приложении к сортировке и не отличается особой эффективностью, он обладает некоторыми очень интересными свойствами.
Теорема С (М. П. Шуценберже (М. Р. ЯсЬйггепЬегйег)). Если Р— диаграмма, построенная, как в теореме А, нз перестановки а1 ат... а„, я если а; = пнп(аыаг,...,а„), то алгоритм Я преобразует Р в диаграмму, соответствующую перестановке ам, . а; а;~.ы .. а„. Докаэагвельсвтвв. См. упр. 13. $ Давайте после применения ътгорнтма Я поместим на вновь освободившееся место Р„, удаленный элемент, но отобразим его курсивом, указав таким образом, что на самом деле элемент не является частью диаграммы.
Применив, например, эту процедуру к диаграмме (25), мы получим а выполнив такую же процедуру еще два раза, получим Продолжая до тех пор, пока все элементы не будут удалены, получим конфигурацию (26) имеющую ту же форму, что и исходная диаграмма (25). Эту конфигурацию можно назвать деойсгпвенной диаграммой, потому что она похожа на диаграмму с той лишь разницей, что применяется "двойственное отношение порядка" (> и ( поменялись ролями). Обозначим двойственную диаграмму, полученную из Р таким способом, через Рз. Диаграмма Р определяется из Рв единственным образом. В самом деле, исходную диаграмму можно получить из Рв при помощи того же алгоритма, но изменив на обратные отношения порядка и роли обычных и представленных курсивом элементов, поскольку Рз — двойственная диаграмма. Например, применив к (26) два шага этого алгоритма, получим В конце концов, опять получается диаграмма (25)! Этот замечательный резуль- тат — одно из следствий нашей следующей теоремы.
Теорема О (К. Шенстед (С. БсЬепвсеп), М. П. Шуценберже (М. Р. БсЬйсхепЬегкег)). Пусть (27) представляет собой двухстрочный массив, соответствующий паре диаграмм (Р, Д). а) Если пользоваться двойственным (обратным) отношением порядка для о, но не для р, то двухгтрочный массив (а а а) (28) соответствует паре (Рт, ЯЗ)т). Как обычно, через "Ти обозначена операция транспонирования строк и столбцов; Р— диаграмма, а (Я ) — двойственная диаграмма, поскольку элементы о т, эт расположены в обратном порядке. Ь) Если пользоваться двойственным отношением порядка для р, но не для д, то двухстрачный массив (27) соответствует паре ((Рь)т, Я~). с) Если пользоваться двойственным отношением порядка как для р, так и для 9, то днухстрочный массив (28) соответствует паре (Р, (гл).
Доказашельсшво. Простое доказательство этой теоремы неизвестно. То, что случай (а) соответствует паре (Р, Х), где Х вЂ” некоторая двойственная диаграмма, доказано в упр. 5: следовательно, по теореме В случай (Ь) соответствует паре (У, Я~) для некоторой двойственной диаграммы У и У должна иметь ту же форму, Р . Пусть р, = ппп(рм..., р„) ', так как р, — "наибольший" элемент при двойственном отношении порядка, то он оказывается на границе У и не вытесняет никаких элементов при построении из теоремы А.
Таким образом, если последовательно вставлять элементы рм, .., р; бр;~~,..., р„, применяя двойственное отношение порядка, то получится У вЂ” (р ), т. е. У, из которой удален элемент рь Па теореме С, если последовательно вставлять элементы ры.,., р; ы р,+~,..., р„, применяя обычное отношение порядка, построим диаграмму фР), которая получаетгя путем применения к Р алгоритма Б. Индукция по и дает У вЂ” (р,) = (й(Р)з)т.
Но поскольку (Рэ) — (р1) = фР)~)т (29) по определению операции 5, а У имеет ту же форму, что и (Р )т, должно иметь место равенство г = (Рэ)т. Тем самым доказано утверждение (Ь); (а) получается в результате применения теоремы В. Последовательное применение (а) и (Ь) показывает, что случай (с) соответствует паре (((Рт)э)т,((чэ)т)т), а это равно (РЯ,Яэ), так как (Р ) (Рт)э вследствие симметрии операции Я по отношению к строкам и столбцам.
э Этв теорема, в частности, устанавливает два удивительных факта, касающихся влгоритмй вставки в диаграмму. Если в результате последовательной вставки различных элементов ры...,р„в пустую диаграмму получается диаграмма Р, то в результате вставки этих элементов в обратном порядке, р„,...,ры получится шранспонированная диаграмма Рт. Если же мы не только станем вставлять элементы в порядке р„,...,рм но и поменяем ролями > и (, а также 0 и оо, то получим двойственную диаграмму Рэ.
Настоятельно рекомендуем читателю проанализировать эти процессы самостоятельно на нескольких простых примерах. Необычная природа этих совпадений может вызвать подозрение о вмешательстве каких-то потусторонних сил. До сих пор неизвестно какое-либо простое объяснение подобных явлений; кажется, не существует простого способа доказать даже то, что случай (с) соответствует диаграмме той же формы, что и Р и Я, хотя метод характеристики классов, использованный в упр.
2, может послужить отправной точкой для дальнейших поисков. Соответствие, устанавливаемое теоремой А, было найдено Ж. Б. Робинсоном (О. де В. КоЬ1пэоп) (Атех7сап и. МагЬ. 60 (1938), 745-760, эб) в несколько иной и довольно туманной форме как часть решения весьма сложной задачи из теории групп.
Он сформулировал теорему В беэ доказательства. Много лет спустя К. Шенстед независимо заново открыл это соответствие, которое сформулировал в терминах "вытеснения", т. е., по существу, в той же форме, которую использовали мы в алгоритме 1.
Шенстед также доказал часть теоремы Р (а), касающуюся пРп (см. Саладьал д. Ма112. 13 (1961), 179 — 191). В работе М. П. Шуценберже [МаВ1. Ясшьд. 12 (1963), 117 — 128) доказана теорема В и пОп-часть теоремы Р (а), из которой следуют (Ь) и (с). Это соответствие можно распространить и на перестаьювки мультимноэьсеств; случай, когда рь,...,р„необязательно различны, рассмотрел Шенстед, а пмаксимальноеп обобщение, когда и р, и д могут содержать повторяющиеся элементы, исследовано Кнутом (Расьбс д. Маь11. 34 (1970), 709-727].
Обратимся теперь к родственному вопросу: сколько диаграмм, составленных иэ элементов (1,2,...,П), имеют данную форму (пь,пг,...,пп,), где пь+ пг+ + п = и? Обозначим это число через 7(пь, пг,..., п ); если параметры й произвольные целые числа, то функция 7' должна удовлетворять соотношениям Дпь,пг,...,и ) = О, если не пь > пг » . Пп, > 0; (30) Дпь)пг)...)П,О) = У(пь)пг,,п„,); ,ь (йь) П2,..., Пт) — ф(П1 — 1) П2 ° й)п) + ь (й!,П2 — 1) .. ° ) Пп)) (31) + ' '+ )'(пь)112) ° ° .) Пп) — 1), если и, >пг» п,„>1.
(32) Рекуррентььое соотношение (32) вытекает из того факта, что при удалении из диаграммы наибольшего элемента всегда снова получается диаграмма; например, количество диаграмм формы (6, 4, 4, 1) равно /(5, 4, 4, 1) + ь'(6, 3, 4, 1) + 2'(6, 4) 3, 1) + ь(6, 4, 4, 0) = /(5, 4, 4, 1)+Д6„4, 3, 1)+ь(6, 4, 4), потому что всякая диаграмма формы (6,4,4, 1) из элементов (1, 2,..., 15) получается в результате вставки элемента 15 в подходящее место в диаграмме формы (5,4,4, 1), (6,4,3, 1) или (6,4,4). Изобразим это схематично: + (33) 15 Функция ь'(пь,пг,...,п ), удовлетворяющая таким соотношениям, имеет довольно простой вид: Ь)Ь(йь+ т — 1, Пг+т, — 2,..., Пп))ПЬ ь(йь,пг,...,п )— (п1 + т — 1)! (112 + т — 2)! ...Пп,! (34) при условии, что соблюдается соотношение пь + т — 1 > пг + т, — 2 » пп,.
Здесь через А обозначена функция "квадратный корень из дискриминантап юп — 1 т — 1 п~-1 х 1 Х2 ''' Хп~ А(х1,хг,...,х ) = 1!еС 2 2 2 = Ц (х; — хг). (35) 1<!С!Сла Х1 Хг е$ 1 1 ... 1 Формулу (34) вывел Г. Фробениус (см. С. ЕгаЬеп1пг Ясхипягбег!сйсе ргеид. Анас!. г!ег 121гзепгсЛайеп (1900), 516-534, 23), изучая зквивалентную задачу теории групп; он использовал довольно глубокую аргументацию, опирающуюся на теорию групп. Комбинатарное доказательство независимо нашел Мак-Магон [см. МасМаЬоп, РЬ1- !огарЬ!са! 7?апг. А209 (1909), 153-175). Эту формулу можно доказать по индукции, так как (30) и (31) доказываются без труда, а формула (32) получается, если положить у = -1 в тождестве из упр. 17.
Из теоремы А в связи с втой формулой для числа диаграмм вытекает замечательное тождество. Взяв сумму по всевозможным формам диаграмм, получим 1((11~ (С2 " ) (Сп) 1,>ь.й йь„>о Й~ Тгв+ -+Ь =и 22(К1 + и — 1, (22 + и — 2, ..., Йп) (!г + — 1)12(й +п — 2)12 Ь М Ь,>Ь,> ->1„>О ЬЮ+йг ~- сйг„=П А(41,92,",9.)' д 12 д 12 9 12 ю >г » " д.
>о Е+гп+ "и'-г =1п+11п/2 12 отсюда 2 Е ~(21~ Ч2~ ° ° ° ! Яп) (36) 91)~92'2 Чп'2 В~-гп+".+г.п(п~-пп!2 м,м,,г. >о В послеДней срмме отсУтствУют неРавенства 91 > 92 ) > дп, патомУ что слагаемые — симметричные относительно д функции, которые обращаются в 0 при Ф = щ. Аналогичное тождество появляется в упр. 24. Формулу для числа диаграмм можно представить в более привлекательной форме, если ввести понятие пугалак'. В уголок, соответствующий клетке диаграммы, входит сама зта клетка плюс все клетки, расположенные в той же колонке снизу и в той же строке справа от нее.
Например, заштрихованный участок на рис. 5 — зта уголок, соответствующий клетке (2,3) строки 2 и столбца 3; он состоит из шести клеток. В каждой клетке на рис. 5 записана длина соответствующего ей уголка. если диаграмма имеет форму (п1, иг,..., и,„), то длина самого длинного уголка равна п1 + 1п — 1. Дальнейший и1ализ длин уголков показывает, что строка 1 содержит все длины п1+т — 1, и, +т — 2, ..., 1, кроме (п1+т — 1) — (и,„), (и1+1п — 1)— (и„, 1+1), ..., (п1+т — 1) — (пг+1п — 2).
Например, на рис. 5 длины уголков в 1-й строке суть 12, 11, 10,..., 1, за исключением 10, 9, б, 3, 2; эти исключения соответствуют пяти несуществующим уголкам, начинающимся в несуществующих клетках Рис. 5. Уголки и длины уголков. (6,3), (5, 3), (4, 5), (3,7), (2,7) и заканчивающимся в клетке (1, 7). Аналогично у-я строка содержит все длины уголков о +т — 7', ..., 1, кроме (п +т — 7) — (и ), ..., (пу+т —,1) — (огеэ+т — 1' — 1). Отсюда следует, что произведение длин всех уголков равно (ос+со — 1)1(пэ+т — 2)!...о„,! Л(о~ + т — 1, ох+ т — 2,..., о ) ' Это выражение входит в формулу (34).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
