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

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

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

А. Бендеру (Е. А. Веггдег), каждое разбиение множества (1,2,..., и) на й непустых непересекающихся подмножеств соответствует некоторому расположению л — 5 ладей. Пусть разбиение таково: (1,2,...,п] = (ап,аш,,аггч) 0 0(аю,,амм), где ао < ац,+П пРи 1 < 1 < пп 1 < г < а. Ему соответствует следующее расположение ладей: ладьи помещаются в ао-й столбец ан,т,цй строки, где 1 < 1 < п„1 < г < к. 11апример, позиция, приведенная на рис.

4, соответствует разбиению (1, 3, 8) 0 (2) 0 (4, 6) 0 (5) 0 (7), 20. Число чтений равно числу серий в обратной перестановке. Первая серия соответствует первому чтени!о и т. д. 21. Перестановка имеет и+ 1 — 5 серий и требует и+ 1 — 7' чтений. 22. [2. Сошбзпа!ог!а! Т1!еогу 1 (1966), 350 — 374.] Если гэ < и, то при некотором чтении выбирается 1 > г элементов, аб = 7 5 1,..., ач = /+1, где г! « .. г!, Нельзя получить аы > аме! для всех ьч в диапазоне гь < и! < !ье!. Таким образом, перестановка содержит, по меньшей мере, 1 — 1 таких мест, где а < а +!: отсюда следует, что в перестановке не более и — 1+ 1 серий. С другой стороны, рассмотрим перестэловку о„...

а! а!, в которой блок а! содержит числа = / (по модулю г) в порядке убывш!ия; например, когда и = 9 и г = 4, эта пере<шпанка имеет вид 8 4 73 6 2 9 5 1. Если и > 2г — 1, зта перестановка имеет г — 1 возрастаний. Значит, в ней имеется и+1 — г серий. Вачее того, если г > 1, она требует точно и+1 — (г!/г) чтений. Можно по-другому расставить элементы в (кг+1,... ! Йт+г), не меняя числа серий; таким способом можно уменьшить число чтений до любой желаемой величины > (и/г]. Теперь предположим, что гэ > и, г + э < и+ 1 и г, э > 1.

Как показано в упр. 20 и 21, можно считать, что г < э, поскольку отражение инверсии с и+ 1 — г сериями и э чтениями имеет и + 1 — э серий и г чтений, После этого рассуждения предыдущего абзаца можно применить ко всем случаям, кроме тех, где э > и+ 1 — (и/г] и г > 2, Чтобы завершить доказательство, можно воспользоваться перестановкой в форме 25+1 25 — 1 ... 1 и+2-г и+1 — г ...

25+2 25 ... 2 и+3-г ... и — 1 и, которая имеет и+ 1 — г серий и и + 1 — г — 7! чтений, 0 < 5 < 1(и — г). 23. (ЯАМ Нег!е!г 3 (1967), 121-122.] Допустим, что бесконечная перестановка состоит иэ независимых частей, подчиненньп! равномерному закону распределения, Пусть /ь (х) Их— вероятность того, что й-я удлиненная серия начинается с х, и пусть д(и,х)Ых — вероятность того, что удлиненная серия начинается с х, при условии, что предыдущая удлиненная серия начинается с и. Тогда /!(х) = 1, /ь+!(х) = ]о /ь(и)д(и,х)!4и.

Здесь д(и, х) = 2 " й, д,(к, х), где д (и,х)=Рг(н<Х! «. Х„>х или н>Х! » .Х <х) =Рг(и<Х! « - Х„,)+Рг(и>Х! » Х„,) — Рг(и<Х!« Хч!<х) — Рг(и>Х!» Х!ч>х) = (и + (1 — и) + ]и — х] )/и!!, Следовательно, д(п,х) = е" + е' " — 1 — е!" М и получим /э(х) = 2е — 1 — е* — е' Можно показать, что /е(х) стремится к предельному значению (2 соя(х — -) — э!пб— ! ! сое ! )/(3шп-' — соэ — ').

