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