AOP_Tom3 (1021738), страница 170
Текст из файла (страница 170)
34 (1970), 709 — 727), можно получить комбинаторное доказательство весьма примечательных тождестн: 1 ~ З.(.,*-)бл(у у-)=ПП, .„ л 1 — х,уз ЕЗ(...-)З*( -)=ПП('+ '» Здесь суммировшьие выполняется по всем возможным формам А, а А обозначает транст понироэаиную форму. Впервые эти тождества были найдены в работе Р. Е. ВН11енооб, Ргос.
1оль!ол МаНс Бос. (2) 40 (1936), 40 — 70, ТЬеогегп ЯХ Замечание. Отсюда. в частности, следует, что любое произведение последователь- ных биномиэльных коэффициентов (') ('»»') .. ('+') можно разделить на (») ( ~»')... ("» '), поскольку это отношение есть /ь(а+ 1,...,а+ 1,а,/с — 1,...,1,0)/»5(1,,1,0). Значение ~(!....., 1, О) = (! — 1)!... 1! 0~ иногда называют суперфакториалом, 34. Длина уголка есть также длина любого зигзагообразного пути от левой нижней ячейки уголка (х,у) до его праной верхней ячейки (х',у'). Докажем более сильный результат. Если существует уголок длиной а + 6, то существует либо угачок длиной а, либо уголок длиной 6.
Рассмотрим ячейки (г, у) = (хь, уь), (хь, уь), ..., (х +ь, у +ь) = (х', у'), которые обрамляют нижнюю часть формы диаграммы. Если х,+ь = х„то ячейка (х„уь) имеет уголок длиной а; в противном случае (х,эь, у„эь) имеет уголок длиной 6. [См.,!аралеяе Х у!аь!ь. 17 (1940), 165 .184, 411-423. Накаяма первым рассмотрел уголки в процессе анализа групп перестановок и подошел очень близко к открытию теоремы Н.[ 35. В результате выполнения шагов СЗ-С5 на 1 уменьшается точно 60 элементов массива р, если дч иозросло, поскольку алгоритм отслеживает зигзагообразный путь от р„к рь„,, ь В следующий раз выполнение этих же шагов начнется с большего значения ! или будет проходить выше либо на уровне того же зигзага, что и в предыдущий раз.
Таким образом, массив а заполняется елена направо и снизу вверх; для того чтобы застанить процесс идти в обратном направлении, мы должны организовать движение г зева направо и сверху вниз. Н1. [Инициализация.] Присвоить р„о- О, 1 < ! < пз и 1 < ь < и',. Затем присвоить ь о- 1 и ! о- и,. Н2. [Поиск ненулевой ячейки.] Если 90 > О, перейти к шагу НЗ. В противном юзучае, если з < п,', увеличить з на 1 н повторить этот шаг. В противном случае, если ! > 1, уменьшить ! на 1, присвонты ь- 1 н повторить этот шаг.
В противном случае остановить процесс (массив 4 теперь обнулен). НЗ. [Уменьшение д, подготовка к движению по зигзагу.] Уменьшить Оо на 1 и присвоить ! +- ь, й ь- и,. Н4. [Переход вниз или алена.] Если ! < и„'и рзь > рр Пь, увеличить ! на 1 и вернуться к шагу Н4. В противном случае, если !о > у, уменьшить !о на 1 и нернуться к шагу Н4.
В противном случае нернуться к шагу Н2. 9 Первый зигзаг для данного столбца У закапчннается приращением р„, поскольку рз, < < р„влечет за собой р„> О. Каждый последующий путь для столбца !' проходит 3 ниже или на таль же уровне, что и предыдущий, так что он также закончится на р49 Неравенства, которые используются в этом способе, свидетельствуют о том, что погтроенный алгоритм нвляется обратным по отношению к описанному при ззастаноаке задачи. [Х СозпЬшасойа! ТЛеогу А21 (197б), 21б — 221.] 36. (а) Коэффипиент при з есть число решений зп = 2 Л,здб, так что можно распространить на данный случай результат предыдущего упражнения.
(Ь) Если аз,, аь любые положительные целые числа, можно доказать, используя индукцию по !о, что [з ]1/(1 — з)(1 — э ')... (1 — з ") = /аз ...аз + 0(зп ). 1!о! Число разбиений зп на не более чем и частей равно, таким образом, [„'",) /п!+ 0(т" з) при фиксированном п, как следует иэ упр. 5.1.1 — 15 Это также асимптотическое число разбиений зп = рз+.. +р„, козла части разлпчнм — рз » .
р > О (см. упр. 511.1б) Таким образом, число обратных плоских 1зазбиений асимптотически приближается к зУ( "',)/и! 4 0(гп" о), если имеется Аз дню рамм данной формы из л ячеек. Из и (а) это также есть [„,)/ ПЛ з + 0(зп" з) [БьиаОеэ зн Аррйеб 5!аСЛ. 50 (1971), 187 — 188, 259 279] 37.
Плоское разбиение на прямоугольнике эквивалентно обратному плоскому разбиению, так что длкны уголков дают нам производящую функцию 1/ П,"., П',(1 — оью ') на прямоугольнике г х с. Если положим г,с -ь оо, то получим ответ в очень элегантном виде: 1/(1 — о)(1 — зз)з(1 — з) ..
[Вывод принадлежит Мак-54шону и опубликован в Р!и!азор!пса! Тзалэагйопэ 211 (1912), 75 — 110, 345-373, но там он имел гораздо более сложную форму. Первым простое доказательство нюнел Леонард Карлиц (Ьеоаагб Саг!зня), Асса Апгбпзейса 13 (19б7), 29-47.) 38. (а) Вероятность равна 1/и при Л = ! = 1: в противном случае, применяя индукцию по й+ 1, полз чим ззР(Гзз(зо), о) ч-пР(1, о'зь(!ого) (8оь+з! зо)/(пз!зоь.
з!зь зьз( зо ..з! л,) аз' юо г7зоо + зэ зо (Ь) Суммирование повеем 7 и о дает п '(1+Озь) (1+о!о,,' Пь) (1+о!,з) (1+о!,,1ь-ц): что, как легко нидеть, равно /(Т зь ((а 5)))//(Т). (с) Суммирование по всем угловым ячейкам дает 1, поскольку каждый путь заканчивается в какой-либо углоной ячейке.
Таким образом, 2,'/(Т 1 ((а,Ь))) = /(Т), а это доказывает теорему Н, если применить индукцию па и. Более того, если разместить ц в угловой ячейке в конце случайнога пути и повторить процесс на оставшихся и — 1 ячейках, получится каждый вариант диаграммы с вероятностью 1(Г(Т). [Адеавсев !л МвН>. 31 (1979), 104-109.] 39. (а) !дм . !д> будут иметь вид Ь>... Ь„, т. е.
будут представлять собой таблицу инверсий исходных перестановок Р11... Р,„(см. раздел 5.1.1). (Ъ) !д~1... !Г > — таблица инверсий с обратным знаком (-С1)... ( — С„) из упр. 5.1.1-7. (с) Это условие, очевидно, предусматривается на шаге РЗ. (д) (вз) > ((г4) (а е )) (1т) > Нвв), (е е )). Этотпримерпокаэывает, что нельзя выполнять шаг РЗ в обратном направлении, не просмотрев массив Р.
(е) (Г) Следующий алгоритм корректен, но не очевиден, ь)1. (Цикл по (1, !),] Выполнить шаги Я2 и !43 для каждой ячейки (1,!) массива в лексикографическом порядке (к е. сверху вниз и слева направо в каждой строке), затем прекратить выполнение процедуры. 142. [Изменение О,] Найти "первого кандидата" (г, в) по правилу, которое будет изло- жена ниже. Затем присвоить Оде+1> е — !д,в — 1 лля ! < Л < в.
Ь!3. (Восстановление Р в (Ь!).] Присвоить К е- Р„. Затем выполнять следующие операции до тех пор, пока не будет выполнено условие (г. в) = (1, д). Вели Р>„0, > Ры, », присвоить Р„, е- Рр,>, и г е- г — 1; в противном случае присвоить Р, е — Р,.>„ м и в +- в — 1. И,наконец, присвоить Ра е- К. $ На шаге Я2 ячейка (г,в) является кандидавлом, если в В > и 1;>„< О, и г = ' !дм Пусть Т вЂ” ориентированное дерево, построенное в соответствии с указанием Один из аснанных ннвариантов алгоритма св состоит в том, что на этом дереве будет существовать путь от (г, в) к (Ъ !) в Т всякий раз, когда (г, в) является кандидатом на шаге Я2. Обратный путь к нему можно закодировать последовательностью букв 1>, б) и В., означающих, что мы начали в ячейке (и !), затем спустились (1>) или пошли вправо (В), или закончили Я), 77ерема кандадапэ — это один из кандидатов, код которого в лексикографическом смысле стоит раньше других; интуитивно кажется, что он должен быть крайним слева и снизу по отношению к "конкурентам'! Например, кандидатами при (1,1) = (1, 1) в примере п.
(е) являются (3, 1), (4,2), (2, 3), (2, 4) и (1, б). Им соответствуют коды О1>О., ПОРВО., ВПВО, В1>ВЩ и ВВВВВ>4; из них первым будет (4, 2). Алгоритм Р представляет собой несколько упрощенную версию построения, описанного без доказательства в работе, опубликованной в журнале Функциональный анализ и его приложения, 26, 3 (1992), 80 — 82.
Доказательство корректности этого построения отнюдь не очевидна и дано Ж.-К. Новелли (.!.-С. Хоме!>!), И. Паком (1. Рай) и А. В. Стояновским (А. У. Згоуаповвй>!) в Р!вс. МавЛ. апд ТЛеогейса! Сот р. Ясй 1 (1997), 53 — 67. 40. Эквивалентный процесс проанализирован в работе Н. Вовс, Ле!свсЛг>7! Гбг ИабгвсЛе!и!>сййе!!в!Леев!е апд 1егнапд!е Себ!еве 58 (1981), 41 — 53. 41. (Решение предложено Р.
У. Флойдом (В ЪЧ. Р>пуси).) Операция удаления-вставки фактически перемещает только а,. В процессе ее выполнения незатронутые элементы сохраняют порядок. Таким образом, если перестановку я можно рассортировать при помощи Л операций удкчен»зя-вставки, то она имеет возрастающую подпоследовательность длиной и — Л, и наоборот. Следовательно, ббв(я) = и — (длина самой длинной возрастающей подпоследовательности в л) = и + (длина строки 1 в теореме А). М.
Л. Фредман (М. Ь. Ггес)шап) доказал,что наименьшее количество сравнений, необходимое для вычисления этой длины, равно п18п — и !8 !8 и+0(п) [Р1зсгеге Ма»Л. 11 (1975), 29 — 35). 42. Постройте мультиграф с вершиналш (Ол, 1», 1д,..., пс, п д, (и + 1) в ) и ребрами Лев (/с+ 1)ь при 0 < Л < и, включите также ребра Од — 7д, 7». — 1»„1д — 2», 2д — 4», 4л — 5», бд — Зь, Зя — бя, бь — 8», которые соответствуют "узам" в ЬоЬе!за уетеепз. К каждой вершине подходит в точности два ребра, так что связанные компоненты являются циклами: (Од 1» 7» бл Зд 4» 2д Зь 5д бь 8» 7д)(1д 2»)(4л 5»).
Некоторая операция перебрасывания изменяет количество циклов на — 1, 0 или +1. Таким образом, нам понадобится, по крайней мере, пять операций для того., чтобы прийти к восьми циклам (Ол 1с)(1л 2»)... (7д 8»). [.1. Косее!об!т», Р. Бап)сой, бес»иге Косел !л Сотр. Ясб 807 (1994), 307-32зт.] Первая операция должна разорвать узы бь — 8», поскольку мы не достигнем никакого нового цикла после разрыва двух уз, которые имеют одинаковую ориентацию слева направо в линейном представлении.
В результате после одной операции появляется пять д л я л д л д д д д д л д вариантов, а именно -- Ут ув9» узус Увдт, угу»9»Усу»узус угу»у»дед»У»У» 9т У»У»Усу»У»Уз и 9вдз дз 94 Уз 9» Ут: еще четырех опеРаций достаточно для того, чтобы рассортировать все, ля я ля кроме второй иэ них. Существует 2' 7! = 645 120 разных вариантов компоновки дт...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