Средняя длина серии, начинающейся с х, равна е*+ е' * — 1; таким образом, длина й-ой удаленной серии С! равна ] /ь(х)(е* + е' * — 1) бх; ь! = 2е — 3- 2.43656; Се — — Зе~ — 8е+ 2 — 2.42091. Аналогичные результаты имеются е разделе 5.4.1. 24. Рассуждая, как и раньше, получим в результате 1+ ~ 2 (р + у ) (р +2ру(2" — 1+ 4 ((2ру)™ ! — 1)/(2ру — 1))). 0<!<а После суммирования и упрошенив получим искомую функци!о 2(э+ !)(( )/(э+ ! ) Ч+(2 ) з/(з+ !)(э+ + у'/(р'+ у') + 2"-'. 25. Пусть Ъ! = (У! +. + Уг) шо!1 1; тогда 1!!,..., 1а — независимые равномерно распределенные числа в интервале ]О .. 1), образующие перестановку, которая имеет 5 нисходящих серий тогда и только тогда, когда (гч+ + У„) = Ь.

Отсюда получается ответ ()/и!; зто свойство впервые обнаружил С. Тэнни (Б. Танну) (см. Рейс Магб. Х 40 (1973), 717-722). 26. Например, д~(1 — х) ' = (х + 26э~ + ббхэ + 26г~ + э~)/(1 — е) е. 27. Следующее правило дает взаимно однозначное соответствие между перестановкой а~ аэ... а„, имеющей й нисходящих серий, и и-узловым разрастающимся лесом, имеющим Ь + 1 лист. Первый корень — ам а его потомки — лес, соответствующий аэ... аю где )г — наименьшее число, удовлетворяющее аьэч < ац или Ь = и. [11. Р. Бган!еу, Епишегайке СошЬ1па1ог)сэ 1 (%аг(эког11Ь 1986), Ргороэййов 1.3.16.) РАЗДЕЛ 5.1.4 (5924817)7 2.

Пусть р„— элемент столбца 1 — 1, если р; вставляется в столбец П Тогда (9э,р,) принадлежит классу 1 — 1, д, < 90 рэ < рп таким образом, по индукции приходим к заключению, что существуют индексы 1м..., Ь, обладающие нужным свойством. Обратно, если 91 < 90 р, < р, н (дэ, р„) принадлежит классу 1 — 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]). 6. Допустимые обмены симметричны в направлении слева направо, а каноническая перестановка для Р очевидным образом переходит в Р, если вставлять элементы в обратном т порядке. 6. Будем считать,что существует всего 1 классов; из них точно Ь имеют нечетное число элементов, поскольку элементы класса имеют вид (см.

(18) и (22)). Вытесненный двухстрочный массив имеет ровно 1 — Ь фиксированных точек, что следует из способа его формирования. Следовательно, по индукции диаграмма без ее первой строки имеет 1 — Ь столбцов нечетной длины. Таким образом, 1 элементов в первой строке приводят к появлению й столбцов нечетной длины по всем диаграммам.

