Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 19
Текст из файла (страница 19)
Строка 3 оо 7 Строка 4 оо Здесь в строках О и 1 записан заданный двухстрочный массив. При й > 1 строка 5+ 1 образуется из строки к следующим образом. а) Присвоить р е- оо. Ь) Пусть столбец у — крайний слева столбец, в строке й которого содержится целое число < р, а соответствующее место в строке Ь + 1 пе заполнено, Если такого столбца нет и р ы оо, то формирование строки л+ 1 на этом заверюается; если такого столбца нет и р < со, то возвратиться к (а). с) Вставить р в столбец 7' в строке Ь + 1, присвоить р значение элемента столбца у и строки й и вернуться к (Ь), После того как таблица таким образом построена, строка л диаграммы Р составляется из тех целых чисел строки Ь этой таблицы, которые отсутствуют в строке (к + 1); строка Ь диаграммы Я строится из тех целых чисел строки О, которые находятся в спхзбцах, содержащих оо в строке й + 1.
4. (МЗО) Пусть о|... ау г о,... а„— перестановка различных элементов и 1 < у < и. Перестановка аг... Оу г аз аз г а, ем .. а„, получающаяся нз исходной, если поменять местами а, г и аг, называется допустимой, если либо !) у > 3 наг-г лежит между а 1 на., либо й) у < и па,е; лежит межлу а, г н о, Напргьмер, в перестановке 1546837 можно выполнить ровно три допустимые замены'. можно поменять местами 1 н 5, поскольку 1 < 4 < 5; можно поменять местами 8 и 3., поскольку 3 < 6 < 8 (нли 3 < 7 < 8): однако нельзя менять местами 5 и 4 нли 3 и 7. а) Докажите, что прн допустимой замене не меняется диаграмма Р, которая получается из перестановки путем последовательной вставки элементов аы аг,..., а, в первоначально пустую диаграмму, Ь) Обратно, покажите, что можно преобразовать одну в другую любые две перестановки, которые соответствуют одной н той же диаграмме Р, выполнив одну или более допустимых замен.
[Указание. Покажите, что если диаграмма Р имеет форму (и ы пг,, п ), то любую соответствующую ей пересчвновку прн помощи последовательности допустимых замен можно преобразовать в "каноническую перестановку" Р г" Р~п . Ргг, Рг,гРп."Ры,) б. [М22] Пусть Р— диаграмма, соответствующая перестановке а~ аэ... а„.
Используя результаты упр. 4, докажите, что диаграмма Р соотяетсгяует перестановке ба„... аэ аэ. 6. [МЯО] (М. П. Шуценберже (М, Р. БсЬаеэепЬегбег).) Пусть я — ннволюцня с Ь неподвижными точками. Покажите, что диаграмма, соответствующая я в доказательстве следствия нз теоремы В, содержит ровно 1" столбцов нечетной длины. 7. [МЯО) (К. Шенстед (С. БсЬепэсед).) Пусть Р— днаграмма, соответствующая перестановке аэаз.,. а . Докажите, что число сшолбцое в Р равно длнне 8 максимальной возрастающей подпоследовательностн он < а,э « и;„где П < зэ « ° . (,; число строя в Р равно длине г максимальной убывающей подпоследовательности а, > аз > > аз„, где и < уэ « .
8 . 8. [М18] (П. Эрдеш (Р. Епйэ), Г. Секереш (С. Бяеуегеэ).) Докажите, что в любой перестиювке, состоящей яз более чем и элементов, имеется монотонная подпоследовательность длиной более и; однако существуют перестановки п элементов, не содержицне монотонных подпоследовательностей длиной более и. [Уюианне. См. предыдущее упражнение.) 9. [МЯ8] Продолжая упр. В, найдите "простую" формулу точного числа перестановок множества (1, 2,..., пэ), не содержащих монотонных подпоследовательностей длиной более и.
19. [МЯО] Докажите, что массне Р остается диаграммой-пекле окончания выполнения алгоритма Б, если он был диаграммой до этого. 11. [80] Можно лн восстановить исходный вид диаграммы Р по окончанви выполнения алгорнтма Б, если известны только значения г и э? 12. [М88] Сколько раз выполняется шаг БЗ, если алгоритм Б многократно применяется для нсключення всех элементов нз диаграммы Р формы (пы пэ,..., пм)? Каково миннмальное значение этой величины по всем формам, такнм, что п~ + па + . + и,„= и? 13. [М88] Докажите теорему С. 14.
[М88] Найднте более прямое показательство теоремы П, п. (с). 16. [Муд] Сколько перестановок мультнмножества (( ° а, гл Ь, п ° с) обладают следующим свойством: еслн читать перестановку слева направо, то число прочитанных букв с никогда не превышает числа букв Ь, которое, в свою очередь, не превышает числа букв а? (Например, перестановка а а Ь с а Ь Ь с а с а обладает зтнм свойством.) 16. [М08] Сколькими сцособамн моною топологнчески рассортировать частичное упорядоченна, представляемое графом (39)? 17.
[НМ88] Пусть 8(хм хе,. ° ° хя~ у) ж х~ Ь(к~+у,хэ, ° ° ° ~ха)+ хам(хмхэ+у~ ° ° ~хе) +".+х Ь(хмхэ,...,х,+у). Докажите, что 8(хмхэ,.",хя, у) = (ха+ля+" +хе+ [я)у) Ь(хмхэ,...,хя), [Указанпе. Поляком 0 однородный (все слагаемые имеют одннаковую суммарную степень) н антнснмметрнчный по х (знак 8 изменится, если поменять месщми х; и х;).] 16. [ВМ80] Обобщая упр. 17, вычислите при гл > 0 сумму х,"с1(я~+у,хэ,...,х„)+хэ" Ь(хпхэ+у,...,х„)+" +х„с1(хмхэ,...,х„+у). 19.
[М80) Нейдите формулу для определения числа способов, которыми можно заполнять массив, подобный диаграмме, но без первых двух клеток в первой строке, например массив такой формы: п~ — 2 клеток пэ клеток цз клеток (Элемеиты в строках и столбцах должны располагаться в порядке возрастания, как в обычных диаграммах, ) Иными словами, сколько диаграмм формы (пм пэ,..., и ), составлеиных из элементов (1,2,...,ц~+ +и ), содержат элемепты 1 и 2 в первой строке? ь 20. (5494) Докажите, что чисэо способов такой разметки узлов данного бинарного дерева элементами (1„2,...,и), чтобы метка каждого узла была меньше метки любого из его потомков, раино часгному от деления и! на произведение "длин поддеревьев", т, е. количеств узлов в каждом поддереве (см. теорему Н).
Например, число способов разметки узлов дерева равно 11) / 11 . 4 1 5 1 . 2 3 . 1 . Цог1 . 1 = 10 9 8 ° Т 6 (ср. с теоремой Н). 21. (Т?М31] (Р. М. Тролл (К. М. 'ГЬгаП).) Пусть числа п~ > пэ > " > п~ описывают форму "слвииутой диаграммы'! в которой строка 1+ 1 начинается па одну позицию правее, чем строка 1; нэцример, гдвииутвя диаграмма формы (Т, 5,4, 1) имеет вид Докюките, что число способов такого заполпепяя сдвииутой диаграммы формы (цм пэ, и ) числами 1, 2,..., и = им+па+ +и „чтобы числа во всех строках и столбцах располагались в порядке возрастаиия, равно частному от деления и! на произведение "длин обобщенных уголков"; на рисукке заштриховал обобщеипый уголок длиной 11, соответствующий клетке строки 1 и столбца 2.
(Уголки в левой части массива, имеющей вид перевернутой лестницы, имеют форму буквы П, повернутой на 90', а не буквы Ь.) Итак, существуег 17!/12 11 8 7 5 4 1 9 б 5.3.2 5 4 ° 2 1.1 способов такого заполнения изображенной выше формы, чтобы элементы во всех строках и столбцах располагались в порядке возрастания. 22. [МЯУ) Сколькими способами можно заполнить массив формы (пм пэ,..., и,„) элементами множества (1,2,..., Х), если допрскаюшсл одииахоеме элеменшм, причем в строках элементы должны располагаться в порядке неубываиия, а в стсшбцах — только в порядке возрастания? Например, простую форму из т строк (1,1,...,1) можно заполнить ( ) способами; форму из одной строки (гл) можно заполнить ( +л ') способами; форму (2,2) можно заполнить -' (л~+') (лэ) способами.
при этом другие метки так, как в алгоритме Я, и помещая метки 1, 2, ... на освободив»пиеса места. Покажите, что эта опере»шя, если ее многократно применять к двойственной системе меток с обраткым отношениел» порядка для чисел, дает исходную систему меток; исследуйте другие свойства этой операции. 31, [НМЯО) Пусть х„— число способов такого размещения и взаимно неатакующих падей на шахматной доске размером и х и, что расположение не меняется прн отражении доски относительно обоих главных диагоналей.
В результате получим х» = 6. (От инволюций же требуется симметрия только относительно одной из главных днш оналей. Похожая задача рассматривалась в упр. 5.1.3-19.) Найдите асимптотическое поведение х . 32. (НМ21) Докажите, чт— среднее значение Х", если Х является нормальной случайной величиной с математическим ожиданием 1 и дисперсией 1.
33. (Мйб) (О. Митчелл (О. У!!»с!»с!!), 1881,) Верно ли утверждение: »х(а»,аэ,...,а )/»х(1,2,...,т) является целым числом, если а», аи ..., аи — также целые числа. 34. (9б) (Т. Накаяма (Т. »4а)шуаша), 1940,) Докажите, что если форма диаграммы включает уголок длиной аб, она содержит и уголок длиной а. ь 35. (уд) (А. П.
Хиллман (А. Р. Н»!!шаи) н Р, М. Грасса (К. Ы. Сгаш!), !976.) Размещение неотрицательных целых чисел р» по ячейкам диаграммы, которая имеет и, ячеек в строке » и и'. ячеек в столбце у, называетгл плоским разбиением»и, если ~" р„= ш и где 1 <» < и',, 1 < у < и». рц »" р,.». Оно же называется об!и»икмм и юским !избиением, если вместо сформулированных выше выполняются условия где 1<» < и», 1<1 < и». ри «''" р»а»» РМ « ' Рэ»»» Рассмотрите следующий алгоритм, который выполняет обратные плоские разбиения дан- ной формы н формирует другой массив чисел 99, имеющий ту же форму. 01.
(Инициализация.) Присвоить 9», »- О, 1 < б < и» и 1 <» < и», Затем присвоить 1»-1. 03. (Поиск ненулевой ячейки.) Если р„, > О, присвоить»»- и»», й»- у и иервйти к »» шагу 03. В цротивиом случае, вски у < и», увеличить у на 1 и повторнть этот шаг. В противном случае остановить процесс (массив р теперь обнулен). 03.
(Уменьшение р,) Уменьшить рм на 1. 04. (Переход вверх или вправо,] Если» > 1 и р»» це > рм, уменыпить 4 иа 1 и вернуться к шагу 03, В протявном случае, если й < и», увеличять й на 1 и вернуться к шагу 03. Сб. [Увеличение 9.) Увеличить 99 на 1 и вернуться к шагу 02. ! Разработайте алгоритм, который восстанавливает значения р по значениям 9, и тем самым докажите, что описанное выше построение определяет взаимно однозначное соответствие между обратным плоским разбиением т и реп»синем уравнения ги = ~ Ь»уй»», где числа ЬП вЂ” длины уголков формы.
36. [УУМ37] (Р. П. Стэнли (И. Р. Бгаг»!еу), 1971.) (а) Докажите, что количество обратных плоских разбиений ш на данной форме равно [з" ] 1/ ] ](1 — х " ), где чигла Ь;, — суть длины уголков формы. (Ь) Выведите из этого результата теорему Н. [Указание. Задумайтесь, к чему асимптотически приближается количество разбиений при и» -» ж.] 37. [М39] (П.
А. Мак-Магон, 1912.) Какова ироизводяшан функция для любого плоского разбиения7 (Коэффициент при г должен быть общим числом разбиений т, если форма диаграммы неогранпченна.) ° 38. [МУО] (Грин (Сгеепе), Ниенхыоз Щ)еп!»и!з), Вильф (»!Г(!У), 1979.) Можно построить прямой ациклический граф на ячейках Т любой данной формы диш рампы связующим образом. Пусть дуги исходят из каждой ячейки к другим ячейкам в этом уголке; внешняя степень ячейки (»,у) будет тогда»Уо = Ьо — 1, где ЬЬ равно длине уголка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
