AOP_Tom3 (1021738), страница 30

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 30)

Например, перестановка 7 5 ( 6 2 ( 3 8 9 ( 1 4 содержит четыре удлиненные серии. Найдите средние длины первых двух удлиненных серий бесконечной перестановки и докажите, что в пределе длина удлиненной серии равна (1 + сос 1,')/(3 — сот 1) ш 2.4202. в5.1.4. Диаграммы и инволюции В заключение нашего обзора комбинаторньпс свойств перестановок обсудим некоторые замечательные отношения, связывающие их с массивами целых чисел, называемыми диаграммами. Диаграмма Юнга формы (пы пз,..., и,„), где пэ > пз » . и > О.

— это расположение п1+ из+. + пш различных целых чисел в массиве строк, выровненных по левому краю, где в 1-й строке содержится и, элементов; при этом в каждой строке элементы возрастают слева направо, а элементы каждого столбца возрастают сверху вниз. Например, диаграмма Юнга формы (6, 4, 4, 1) имеет вид Диаграммы такой формы ввел Альфред Юнг (АНгед Уовпб) в 1900 году в качестве вспомогательного средства при изучении матричного представления перестановок. [См.

Ргос. Йош)оп МаНь Яос. (2) 28 (1928), 2о5 — 292; Вгпсе Е. Вабап, ТЬе Яупипе1г[с Сгопр (Рас15с Стоге, СаИс %Ывэгогсп й Вгоо1сэ/Со1е, 1991).] Для краткости вместо "диаграмма Юнга" мы будем говорить просто "диаграмма". Ннволюцил — это перестановка, обратная самой себе. Например, существует 10 инволюцнй множества (1, 2, 3, 4): 1234 2134 3214 4231 1324 1432 1243 2143 3412 4321 (2) Термин "инволюция" первоначально использовался в классических задачах геометрии; инволюцвн в общем смысле, рассматриваемые здесь, были впервые изучены Х. А.

Роте (Н. А. ВосЬе), когда он ввел понятие обратной перестановки (см. раздел 5Л.1). Может показаться странным, что мы рассматриваем диаграммы и инволюции вместе, но существует удивительная связь между этими понятиями, не имеющими, казалось бы, друт к другу никакого отношения: число ллволюций множества 24. [МЯ0[ Выразите в виде функции от р среднее число серий в последовательностях, полученных методом, который описан в упр. 5.1.1 — 1В. 25. [М20) Пусть Уп..., У„- — независимые равномерно распределенные числа иа интервале [0..1). Какова вероятность выполнения равенства [15+ + П ) = Й? 26.

[М20[ Обозначим через д операцию з+д которая умножает на и коэффициент при х" в производящей функции. Покажите, что результат многократного (кч раз) применения д к 1/(1 — з) может быть представлен в терминах чисел Эйлера. ь 27. [М21) Разрастающийся лес — это лес, в котором узлы пронумерованы (1, 2,..., и) таким образам, что родители всегда имеют меньшие номера, чем их потомки. Покажите, что (~) — число и-узловых разрастающихся лесов, в которых имеется 5+ 1 лист. (1,2,...,и) равно числу диаграмм, которые можно сформировать из элементов (1, 2,..., и). Например, из (1, 2, 3, 4) можно сформировать ровно 10 диаграмм: 3 124 134 14 ~з~ (3) 21231312 Дз Это соответствует 10 инволюциям (2).

Такая связь между инволюциямн и диаграммами отнюдь не очевидна, и, по-виднмому, не существуег простого способа ее доказательства. Доказательство, которое мы обсудим, включает интересный алгоритм построения диаграмм, обладающий н другими неожндвннымн свойствами; он основан на особой процедуре вставки в диаграмму новых элементов. Предположим, например, что нужно вставить элемент 8 в диаграмму (4) В алгоритме 1 содержится точное описание этого процесса н доказательство того, что он всегда сохраняет свойства диаграммы, Алгоритм 1 (Вставка в диаграмму). Пусть Р = (Рб) — диаграмма целых положительных чисел, а х — целое положительное число, не содержащееся в Р. Этот алгоритм преобразует Р в другую диаграмму, содержащую х наряду с исходными элементами Р.

Новая диаграмма имеет ту же форму, что н старая, но на пересечении строки з и столбца 1 появился новый элемент, где з н 1 — величины, определяемые алгоритмом. Метод, которым мы будем пользоваться, состоит в том, чтобы сначала поместить 8 в 1-ю строку, в клетку, ранее занимаемую 9, поскольку 9 . — наименьший из элементов этой строки, больших 8. Элемент 9 "вытесняется" вниз., в строку 2, где он замещает 10.

Затем 10 "вытесняет" 13 из 3-й строки в 4-ю и, поскольку в 4-й строке нет большего элемента, чем 13, процесс завершается добавлением 13 в правый конец строки 4. Наша диаграмма (4) преобразовалось в (В этом алгоритме замечания в круглых скобках предназначены для доказательства его правильности, поскольку по индукции легко проверить, что эти замечания справедливы и что массив Р продолжает оставаться диаграммой на протяжении всего процесса. Для удобства будем предполагать, что диаграмма ограничена нулями сверху и слева и символами "оо" — справа и снизу, так что элемент Ру определен при всех 1,у > О.

Если ввести отношение а <; Ь тогда и только тогда, когда а < Ь или а = Ь = О, или а = Ь = оо, (6) то неравенства для диаграммы можно выразить в удобной форме: РО = 0 тогда и только тогда, когда ~ = 0 или у = 0; (7) РО < Рц.+О и РО < Р~,.~01 при всех ю,,~ > О. Утверждение "х й' Р" означает, что либо х = оо, либо х ф РО ни при каких 1, у > 0.) 11. [Ввести х.] Присвоить 1 < — 1, х~ < — х и присвоить у наименьшее значение, такое, что РО = оо.

12. [Найти х;.ы.] (В этот момент РО О < х; < РО и х; к Р.) Если х, < Рй О, то уменьшить у на 1 и повторить этот шаг. В противном случае присвоить хьы < — Рб иг; <-у. 13. [Заменить элементом х,.] (ТепеРь Рй. О < х, < х,+, — — Р;. < Рцу+,, РО, у < х~ < хг+1 = РО < Рбч.цу и гг =,(.) Присвоить РО +- хо 14.

[хг~ы = соу] (Теперь Рд О < РЗ = х, < х,чч < Рдз+О, РО О < Р; = х; < хьы <~ Р~м.~ у, г; = у и хсьг ф Р.) Если хьь~ ф ос, то увели читы' на 1 и вернуться к шагу 12. 15. [Определить э, й] Присвоить я с — т, Ф +- у и закончить процедуру.

(К этому моменту угловия Рм Ф оо и РО-~-О~ = Рць~-О (8) будут выполнены.) 1 Заметим, что данный алгоритм определяет "последовательность вытеснений" (9) х — хг < хз « ' ' ' х~ < х~.~.1 = оо> а также вспомогательную последовательность индексов столбцов (10) г~ > гт > ... > г, = Ф; при этом элемент Р;„меняет свое значение х;~~ на хо 1 < 1 < з. Например, когда в диаграмму (4) вставлялся элемент 8, последовательность вытеснения имела вид 8, 9, 10, 13, со, а вспомогательная последовательность — 4, 3, 2, 2.

Мы могли бы переформулировать алгоритм так, чтобы он расходовал меньше временной памяти (необходимо хранить только текущие значения у, х; и хьы); последовательности (9) и (10) были введены с той лишь целью, чтобы можно было доказать некоторые интересные особенности этого алгоритма. Основное свойство алгоритма 1, которым мы не преминем воспользоваться, состоит в том, что алгоритм можно "прокрутить" в обратном направлении: по заданным э и 1, определенным на шаге 15, можно привести Р к исходному виду, найдя и удалив элемент х, который был вставлен. Рассмотрим, например, (5); пусть известно, что элемент 13 занимает позицию, которая раньше была пуста. Тогда элемент 13, наверное, был вытеснен вниз иэ 3-й строки числом 10, потому что 10 — наибольший элемент в этой строке, меньший 13; аналогично элемент 10, по-видимому, был вытеснен из 2-й строки числом 9, которое, в свою очередь, было вытеснено из 1-й строки числом 8.

Таким образом, от (5) можно вернуться к (4), В следующем алгоритме подробно описан этот процесс. Алгоритм Р (Удаление иэ диаграммы). По заданной диаграмме Р и целым положительным числам э, 1, удовлетворяющим условиям (8), этот алгоритм преобразует Р в другую диаграмму почти такой же формы, но с со на пересечении столбца 1 и строки э. Найденный при этом элемент х удаляется из диаграммы Р.

(Как и в алгоритме 1, пояснения в круглых скобках включены для облегчения доказательства того, что массив Р продолжает оставаться диаграммой на протяжении всего процесса.) Х)1. [Ввести э, б] Присвоить 2' +- 1, 1 е- э, х,~ 1 е- оо. Р2. [Найти х,.] (В этот момент Р; < х,~.1 < Рб+0 их; 1 ф Р.) Если 1;.~ „< х,+,, то увеличить у на 1 и повторить этот шаг. В противном случае присвоить х;е-Рб иг;< — 1 123. [Заменить элементом х;+м] (Теперь Рй, 0 < Рб = х; < хгы < Реу+П, Рц 0 < Р„. = х; < х,.ы < Рб+0, и г, = 2'.) Присвоить РВ <- х,ем 114.

[1 = 12] (Теперь Рц 0 < х; < хьы — — Р; < Р,.0+11, Рц П < х; < х;~.1 — — Р, < Рц 01 и г; = 1.) Если 1 ) 1, то уменьшиты на 1 и вернуться к шагу 02. ОЬ. [Определить х.] Присвоить х < — х~ и закончить процедуру. (Теперь 0 < х < оо.) 1 Пояснения к алгоритмам 1 и П, заключенные в круглые скобки, не только полезны для доказательства того факта, что эти алгоритмы сохраняют структуру диаграммы, но и позволяют убедиться, что алгоритмы 1 и Р взаимно обратны.

Если сначала выполнить алгоритм 1 с данной диаграммой Р и некоторым целым положительным числом х ф Р, то он вставит х в Р и определит цетые положительные числа э, г, удовлетворяющие условиям (8). Алгоритм В, примененный к полученному результату, восстановит значения х и первоначальный вид Р. Обратно, если сначала выполнить алгоритм П с данной диаграммой Р н некоторыми целыми положительными числами э, г, удовлетворяющими условиям (8), то он модифицирует Р, удалив некоторое целое положительное число х.

Алгоритм 1, примененный к полученному результату, восстановит значения э, т и первоначальный вид Р. Дело в том, что присвоения, приведенные в заключенных в скобки пояснениях к шагам И и В4, равно как и к шагам 14 и РЗ, совпадают и однозначно определяют значение 11 Следовательно, вспомогательные последовательности (9), (10) одинаковы в обоих случаях. Теперь мы подготовлены к доказательству основного свойства диаграммы.

Теорема А. Существует взаимно однозначное соответствие между множеством всех перестановок множества (1,2,..., и) и множеством всех упорядоченных пар диаграмм (Р„ф, где Р и Я вЂ” диаграммы одинаковой формы яз элементов (1, 2,..., и). (Пример к этой теореме содержится в приведенном ниже доказательстве.) Доказагпельсгпво. Удобнее доказать несколько более общий результат.

По произвольному двухстрочному массиву с Й Ч2 Яи ~ ч1 < Чэ < < Ча, (11) р1 рэ ... р„ / ' ры рэ,..., р„различны, построим две соответствующие диаграммы Р и Я, где Р состоит из элементов (ры...,р„), а 1~ — из элементов (д„...,о„), причем Р и Я имеют одинаковую форму. Пусть Р и Я вначале пусты. Прис = 1, 2, ...„п (именно в таком порядке) выполним следующую операцию: вставим р; в диаграмму Р при помощи алгоритма 1; затем установим Ям < — дь где э и 1 определяют вновь заполненную позицию в Р.

Характеристики

Список файлов книги