7. Число столбцов, а именно — длина строки 1, равно числу классов (упр. 2). Число строк равно числу столбцов в Р . Далее, применив результаты упр. 5 (или теоремы П), т завершаем доказательство. 8. Диаграмма Р, в которой содержится более и элементов, должна иметь либо более т и строк, либо более п столбцов. Однако существует н диаграмма размером п х ть, (Этот результат впервые был доказан в Сошроэьььо МасЛ.

2 (1935), 463-470.] 9. Подобные перестановки обладают взаимно однозначным соответствием с парами диаграмм вида (и, п,..., ть); таким образом, с учетам (34) ответ таков: ит! ь3(2п-1,2п-2,...,ть)) ( (" иь! (2п — 1)(2и — 2)'... и" (и — 1)" '... 1' Вонстэшу удивительно, что решением этой задачи является такая простак формула. Теперь люжно подсчитать число перестановок (1, 2,..., пьп), в которых отсутствуют возрастающие последовательности длиннее тп и убывающие последовательности длиннее п.

10. Доказынаем по индукции, что на шаге БЗ оба массива — и Рй Ч„и Рп> ц меньше, чем Рб вььь н Р,ь, 11. Разумеется, нам еще нужно знать, какой элемент был раньше на месте Рп То- гда существует возможность восстановить исходный вид диаграммы, используя алгоритм, чрезвычайно похожий на алгоритм Б. 12. ( ) + ( ) + + ( ) — ( ) — это путь, пройденный н общей сложности. Минимальное значение равно сумме первых и членов последовательности 1,2, 2, 3, 3,3,4,4,4,4...

в упр. 1.2.4 — 41:, эта сумма равна приблизительно ь/8/9 ть"ь~, (Почти для всех диаграмм из и элементов оценка значения минимума подходит очень близко к этой границе, как следует из упр. 29. Поэтому среднее число применений шага ЯЗ равно Э(и ь ).) 13. Пусть в перестановке участвуют элементы множества (1,2,..., п), так что а, = 1, и предположим, что а; = 2. Случай 1, 3 < ь.

Тогда 1 вытесняет 2, а значит, строка 1 диаграммы, соответствующей перестановке аь .. а, та,эь...а, есть строка 1 в Р вытесненная перестановка — та же, что и прежняя вытесненнан перестановка, но ее наименьший элемент теперь равен 2; результат по индукции можно расширить н на и. Случай Я, у > ь. Применим результат случая 1 к Рт, приняв во внимание результат упр.

5 н тот факт, что (Рт)з = (Рз)т. 15. Как и в (37), приведенная в качестве примера перестановка соответствует диаграмме 9 11 10 следовательно, искомое число равно Я та и) = (1+ та+и)ь (1 — та+1)(1 — ть+2)(тп — и+1)/ (С + 2)! (та+ 1)' (и)ь при условии, разумеется, что 1 > тп > и. 16. Как следует нз теоремы Н, 80 080 способами. 17. Поскольку полинам д антнсимметричен по х, он обращается в О при хь = х„", следовательно, он делится на х, — х, при всех ь < т1 Таким образом, д(хь,...,х„;у) Ь(хь,..., х; у) Ь5(хь,..., х„). Здесь функция Ь должна быть однородным полнномом первой степени хь,..., х, у, симметричным относительно хь,..., х„, так что Ь(хь,..., х„у) = а(хь + .

+ х ) + Ьу для некоторых а и Ь, зависящих только от п. Можно вычислить а, положив у = 0; можно вычислить Ь, взяв частную производную по у и затем положив 9 = О. Получим д д у 1 — »3(х»,...,х +у,..., хч))»=е = — Л(хп...,х ) = »3(хп,х„) 7 Окончательный результат таков: (г)' »Ф »< 18. Онадолжна равняться»1(хп...,х ).(Ье+Ь»р+ ..+Ьму ), где все Ь» — однородные симметричные полиномы степени гл — й от переменных х.

Имеем где сумма берется по всем (" ') способам выбора различных индексов ум ..,,2». ф». Теперь в выражении Ь» = г х~/П, »(х» — хл) можно скомбинировать группы из Ь+ 1 членов, имеющих данный набор и»»дексов (», 1м, /»); например, при Ь = 2 сгруппируем наборы из трех членов вида ам/(а — Ь)(а — с) + Ь"'/(Ь вЂ” а)(Ь вЂ” с) + с /(с — а) (с — Ь). Сумма членов каждой группы вычисляется, как в упр. 1.2.3-33: (я ) 1/(1 — х»е)(1 — хм г)... (1 — х,»э). Таким образом, находим, что где э(р»,..., р,) — симметричная функция, содержащая всевозможные различные одно- члены вида х» ... х,',, с различными индексами»п ., ., », Е (1,..., и), а внутренняя сумма Р» берется по всем разбиениям т — й точно на 3 частей, таких, что р» » .

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

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