AOP_Tom3 (1021738), страница 35
Текст из файла (страница 35)
П. Хиллман (А. Р. Н1йшап) и Р. М. Грассл (Н. М. СгазоЦ, 197б.) Размещение неотрицательных целых чисел р, по ячейкам лиаграммы, которая имеет и, ячеек в строке л и и', Ячеек в столбце 1, называетсЯ плоским Разбиением т, егзи 2 Ро = т и Зй. [НМв7] (Р. П. Стэнли (В. Р. Бсап1еу), 1971.) (а) Докажите, что количество обратных плоских разбиений т наданной форме равно [з ]1/[[(1 — з"'), где числа Ьп — сутьдлины уголков форл»ы. (Ь) Выведите из этого результата теорему Н.
[Указание. Задумайтесь, к чему асимптотически приближается количество разбиений при и» -э оо,] 37. [М90] (П. А. ЬЛак-ЬЛагон, 1912.) Какова производящая функция для любого плоского разбиения? (Коэффициент при г должен быть общим числом разбиений т, еети форл»а диаграмлгы неограниченна) ь 38. [МЯ0] (Грин (Сгеепе), Ниенхьюз (Ь911епйшэ), Вильф (11311), 1979.) Гйожно построить прямой ациклический граф на ячейках Т любой данной формы диаграммы следующим образом. Пусть дуги исходят из каждой ячейки к другим ячейкам в этом уголке; внешняя степень ячейки (Л,У) будет тогда 4, = Ьч — 1, где Ьо равно длине уголка Предположим, мы построили некоторый случайный путь на этом диграфе, выбрав случайным образом начальную ячейку (К/), и случайно выбирали гтедующие дуги до тех пор, пока не оказались в угловой ячейке, из которой нет выхода. Каждый случайный выбор выполняется равновероятно. а) Пусть (а, Ь) - - угловая ячейка Т и пусть 7 = (Ло,..., Л») и э' = (Ло, .д) .
— множества строк и столбцов, причем Ло « . 1» = а и /о « 7~ = Ь. Диграф содержит ( ) путей, множества строк и столбцов которых суть 7 и э; пусть Р(7, 1) -- веро- »~! ятность выбора определенного случайного пути Докажите, что Р(А з) = 1/(и 0м»... г(м-~»0 ~о ..0 л-~), где и = [Т] Ь) 11усть /(Т) = и!/ [ [ Ь„. Докажите, что г тучайный путь завершается в угловой ячейке (а, Ь) с вероятностью /(Т 1 ((а., Ь)))//(Т).
с) Покажите, что результат (Ь) доказывает теорему Н и предоставляет способ формирования случайной диаграммы формы Т, причем все диаграммы /(Т) равновероятны. 39. [МЯ8] (И. М. Пак, А. В. Стояновский, 1992 ) Пусть Р— — массив (пп, и,„), который заполнен некоторой перестановкой множества целых чисел (1,...,и), и = и, + + и,„. Следующая процедура, которая аналогична алгоритму 'просеивания", описанному в разделе 5.2.3, может быть использована для преобразования Р в диаграмму.
Она также определяет массив»7 такой же формы, который может послужить для комбинаторного доказательства теоремы Н Р1. [Цикл по (Пу).] Выполнить шаги Р2 и РЗ для каждой ячейки (К/) массива в обратном лексикографическом порядке (т. е. снизу вверх и справа налево в каждой строке), затем прекратить выполнение процедуры РЗ.
[Обработать Р в (1,7).] Присвоить К»- Р„. и выполнить алгоритм Я' (см. виже). РЗ. [Изменение Я] Присвоить Я»»- Л3ц»»В+1 для 1 < Ь < э и присвоить Ям»-Л-г. 1 Ниже описан тот же алгоритлб что и алгоритм Я Шуценберже, ио шаги 91 и 52 слегка модифицированы — распространены на более обп»ий случай.
Я1~. [Инициализация.] Присвоить г»-1, з»-/л БЗ'. (Выполнено?) Если К < Рй„.ц, и К < Рц,„ц, присвоить Р„, +- К и завершить процесс, (Алгоритм Б предполагает особый случай: 1 = 1, 7' = 1, К = оо.) Например, алгоритм Р обрабатывает массив формы (3,3, 2) следующим образом, егти просматривать содержимое массивов Р и Я в начале каждого шага Р2, причем значения Р„выделены полужирным шрифтом: -1 Π— 1 о Окончательный результат имеет вид а) Если Р— это просто массив 1 х и, алгоритм Р сортирует его и превращает в Какой вид при этом будет иметь массив Я? Ь) Ответьте на тот же вопрос, но в случае, если Р имеет вид и х 1, а ие 1 х и.
с) Докажите, что в общем случае получим -Ьо < до < где Ьо — число ячеек, расположенных ниже ячейки (г) У), и гц — число ячеек справа от нее. Таким образом, число возможных значений Оп в точности равно йц размеру (г, ))-го уголка. й) Теорема Н будет доказана по построению, если мы сможем показать, что алгоритм Р определяет однозначное соответствие между гй способами заполнения исходной формы н парами результирующих массивов (Р, Я), где Р сеть диаграмма, а элементы в сг' удовлетворяют условиям п. (с). Значит, желательно найти процедуру, обратную алго- О -1 ритму Р. Для каких исходных перестановок алгоритм Р сформирует массив сг' = (е е ) формы 2 х 2? е) Какую исходную перестановку алгоритм Р преобразует в массивы Г) Разработайте алгоритм, обратный по отношению к атгорнтму Р, задавая любую пару массивов (Р, О), таких, что Р— диаграмма, а Я удовлетворяет условиям п, (с).
(Указание. Постройте ориентированное дерево, першины которого — ячейки (1,у), а дуги— (г,у) -> (1,2 — 1), если Р,б ц > Рп-,у', (1,у) — > (1 — 1,у), если РП, ц < Рр цр В примере (е) мы имеем дерево Его составные злементы и представляют собой ключ к обращению алгоритма Р.] 40. ]НМЯЯ] Предположим, что некоторая диаграмма Юнга построена путем последовательного размещения чисел 1, 2,, и таким способом, что выбор очередной доступной ячейки для каждого следующего числа равновероятен. Например, с вероятностью -, '.
-' — — — так будет получена диаграмма (1). 1 1 1 1 1 1 1 1 г 1 г 1 1 2 3 3 3 4 3 3 4 4 е 4 е 4 Докажите, что с большой вероятностью результирующая форма (пц пш..., и ) будет иметь т = ~/бп пи ь/й + ъ/пь,гг ш ~/т при 0 < к < т. 41. ]25] (Беспорядок е библиотеке.) Некоторые бестолковые читатели часто возвращают книги в библиотеку и ставят их на полки где попало.
Измерить вносимый при етом беспорядок можно, рассмотрев минимальное количество повторений простейшей процедуры перемещения данной книги, которое необходимо лля того, чтобы все книги заняли надлежащие им места. Пусть я = аг аз .. о„— перестановка множества (1,2,...,гг). Операция удаления- вставки превращает и в аш..а; га,.г~...аза,а~~гг...а или аг...о,а;аег...а, гаг ш..а„ для некоторых Ь и Я. Пусть дбе(гг) — минимальное число операций удаления-вставки, которое рассортирует к и приведет его в порядок, Можно ли выразить дйз(к) в терминах простых характеристик я? ь 42. ]Яд] (Беспорядок генов.) Молекула ДНК растения Бобейа тегеепе имеет гены в последовательности дг дг дед4дедзде, где дг обозначает отражение шгева направо дп Те же самые л л л гены существуют и в табаке, но в порядке дгдедэдедедедг. Покажите, что для того, чтобы получить из дгдедздвдедедг последовательность дг дгдедедедзде, необходимо пнть операций л л 'перебрщ;ывания" подцепочек.
(Операция перебрасывания превращает оду в цДн у, если и, Ь) и у явлнются цепочками.) 43. (Яб] Продолжая предыдущее упражнение, покажите, что по крайней мере я+1 операций перебрасывания необходимо для сортировки любого варианта компоновки дгдз... д . Постройте примеры, которые требуют п + 1 операций для всех и > 3. 44. [МЯ7] Покажите, что среднее число перебрасываний, необходимых для сортировки случайной компоновки и генов, больше, чем ц — Н, если все 2" гй компоновок генов равновероятны.
5.2. ВНУТРЕННЯЯ СОРТИРОВКА Нячням обсуждение "хорошего" пропесса сортировки с маленького эксперимента. Как бы вы решили следуюгцую задачу программнрованияу "В ячейках памяти й+1, й+2, й+3, й+4 и й+5 содержится пять чисел. Напишите программу, которая переразмещает, если нужно, эти числа так, чтобы они расположились в порядке возрастания." (Если вы уже знакомы с какими-либо методами сортировки, постарайтесь, пожалуйста, на минуту забыть о них; вообразите, что вы решаете такую задачу вперные, не имея никакого представления атом, как к ней подступиться.) Преэгсдс чем читать дальше, насгпояпгельно просим оас ггайти хоть какое- нибудь решение этой задачи.
Время, затраченное на решение приведенной выше задачи, окупится с лихвой, когда вы продолжите чтение этой главьг. Возможно, ваше решение окажется одним из следующих. А. Сортировка мспгодом вставок. Элементы просматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. ~Именно таким способом игроки в бридж упорядочивают свои карты, беря по одной.) В. Обменная сортировка.
Если два элемента расположены не по порядку, то они меняются местами. Этот процесс понторяется до тех пор, пока элементы не будут упорядочены. С. Сортировка посредством выбора. Сначала ныделяется наименьший (или, быть может, наибольший) элемент и каким-либо образом отделяется от остальных, затем выбирается наименьший (наибольшггй) из оставшихся и т. д.
О. Сортировка путем ггодс"гота. Каждый элемент сравнивается со всеми остальными; окончательное положенпе элемента определяется после подсчета числа меньших ключей. Е. Специальная соргпировка. Она хороша для пити элементов, указанных в задаче, но не поддается простому обобщению, если элементов больше. Г. Способ леггтпяя. Вы не откликнулись на наше предложение и отказались решать задачу. Жаль — - вы упустили свой шанс...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
