Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 67
Текст из файла (страница 67)
Тогда /~(х) ш 1, /ь~.~(х) ж Д /е(и)д(и,х) Ии. Здесь д(и, х) = 2 ь, ди(и,х), где д (и,ж)шрг(и<Х~< ° ° ° <Х >х или и>Х~>" >Л <х) =Рг(и <Хь « Х,ь)+Рг(Р>Хь » Хт) — Рг(и < Х~ <" <Хи <х) — Рг(и> Л, >." > Х., >х) ш (и + (1 — и) + !и — х(м)/гп! . Следовательно, д(и, х) = е" + е' " — 1 — ем Ы и шшучим /э(х) = 2е - 1 — е* — е' Можно показать, что /ь(х) стремится к предельному значеншо (2сое(х — 1) — яп1з— сое-')/(Зып3 — сое-'). Средняя длина серии, начинающейся с х, равна е'+е'-* — 1; таким обрезом, длина й-ой удаленной серии ье .равна Д' /д(х)(е* + е' ' — 1) ах; за = 2е — 3 2.43656; ьэ = Зез — 8е + 2 ж 2.42091.
Аналогичные результаты имеются в разделе 5А.1. 24. Рассуждая, как и раньше, получим в результате 1+ Х~" 2"(р'+д')е(р'+2рд(г"-'-' — 1+9'((2рд)" " ' — 1)/(2рд- ц)) е<е<ь После суммирования и упрощения получим искомую функцию 2" (р'+ д')" (р(р — д)/(р~ + д' - рд) — е ) + (2рд) "рд'/(р'+ 9~Крэ + д' — рд) + д'/(рР+ д') + 2"-'. 26. Пусть г) = (б~ + +(71) шоб 1; тогда Ьн..., 1'„— независимые равномерно распределенные числав интервале (О .. 1), образующие перестановку, которая имеет к нисходящих серий тогда и только тогда, когда (П» + + К,) = /с. Отсюда получается ответ (ь)/пй это свойство впервые обнаружил С. Тэпли (8.
Таину) (см. Рийе ИагЬ. Х 40 (1973), 717-722). 26. Например, бл(1 — з) ' = (э+ 26сз+ббл»+ 26»»+ гз)/(1 — з)е, 27. Следующее правило дает взаимно однозначное соответствие между перестановкой а, ат... а„, имеющей Ь нисходящих серий, и и-узловым разрастающимся лесом, имеющим /с+ 1 лист. Первый корень — ам а его потомки — лес, соответствующий аз... аы где й — наименьщее число, удовлетворяющее ас ю < ам или Ь = и. (К, Р, Бсап)еу, Елв»пегас»ге Со»пЬ»лагщбся 1 (ЖаовногсЬ„1986), Ргороыйоп 1.3.16.] РАЗДЕЛ Ы.б (1 3 4 5 7 8 9) 9 1 2 3 8 1 3 2.
Пусть р» — элемент столбца 1 - 1, если р, вставляется в столбец Ь Тогда (д»,р») принадлежит классу 1-1, е» < е„р» < рц таким образом, по индукции приходим к заключению, что существуют индексы гм °, Ь, обладающие нужным свойством. Обратно, если»Ь < йи р» < р, и (6». р») принадлежит классу 1 — 1, то„когда вставляется р„столбец Ф вЂ” 1 содержит элемент < р;. Таким образом, (йи р;) принадлежит классу > Ь 3. Здесь столбцы представляют собой последовательные "вытеснения" в смысле (9), которые образуются при вставке рь Строки 1 и 2 отражают операции над строкой 1 (ср, с (14)).
Если убрать столбцы, во второй строке которых стоит элемент оо, то строки 0 и 2 образуют "вытесненный" массив, как в (15). Сформулированный метод перехода от строки Й к строке Й+ 1 — это не что иное, как описанный в данном разделе алгоритм определения классов. 4. (а) Проанализируйте разные случаи, Рассмотрите сначала воздействие на строку 1 и воздействие на последовательность элементов, вытесненных из строки 1, а затем распространите анализ по индукции на диаграмму заданного размера. (Ь) При помощи допустимых обменов можно смоделировать операции алгоритма 1, представив диаграмму до и после выполнения процедуры в виде канонической перестщювки, Например, рядом допустимых обменов можно трансформировать 17 11 4 13 14 2 6 10 15 1 3 5 9 12 16 8 17 11 13 4 10 14 2 6 9 15 1 3 5 8 12 16 (см. (4) и (5)).
(см. (18) и (22)). Вытесненный двухстрочный массив имеет ровно Ф вЂ” Ь фиксированных точек, что следует из способа его формирования. Следовательно., по индукции диаграмма без ее первой строки имеет Ф вЂ” Ь столбцов нечетной длины. Таким образом, Ф элементов в первой строке приводят к появлению й столбцов нечетной длины по всем диаграммам. б. Допустимые обмены симметричны в направлении слева направо, а каноническая перестановка для Р очевидным образом переходит в Р, если вставлять элементы в обратном порядке.
6, Будем считать, что существует всего 1 классов; из них точно Ь имеют нечетное число элементов, поскольку элементы класса имеют вид 7. Число столбцов, а именно — длина строки 1, равно числу классов (упр. 2). Число строк равно числу столбцов в Рз. Далее, примемив результатм упр. 5 (илм теоремы О), завершаем доказательство. 8. Диаграмма Р, в которой содержится более пз элементов, должна иметь либо более и строк, либо более и столбцов. Однако существует м диаграмма размером и х и. [Этот результат впервые был доказан в Сошроэ)йо Магй.
2 (1935), 483-470.[ 9. Подобные перестановки облавщот взаимно однозмачным «оответствием с парами диа.- грамм вида (и, и,..., п)„таким образом, с учетом (34) ответ таков: пз! Ь(2м-1,2п-2,..., и) (' пз( (2п — Ц! (2п — 2)!... и( ) ((Зп — Ц(2п — 2)з... и" (и — Ц"-'...1 Воистину удивительно, что решением этой задачи являетея такая простая формула, Теперь можно подсчитать число перестановок (1, 2,..., тп), в которых отсутствуют возрастающие последовательности длиннее т и убывающие последовательности длмннее и.
10. Доказываем по индукции, что на шаге БЗ оба массива — и Р~„пм и Р,ы ц мезьше, чем Р<„егм и Рц„еп, 11. Разумеется, мам еще нужно знать, какой элемент был раньше на месте Рп. То- гда существует возможность восстановить исходный вид диаграммы, используя алгоритм, чрезвычайно похожий на алгоритм Б. 12, ( ) + ( ) + . + ( ) — ( ) — зто путь, пройденный в общей еложмости.
Минимальное значение равно сумме первых и членов последовательности 1,2,2,3,3,3,4,4,4,4... в упр. 1.2.4-41; эта сумма равна приблизительно /8/9пщ". (Почти для всех диаграмм из и элементов оценка значения минимума подходит очень близко к этой границе, как следует из упр.
29. Поэтому среднее число применений шага БЗ равно В( з7з) ) 13. Пусть в перестановке участвуют элементы множества (1,2,..., и), так что а; = 1, и предположим, что ат = 2. Случай 1, у' < (. Тогда 1 вмтесняет 2, а змачит, строка 1 диаграммы, соответствующей перестановке аз...а, ~ аеы ... а„, есть строка 1 в Р Я вытесненная перестановка — та же, что и прежняя вытесненная перестановка, но ее наименьший элемент теперь равен 2; результат по индукции можно расширить и на п.
Случай Я, у > й Применим результат случая 1 к Рт, приняв во внимание результат упр. 5 и тот факт, что (Рт) = (Р )т. 15. Как и в (37), приведенная в качестве примера перестановка соответствует диаграмме 5 911 7 10 следовательно, искомое число равно Щ пп и) = (1+ т+ и)! (1- т+ Ц(1 — п+ 2)(т — и+ Ц/ (1+ 2)1(т+ Ц! (и)! при уаювии, разумеется, что 1 > т > и. 18. Как следует из теоремы Н, 80 080 способами. 17.
Посхольку полинам у антисимметричен по х, он обращается в 0 при х; = хзч следовательно, он делится на х, — х при всех 1 < у. Таким образом, у(хм...,х„;у) = Ь(хм...,хп', у) Ь(хм...,х~) Здесь функция Ь должна быть однородным полимомом первой степени хм...,х,у, симметричным относительно хм...,х, так что И(хм.,,,х«, у) = а(х~ + + хе) + Ьу лля некоторых а и Ь, зависящих только от и. Можно вычислить а„ положив р = О; можно вычислить Ь, взяв частную производную по 9 и затем положив р = О. Получим д д ч 1 — 1(*н-" ж+р,",х.и,=. = — 21(*,.",*.) = Ь(,...,х.) Š— --.
эФ*' Окончательный результат таков: (х;/(х< — эд)) =,5 ~ (х'/(х ху) + хг/(ээ х')) = ( ) Фзеи 1 г<1 18. Она должна равняться гг(хн...,х„). (Ьо+Ь~р+ . +Ь„р ), где все Ьь — однородные симметричные полнномы степени гл — й от переменнык х. Имеем дь ид Ь( + )) Ь( )ЕИП ( ))' где сумма берется по всем (" ') способам выбора различнык индексов зм..., уь уэ 1. Теперь в выРажении Ьь = 2,'х, /Ц~ш,(х; — хл) можно скомбиниРовать гРУппы из Ь + 1 членов, имеюшик данный набор индексов (г', ум..., уь); например, прн Ь = 2 <группируем наборы из трех членов вида а /(о — Ь)(а — с) + Ь /(Ь вЂ” о)(Ь вЂ” с) + с /(с — а)(с — Ь). Сумма членов каждой группы вычисляется, как в узр.
1.2.3-33: (х "] 1/(1 — х,х)(1 — хп з)... (1 — хэ э). Таким образом, находка, что ) ~' э(ри р1)~ где э(рм.,.,ру) — симметричная функция, содержшная всевозможные различные одно- члены вида х',,",... х,', с различными индексами П, ..,, зэ Е (1,..., и), а внутренняя сумма берется по всем разбиениям гл — )с точно на / частей, таких, что р~ > > р > 1, р~+. +ру = т — 1с. (Этот результат получен совместно с Э, А. Бендером в 1969 гаду.) При гл = 2 ответ равен (э(2) + (и — 1) э(1) 9 + ("„)рэ) 21(хм..., х„); при гл = 3 получаем ((3)+И--» (2)+.(, ))9+(.-,') ()рэ+(;).") ~(*„.',*.')"«*' д В другом выражении Ьь представляет собой коэффициент при х"' в выражении ~Ц /э — ( /о!3 + ( /оэ ' ' ') / (1 — о!э +оэх — ), гДе а~ = 2 ',<ч «о <„хп ...
хч — элементаРнак симметРнчнав фУнкцнЯ. Умножение на 9» и суммирование по Ь дает ответ в виде коэффициента при х в вьгражении /(1+х(9 х ))'''(1+х(р х )) 1) ( ) уэ 1 (1 — ах1)... (1 — эх„) 19. Пусть транспонированная диаграмма имеет форму (и'„пэ,..., и'„); ответ будет таким: где и = 2 и, = 2 и,. (Эту же формулу можно выразить в менее симметричной форме, воспользовавшись соотношением Я 1п; = -'(и + 2 и ~).) Замечаное. В рабоге %. Ге1с, Ргос. Ашег. Масй. Яос. 4 (1933), 740-744, показано, что число способов размещения целых чисел (1,2,...,и) в массиве, который является "разностью" двух форм диаграмм (пм..., и,„) ЦП,..., 1 ) „где 0 < 1.
< и и и = 2 (пэ — 1, ), равно п(без(1/((пэ — 2) — (й — 4))!). 20. Аргумент, который был отвергнут при обсуждении теоремы Н, в данном случае спр»- ведлив — соответствующие события дсдсйюйгйкаьйа независимы. Замсчайае. Если рассмотреть все й! способов маркировки узлов, то рассмотренные здесь маркировки представляют собой маркировки, ие имеющие "инверсий". Инверсии в перестановках — это то же самое, что инверсии маркировок дерева в особых случаях, когда дерево является просто путем. (См. А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
