AOP_Tom3 (1021738), страница 34
Текст из файла (страница 34)
упр, 26), значит, мы можем выполнить умножение и сложение в формуле (49) и получить ~/т/2(я~7~ — — 'и пм + 0(п '7г)). Таким образом, — и"7»е "/г» ~" '/»[1 + г »/г + 0( -3/»)) 1 (53) 2 В действительности члены с 0 должны еще содержать дополнительно 9» в экспоненте, но из наших выкладок ясно, что величина 9» должна исчезнуть, если произвести вычисления с большей точностью.
В принципе, этот метод можно раси»ирить и вместо 0(п г7») получить О(п») при любом 1г Этот асимптотнческий ряд для г„ впервые нашли (другим способом) Мозер (Моэег) и Уаймэн (1т'ушап) [Сападйш Х МаСЛ. 7 (1955), 159-168]. Метод, использованный при выводе соотношения (53), представляет собой исключительно полезную методику аснмптотического анализа, которая была предложена П. С. Лапласом [см. Р. Б. 1 ар!асс, Мйто1геэ Асад. Всй Рапэ (1782), 1-88); она также анализируется в СМагЛ 89.4 под наименованием "ггадш8 Са11э'! Другие примеры и развитие метода, примененного для вывода формулы (53), приводятся в конце раздела 5.2.2.
УПРАЖНЕНИЯ 1. [16[ Какие диаграммы (Р,»,») соответствуют двухстрочному массиву 1234567891 ( 649571283/ в построении из теоремы А7 Какой двухстрочный массив соответствует паре диаграмм 7 7 2. [МЯ1) Докажите, что (д,р) принадлежит классу 1 относительно массива (16) тогда и только тогда, когда г равно максимальному числу индексов гц..., гп таких, что РП <Рг «'''Р =Р 96 <Чг «'''Чч ыЧ- 3. [М24] Покажите, что соответствие, определенное в доказательстве теоремы А, можно также установить,ппстроив следующую таблицу: Строка О 1 3 5 6 8 Строка 1 7 2 9 5 3 Строка 2 оп 7 оп 9 5 Строка 3 по оп 7 Строка 4 по Здесь в строках О и 1 записан заданный двухстрочный массив.
При ь. > 1 строка й+ 1 образуется из строки 1г глелующим образом. а) Присвоить р г — оп. Ь) Пусть стплбец ! — крайний слева столбец, в строке Ь которого содержится целое число < р, а соответствующее место в строке Ь + 1 не заполнено. Если такого столбца нет и р = пп, то формирование строки к+ 1 на этом завершается; если такого столбца нет и р < оп, то возвратиться к (а). с) Вставить р в столбец !' в строке к + 1, присвоить р значение элемента столбца У и строки Й и вернуться к (Ь). После того как таблица таким образом построена, строка к диш раммы Р составляется из тех целых чисел строки к этой таблицы, которые отсутствуют в строке (к+ 1); стрпка 1 диаграммы г„г строится из тех целых чисел строки О, которые находятся в столбцах, содержащих оп в строке й + 1. 4.
[МЯО) Пусть аг...а, г а,...а„— перестановка различных элементов н 1 < 1 < и. Перестановка аь .. а„-г а„аг г агэы .. а„, получающаяся из исходной, если поменять ме- стами аг г н а„называется допустимой, если либо 1) 7 > 3 и аг-г лежит между а, г и а„либо й) г < и и ауты лежит МежДУ а; г и аг. Например, в перестановке 1546837 можно выполнить ровно три допустимые замены: можно поменять местами 1 и 5, поскольку 1 < 4 < 5; можно поменять местами 8 и 3, ппскольку 3 < 6 < 8 (или 3 < 7 < 8); однако нельзя менять местами 5 и 4 или 3 и 7.
а) Докажите, что при допустимой замене не меняется диаграмма Р, которая получается из перестановки путем последовательной вставки элементов ам аз,...,а в первоначально пустую диаграмму, Ь) Обратно, покажите, что можно преобразовать одну в другую любые две перестановки, которые соответствуют одной и той же диаграмме Р, выполнив одну или более допустимых замен. [Указание. Покажите, что егти диаграмма Р имеет форму (пг, пг,..., и„,), то любую с<ютветствующую ей перестановку при помощи последовательности допустимых замен можно преобразовать в "каноническую перестановку" Р лг... Р,„... Ргг...
Рг„Рп... Ры, .] б. [МЯЯ] Пусть Р— диаграмма, соответствующая перестановке а~ аз... а„. Используя результаты упр. 4, докажите, что диаграмма Р соответствует перестановке ба„...аз аь т 6. [МЯО] (М. П. Шуценберже (М, Р. БсЬацхепбегбег).) Пусть я — ннволюцня с 9 неподвижнымн точками.
Покажите, что диаграмма, соответствующая к в доказательстве следствия из теоремы Б, содержит ровно 1 столбцов нечетной длины. 7. [МЯО) (К. Шенстед (С. Бсйевзсгб).) Пусть Р— диаграмма, соответствующая перестановке а~ аз... а . Докажите, что число сшол6цое в Р равно длине у максимальной возрастающей подпоследовательности ач < а„« . ач. где Н < ?з « г;; число справ в Р равно длине г максимальной убывающей подпоследовательности аз, > ам > >аз„,гдец <уз« . т,. 8. [М?0) (П Эрдеш (Р ЕгбЪ), Г. Секереш (С. Бяейегез).) Докажите, что в любой перестановке, состоящей нз более чем п~ элементов, имеется монотонная подпоследовательность длиной более и; однако существуют перестановки п~ элементов, не содержащие монотонных подпоследовательностей длиной более п. [Указание. См.
предыдущее упражнение.] 9. [мдз'] продолжая упр. 8, найдите "простую" формулу точного числа перестановок множества (1, 2,..., п~), не содержащих монотонных подпоследовательностей длиной более и. 10. [МЯО) Докажите, что массив Р остается диаграммой-после окончания выполнения алгоритма Б, если он был диаграммой до этого. 11. [ЯО] Можно ли восстановить исходный внд диаграммы Р по окончании выполнения алгоритма Б, если известны только значения г н з? 12. [МЯ~] Сколько раз выполняется шаг БЗ, если алгоритм Б многократно применяетсн для исключения всех элементов нз диаграммы Р формы (пипщ...,им)? Каково минимальное значение этой величины по всем формам, таким, что п~ +из+ + и = н? 13. [МЯЯ] Докажите теорему С. 14.
[ЛЦЗ[ Найдите более прямое доказательство теоремы П, п, (с). 19. [МЯО] Сколько перестановок мультнмножества (( а, гл Ь, п с) обладают следующим свойством: если читать перестановку слева направо, то число прочитанных букв с никогда не превышает числа букв В, которое, в свою очередь, не превышает числа букв а? (Например, перестановка а а б с а 6 6 с а с а обладает этим свойством.) 19. [МОЯ) Сколькими способами можно топологнчески рассортировать частичное упорядочение, представляемое графом (39)? 17. [НМЯО) Пусть 9(ям ям ° °,я», 9) я!сз(я~+9 кз ° °,к») + яз Ь(хмяз+9, я») + ° +я» Ь(хцяз,...,к„+9). Докажите, что 9(кпяг,,я», '9) = (я!+яз+ +к + (э) 9) Ь(кцхз, .,я»). [Укаэанне. Полинам д однородный (все слагаемые имеют одинаковую суммарную степень) и антисимметричный по х (знак д изменится, если поменять местами я~ и кг).] 18. [г?МУО] Обобщая упр. 17, вычислите при тп > О сумму х! Ь(Я1+9 хз ° ..
~ х ) + Яз IЬ(хм Я2+9 Я ) + ' ' '+ Я»»(кц кз Я +9) ° 19. [Мз'О] Найдите формулу для определения числа способов, которыми можно заполнить массив, подобный диаграмме, но без первых двух клеток в периой строке, например массив такой формы: п1 †2 клет пэ клеток пэ клеток (Элементы в строках и столбцах должны располагаться в порядке возрастания, как в обычных диаграммах.) Иными словами, сколько диаграмм формы (пн пэ,..., и ), составленных из элементов (1, 2,..., п1+ +и ), содержат элементы 1 и 2 в первой строке? ь 20. (МЯ4] Докажите, что число способов такой разметки узлов данного бинарного дерева элементами (1,2,...,и), чтобы метка каждого узла была меньше метки любого из его потомков, равно частному от деления и! на произведение "длин поддеревьев", т.
е. количеств узлов в каждом поддереве (см. теорему Н). Например, числа способов разметки узлов дерева равно 11!/11 4 1 5 1 2 3 1 1бо11 1 = 10 9 8 7 6 (ср. с теоремой Н). 21. (НМ31) (Р. 5Ь Тролл (К. 58 Тяга!1).) Пусть числа п~ > пэ > > п~ описывают форму "сдвинутой диаграммы", в которой строка 1+ 1 начинается на одну позицию правее, чем строка 1; например, сдвинутая диаграмма формы (7, 5, 4, 1) имеет вид Докажите, что число способов такого заполнения сдвинутой диаграммы формы (пы пэ,..., пы) числами 1, 2,..., и = и~+па+ +пы, чтобы числа во всех строках и столбцах располагались в порядке возрастания, равно частному от деления и! на произведение "длин обобщенных уголков"; на рисунке заштрихован обобщенный уголок длиной 11, соответствующий клетке строки 1 и столбца 2.
(Уголки в левой части массива, имеющей внд перевернутой лестницы, имеют форму буквы (?, повернутой на 90', а не буквы Ь.) Итак, существует 17!/12 11 8 7 5 4 1 . 9 6 . 5 3 2 5 4 2 1 1 способов такого заполнения изображенной выше формы, чтобы клементы во всех строках и столбцах располагались в порядке возрастания. 22. [МУ9) Сколькими способами можно заполнить массне формы (пп пэ... и ) элементами множества (1, 2,...,?У), если допускаюглсл одвнакоеме зле иенгнм, причем в строках элементы должны располагаться в порядке неубывш~ия, а в столбцах — только в порядке возрастания? Например, простую форму нз гл строк (1, 1,..., 1) можно заполнить ( ) способами; форму из одной строки (т) можно заполнить ( +~~ ') способами; форму (2, 2) можно заполнить -' (~эт')(э) способами.
при этом другие метки так, как в алгоритме Я, и помещая метки 1, 2, ... на освободившиеся места. Покагките, что эта операция, если ее многократно прилзенять к двойственной системе меток с обратным отношением порядка для чисел, дает исходную систему меток; исследуйте другие свойства этой операции. 31. [НМЯО] Пусть х — число способов такого размещения и взаимно неатакующих падей на шахматной доске разлзером и х и, что расположение не меняется при отражении доски относительно обеих главных диагоналей. В результате получим хл = б. (От инвалюций же требуется симметрия тазько относительно одной из главных диагоналей.
Похожая задача рассматривалась в упр. 5.1.3-19.) Найдите асимптотическое поведение хо. 32. [НМЯ1] Докажите, что 1„— среднее значение Х", если Х является нормальной случайной величиной с математическим ожиданием 1 и дисперсией 1, 33. [Мйб] (О. Митчелл (О Мйсбей), 1881.) Верно ли утверждение: Ь(аг, аг,..., о,,„)/г.'л(1, 2,..., т) является целым числом, если о.г, аг, ..., а „вЂ” также целые числа. рг » рщ, р» » р„, где1<л<и',,1<1<и,. 3 Оно же называется обратным плоским раэбиением, если вместо сформулированных выше выполняются условия где 1 < л' < и'„1 < 1' < и,. рц « рго,, рц «" ро,э Рассмотрите следующий алгоритм, который выполняет обратные плоские разбиения дан- ной формы и формирует другой массив чисел дб, имеющий ту же форму.
С1. [Инициализация.] Присвоить 9,1 о- О, 1 < 1 < и, и 1 < л < ил. Затем присвоить 1 о- 1. С2. [Поиск ненулевой ячейки.] Если ры1 ) О, присвоить г е- и1, )е о- 1' и перейти к шагу 03, В противном случае, если 1 < иг, увеличить 1 на 1 и повторить этот шаг. В противном случае остановить процесс (массив р теперь абнулен). СЗ, [Уменьшение р.] Уменьшить рел на 1.
С4. [Переход вверх или вправо.] Если л ) 1 и рн Ил > р,л, уменьшить л на 1 и вернуться к шагу СЗ. В противном случае, если )е < и„увеличить й на 1 и вернуться к шагу 63. г" б. [Увеличение 9.] Увеличить йеэ на 1 и вернуться к шагу 02. 3 Разработайте алгоритм, который восстанавливает значения р по значениям д, и тем самым докажите, что описанное выше построение определяет взаимно однозначное соответствие между обратным плоским разбиением т и ревэением уравнения где числа йб — длины уголков формы, 34. [35] (Т. Накаяма (Т. )за)еауаша), 1940.) Докажите, что если форма диаграммы включает уголок длиной аб, она содержит и уголок длиной а. о 35. [ЯО] (А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
