«Третий том известной монографии одного из крупнейших американских специалистов по программированию Д. Кнута (первый том вышел в издательстве ”Мир” в 1976 г., второй—в 1977 г.) состоит из двух частей: ”Сортировка” и ...»

1

Original pages: 004-033

УДК 681.142.2

Третий том известной монографии одного из крупнейших американских специалистов по программированию Д. Кнута (первый том вышел в издательстве ”Мир” в 1976 г., второй—в 1977 г.)

состоит из двух частей: ”Сортировка” и ”Поиск”. В них подробно исследуются различные алгоритмы внутренней и внешней сортировки, изучаются методы поиска информации в таблицах на основе сравнения или преобразования ключей, даются оценки эффективности предлагаемых алгоритмов.

Книга снабжена большим количеством задач и примеров разной степени трудности, существенно дополняющих основной текст.

От других руководств по программированию книга выгодно отличается строгостью изложения и широким применением математического аппарата. Вместе с тем она доступна студентам первого курса. Знакомство с двумя первыми томами желательно, но не обязательно. Каждый, кто хочет научиться квалифицированно программировать, найдет в ней много полезного.

Рассчитана на широкий круг программистов.

Редакция литературы по математическим наукам K 041(01)78 20204022 c Перевод на русский язык, ”Мир”. 2 Original pages: 004-

ПРЕДИСЛОВИЕ РЕДАКТОРОВ ПЕРЕВОДА

Д. Э. Кнут хорошо знаком советскому читателю по переводам двух первых томов его обширной монографии ”Искусство программирования для ЭВМ” и не нуждается в аттестации. Настоящая книга представляет собой третий том и посвящена алгоритмам сортировки и поиска информации.

Исторически зарождение методов машинной сортировки можно отнести еще к прошлому столетию, и за столь длительное время многие специалисты успели испробовать свои силы в этой области.

Написано немало отчетов, статей, монографий. И даже в этих условиях книга Д. Кнута стала событием. По существу это энциклопедия, в которой можно найти любую справку, касающуюся алгоритмов, методов их оценок, истории вопроса и нерешенных проблем.

Нет нужды говорить о важности самой области. Практически сортировка и поиск в той или иной мере присутствуют во всех приложениях; в частности, при обработке больших объемов данных эффективность именно этих операций определяет эффективность, а иногда и работоспособность всей системы. Поэтому, как справедливо отмечает автор, книга адресована не только системным программистам, занимающимся разработкой программ сортировки и поиска информации. Можно сказать, что достаточно четкие представления об этой области нужны при решении любой задачи на ЭВМ как обязательные элементы искусства программирования.

Кроме теоретической и практической ценности, книга имеет большое методическое значение.

Многие авторы и преподаватели смогут извлечь из нее новые и полезные сведения не только по существу рассматриваемых вопросов, но и по способу их изложения. Автору мастерски удается ”расслоить” весь материал таким образом, что книгу можно использовать практически на любом уровне знакомства с предметом и при различной общей математической подготовленности читателя.

Перевод выполнен по изданию 1973 г. (первая редакция) с внесением многих (около 700) исправлений и добавлений, любезно предоставленных автором. Разделы с 5.1 по 5.3.2 переведены Н. И.

Вьюковой; разделы с 5.3.3 по 5.5 и предисловие— А. Б. Ходулевым; главу 6 перевел В. А. Галатенко.

Ю. М. Баяковский В. С. Штаркман

ПРЕДИСЛОВИЕ

Кулинария стала искусством, высокой наукой;

повара теперь—благородные люди.

Тит Ливий, АЬ Urbe Condita, XXXIX.vi (Роберт Бертон, Anatomy of Melancholy, 1.2.2.2) Материал этой книги логически продолжает материал по информационным структурам, изложенный в гл. 2, поскольку здесь к уже рассмотренным концепциям структур добавляется понятие линейно упорядоченных данных. Подзаголовок ”Сортировка и поиск” может привести к мысли, что эта книга предназначена лишь для системных программистов, занимающихся построением универсальных программ сортировки или связанных с выборкой информации. Однако в действительности предмет сортировки и поиска дает нам прекрасную основу для обсуждения широкого класса важных общих вопросов:

Как находить хорошие алгоритмы?

Как улучшать данные алгоритмы и программы?

Как исследовать эффективность алгоритмов математически?

Как разумно выбрать один из нескольких алгоритмов для решения конкретной задачи?

В каком смысле можно доказать, что некоторые алгоритмы являются ”наилучшими из возможных”?

Как теория вычислений согласуется с практическими соображениями?

Как эффективно использовать различные виды внешней памяти—ленты, барабаны, диски—для больших баз данных?

Я думаю, что на самом деле в контексте сортировки и поиска встречается практически любой важный аспект программирования.

Настоящий том состоит из гл. 5 и 6 монографии. В гл. 5 рассматривается сортировка (упорядочение); это очень большая тема, она разбита на две главные части—внутреннюю и внешнюю сортировку. В эту главу входят также дополнительные разделы, развивающие вспомогательную теорию перестановок (§ 5.1) и теорию оптимальных алгоритмов сортировки (§ 5.3). В гл. 6 мы имеем дело с поиском определенного элемента в таблице или файле; содержимое этой главы подразделяется на Роберт Бертон (1577–1640) — английский ученый, писатель и теолог. Прим. Перев.

Original pages: 004- методы последовательного поиска, методы поиска со сравнением ключей, поиска с использованием свойств цифр, поиска с помощью ”хеширования”; затем рассматривается более сложная задача выборки по вторичным ключам. Обе главы поразительно тесно переплетаются между собой, между их предметами имеются близкие аналогии. В дополнение к гл. 2 рассматриваются два важных вида информационных структур, а именно приоритетные очереди (п. 5.2.3) и линейные списки, представляемые посредством сбалансированных деревьев (п. 6.2.3).

Читателю, не знакомому с первым томом этой монографии, рекомендуется обращаться к указателю обозначений (приложение В), так как некоторые из встречающихся в книге обозначений не являются общепринятыми.

Эта книга без большей части математического материала была использована мной в качестве учебника по второму курсу лекций ”Структуры данных” для студентов младших и средних курсов.

Математические части этой книги, особенно § 5.1, п.5.2.2, § 6.3 и 6.4, могли бы составить учебник по анализу алгоритмов для студентов средних и старших курсов. Кроме того, на основе п. 4.3.3, 4.6.3, 4.6.4, § 5.3 и п. 5.4.4 можно построить курс лекций ”Сложность вычислений” для старшекурсников.

Быстрое развитие информатики и вычислительных наук задержало выход в свет этой книги почти на три года, поскольку очень многие аспекты сортировки и поиска подвергались детальной разработке. Я очень благодарен Национальному научному фонду, Отделению военно-морских исследований, Институту обороны, фирмам IBM и Norges Almemitenskapelige Forskningsrad за постоянную поддержку моих исследований.

В подготовке этого тома к печати мне оказали помощь многие лица, особенно Эдвард А. Бендер, Кларк Э. Крэйн, Дэвид Э. Фергюсон, Роберт У. Флойд, Рональд Л. Грэхем, Леонидас Гюиба, Джон Хопкрофт, Ричард М. Карп, Гэри Д. Кнотт, Рудольф А. Крутар, Шень Линь, Воган Р. Пратт, Стефан О. Райе, Ричард П; Стэнли, Я. А. ван дер Пул и Джон У. Ренч мл., а также студенты Стэнфорда и Беркли, которым пришлось искать ошибки в рукописи.

Д. Э. Кнут сентябрь Осло, Норвегия, благодетельности которых, надеюсь, нет никаких оснований сомневаться. Так, встретив у меня непонятное место, читатель должен предположить, что под ним кроется нечто весьма полезное и глубокомысленное.

ЗАМЕЧАНИЯ ОБ УПРАЖНЕНИЯХ

Упражнения, помещенные в книгах настоящей серии, предназначены как для самостоятельной проработки, так и для семинарских занятий. Трудно, если не невозможно изучить предмет, только читая теорию и не применяя полученную информацию для решения специальных задач и тем самым не заставляя себя обдумывать то, что было прочитано. Кроме того, мы лучше всего заучиваем то, что сами открываем для себя. Поэтому упражнения образуют важную часть данной работы; были предприняты определенные попытки, чтобы отобрать упражнения, в которых бы содержалось как можно больше информации и которые было бы интересно решать.

Во многих книгах легкие упражнения даются вперемешку с исключительно трудными. Зачастую это очень неудобно, так как перед тем, как приступать к решению задачи, читатель обязательно должен представлять себе, сколько времени уйдет у него на это решение (иначе он может разве только просмотреть все задачи). Классическим примером здесь является книга Ричарда Беллмана ”Динамическое программирование”; это важная пионерская работа, в которой в конце каждой главы под рубрикой ”Упражнения и исследовательские проблемы” дается целый ряд задач, где наряду с глубокими еще нерешенными проблемами встречаются исключительно тривиальные вопросы. Говорят, что однажды кто-то спросил д-ра Беллмана, как отличить упражнения от исследовательских проблем, и тот ответил: ”Если вы можете решить задачу, это—упражнение; в противном случае это—проблема”.

Можно привести много доводов в пользу того, что в книге типа этой должны быть как исследовательские проблемы, так и очень простые упражнения, и для того чтобы читателю не приходилось Перевод А. А. Франковского.—Прим. Перев.

4 Original pages: 004- ломать голову над тем, какая задача легкая, а какая трудная, мы ввели ”оценки”, которые указывают степень трудности каждого упражнения. Эти оценки имеют следующее значение:

Оценка Объяснение 00 Чрезвычайно легкое упражнение, на которое можно ответить сразу же, если понят материал текста, и которое почти всегда можно решить ”в уме”.

10 Простая задача, которая заставляет задуматься над прочитанным материалом, но не представляет никаких особых трудностей. На решение такой задачи требуется не больше одной минуты; в процессе решения могут понадобиться карандаш и бумага.

20 Задача средней трудности, позволяющая проверить, насколько хорошо понят текст. На то чтобы дать исчерпывающий ответ, требуется примерно 15–20 минут.

30 Задача умеренной трудности и/или сложности, для удовлетворительного решения которой требуется больше двух часов.

40 Очень трудная или трудоемкая задача, которую, вероятно, следует включить в план практических занятий. Предполагается, что студент может решить такую задачу, но для этого ему потребуется значительный отрезок времени; задача решается нетривиальным образом.

50 Исследовательская проблема, которая (насколько это было известно автору в момент написания) еще не получила удовлетворительного решения. Если читатель найдет решение этой задачи, его настоятельно просят опубликовать его; кроме того, автор данной книги будет очень признателен, если ему сообщат решение как можно быстрее (при условии, Интерполируя по этой ”логарифмической” шкале, можно прикинуть, что означает любая промежуточная оценка. Например, оценка 17 говорит о том, что данное упражнение чуть легче, чем упражнение средней трудности. Задача с оценкой 50, если она будет решена каким-либо читателем, в следующих изданиях данной книги может иметь уже оценку 45.

Автор честно старался давать объективные оценки, но тому, кто составляет задачи, трудно предвидеть, насколько трудными эти задачи окажутся для кого-то другого; к тому же у каждого человека существует определенный тип задач, которые он решает быстрее. Надеюсь, что выставленные мной оценки дают правильное представление о степени трудности задач, но в общем их нужно воспринимать как ориентировочные, а не абсолютные.

Эта книга написана для читателей самых разных степеней математической подготовки и искушенности, поэтому некоторые упражнения предназначены только для читателей с математическим уклоном. Если в каком-либо упражнении математические понятия или результаты используются более широко, чем это необходимо для тех, кого в первую очередь интересует программирование алгоритмов, то перед оценкой такого упражнения ставится буква ”М”. Если для решения упражнения требуется знание высшей математики в большем объеме, чем это дано в настоящей книге, то ставятся буквы ”ВМ”. Пометка ”ВМ” отнюдь не является свидетельством того, что данное упражнение трудное.

Перед некоторыми упражнениями стоит стрелка ”>”; это означает, что данное упражнение особенно поучительно и его рекомендуется обязательно выполнить. Само собой разумеется, никто не ожидает, что читатель (или студент) будет решать все задачи, потому-то наиболее полезные из них и выделены. Это совсем не значит, что другие задачи не стоит решать! Каждый читатель должен по крайней мере попытаться решить все задачи с оценкой 10 и ниже; стрелки же помогут выбрать, какие задачи с более высокими оценками следует решить в первую очередь.

К большинству упражнений приведены ответы; они помещены в специальном разделе в конце книги. Пользуйтесь ими мудро; в ответ смотрите только после того, как вы приложили достаточно усилий, чтобы решить задачу самостоятельно, или же если для решения данной задачи у вас нет времени. Если получен собственный ответ, либо если вы действительно пытались решить задачу, только в этом случае ответ, помещенный в книге, будет поучительным и полезным. Как правило, ответы к задачам излагаются очень кратко, схематично, так как предполагается, что читатель уже честно пытался решить задачу собственными силами. Иногда в приведенном решении дается меньше информации, чем спрашивалось, чаще—наоборот. Вполне возможно, что полученный вами ответ окажется лучше ответа, помещенного в книге, или вы найдете ошибку в этом ответе; в таком случае автор был бы очень обязан, если бы вы как можно скорее подробно сообщили ему об этом. В последующих изданиях настоящей книги будет помещено уже исправленное решение вместе с именем его автора.

Сводка условных обозначений > Рекомендуется М С математическим уклоном ВМ Требует знания ”высшей математики” 00 Требует немедленного ответа 10 Простое (на одну минуту) 20 Средней трудности (на четверть часа) 30 Повышенной трудности.

40 Для ”матпрактикума” 50 Исследовательская проблема >1. [00] Что означает пометка ”М20”?

2. [10] Какое значение для читателя имеют упражнения, помещаемые в учебниках?

3. [М50] Докажите, что если n—целое число, n > 2, то уравнение xn + y n = z n неразрешимо в целых положительных числах x, y,z.

При таком новом, ”машинном подходе” к изучению природы вы получите возможность быстро распознавать более 260 различных деревьев США, Аляски, В этой главе мы изучим вопрос, который часто возникает в программировании: переразмещение элементов в возрастающем или убывающем порядке. Представьте, насколько трудно было бы пользоваться словарем, если бы слова в нем не располагались в алфавитном порядке. Точно так же от порядка, в котором хранятся элементы в памяти ЭВМ, во многом зависит скорость и простота алгоритмов, предназначенных для их обработки.

Хотя в словарях слово ”сортировка” (sorting) определяется как ”распределение, отбор по сортам;

деление на категории, сорта, разряды”, программисты традиционно используют это слово в гораздо более узком смысле, обозначая им сортировку предметов в возрастающем или убывающем порядке. Этот процесс, пожалуй, следовало бы назвать не сортировкой, а упорядочением (ordering), но использование этого слова привело бы к путанице из-за перегруженности значениями слова ”порядок”. Рассмотрим, например, следующее предложение: ”Так как только два наших лентопротяжных устройства в порядке, меня призвали к порядку и обязали в срочном порядке заказать еще несколько устройств, чтобы можно было упорядочивать данные разного порядка на несколько порядков быстрее2. В математической терминологии это слово также изобилует значениями (порядок группы, порядок перестановки, порядок точки ветвления, отношение порядка и т. п.). Итак, слово ”порядок” приводит к хаосу.

Перри Мейсон—герой серии детективных романов популярного американского писателя Эрла Стенли Гарднера.— Прим. перев.

В оригинале ”Since only two of our tape drives were in working order I was ordered to order more tape units in short order, in order to order the data several orders of magnitude faster”.— Прим. перев.

6 Original pages: 004- В качестве обозначения для процесса упорядочения предлагалось также слово ”ранжирование”3, но оно во многих случаях, по-видимому, не вполне отражает суть дела, особенно если присутствуют равные элементы, и, кроме того, иногда не согласуется с другими терминами. Конечно, слово ”сортировка” и само имеет довольно много значений4, но оно прочно вошло в программистский жаргон. Поэтому мы без дальнейших извинений будем использовать слово ”сортировка” в узком смысле ”сортировка по порядку”.

Вот некоторые из наиболее важных применений сортировки:

a) Решение задачи ”группировки”, когда нужно собрать вместе все элементы с одинаковым значением некоторого признака. Допустим, имеется 10000 элементов, расположенных в случайном порядке, причем значения многих из них равны; и предположим, нам нужно переупорядочить файл так, чтобы элементы с равными значениями занимали соседние позиции в файле. Это, по существу, задача ”сортировки” в широком смысле слова, и она легко может быть решена путем сортировки файла в узком смысле слова, а именно расположением элементов в неубывающем порядке v1 v2... v10000. Эффективностью, которая может быть достигнута в этой процедуре, и объясняется изменение первоначального смысла слова ”сортировка”.

b) Если два или более файла отсортировать в одном и том же порядке, то можно отыскать в них все общие элементы за один последовательный просмотр всех файлов, без возвратов. Это тот самый принцип, которым воспользовался Перри Мейсон для раскрытия дела об убийстве (см.

эпиграфы к этой главе). Оказывается, что, как правило, гораздо экономнее просматривать список последовательно, а не перескакивая с места на место случайным образом, если только список не настолько мал, что он целиком помещается в оперативной памяти. Сортировка позволяет использовать последовательный доступ к большим файлам в качестве приемлемой замены прямой c) Как мы увидим в гл. 6, сортировка помогает и при поиске, с ее помощью можно сделать выдачи ЭВМ более удобными для человеческого восприятия. В самом деле, листинг (напечатанный машиной документ), отсортированный в алфавитном порядке, зачастую выглядит весьма внушительно, даже если соответствующие числовые данные были рассчитаны неверно.

Хотя сортировка традиционно и большей частью использовалась для обработки коммерческих данных, на самом деле она является инструментом, полезным в самых разных ситуациях, и поэтому о нем не следует забывать. В упр. 2.3.2–17 мы обсудили ее применение для упрощения алгебраических формул. Упражнения, приведенные ниже, иллюстрируют разнообразие типичных применений сортировки.

Одной из первых крупных систем программного обеспечения, продемонстрировавших богатые возможности сортировки, был компилятор Larc Scientific Compiler, разработанный фирмой Computer Sciences Corporation в 1960 г. В этом оптимизирующем компиляторе для расширенного ФОРТРАНа сортировка использовалась весьма интенсивно, так что различные алгоритмы компиляции работали с относящимися к ним частями исходной программы, расположенными в удобной последовательности. При первом просмотре осуществлялся лексический анализ, т. е. выделение в исходной программе лексических единиц (лексем), каждая из которых соответствует либо идентификатору (имени переменной), либо константе, либо оператору и т. д. Каждая лексема получала несколько порядковых номеров. В результате сортировки по именам и соответствующим порядковым номерам все использования данного идентификатора оказывались собранными вместе. ”Определяющие вхождения”, специфицирующие идентификатор как имя функции, параметр или многомерную переменную, получали меньшие номера, поэтому они оказывались первыми в последовательности лексем, отвечающих этому идентификатору. Тем самым облегчалась проверка правильности употребления идентификаторов, распределение памяти с учетом деклараций эквивалентности и т. д. Собранная таким образом информация о каждом идентификаторе присоединялась к соответствующей лексеме. Поэтому не было необходимости хранить в оперативной памяти ”таблицу символов”, содержащую сведения об идентификаторах. После такой обработки лексемы снова сортировались по другому порядковому номеру; в результате в программе, по существу, восстанавливался первоначальный порядок, если не считать того, что арифметические выражения оказывались записанными в более удобной, ”польской префиксной” форме. Сортировка использовалась и на последующих фазах компиляции—для облегчения оптимизации циклов, включения в листинг сообщений об ошибках и т. д. Короче говоря, компилятор был устроен так, что всю обработку файлов, хранящихся на барабанах, фактически можВ оригинале ”sequencing”.—Прим. перев.

Это в большей степени относится к английскому слову ”sorting”. Здесь автор приводят пример:

”Не was sort of out sorts after sorting that sort of data”. (Он был как будто не в духе после сортировки такого сорта денных), который в русском переводе не столь выразителен.— Прим. перев.

но было вести последовательно. Поэтому-то данные и снабжались такими порядковыми номерами, которые позволяли упорядочивать эти данные различными удобными способами.

Другое, более очевидное применение сортировки возникает при редактировании файлов, где каждая строка снабжена ключом. Пока пользователь вносит с клавиатуры изменения и добавления, необязательно держать весь файл в оперативной памяти. Все изменяемые строки можно позднее отсортировать (а они и так обычно в основном упорядочены) и слить с исходным файлом. Это дает возможность разумно использовать память в режиме мультипрограммирования. [Ср. с С. С. Foster, Comp. J., 11 (1968), 134–137].

Поставщики вычислительных машин считают, что в среднем более 25% машинного времени систематически тратится на сортировку. Во многих вычислительных системах на нее уходит больше половины машинного времени. Из этой статистики можно заключить, что либо (i) сортировка имеет много важных применений, либо (ii) ею часто пользуются без нужды, либо (iii) применяются в основном неэффективные алгоритмы сортировки. По-видимому, каждое из трех предположений содержит долю истины. Во всяком случае ясно, что сортировка заслуживает серьезного изучения с точки зрения ее практического использования.

Но даже если бы сортировка была почти бесполезна, нашлась бы масса других причин заняться ею! Изобретательные алгоритмы сортировки говорят о том, что она и сама по себе интересна как объект исследования. В этой области существует множество увлекательных нерешенных задач наряду с весьма немногими уже решенными.

Рассматривая вопрос в более широком плане, мы обнаружим, что алгоритмы сортировки представляют собой интересный частный пример того, как следует подходить к решению проблем программирования вообще. Мы познакомимся со многими важными принципами манипулирования со структурами данных и проследим за эволюцией различных методов сортировки, причем читателю часто будет предоставляться возможность самому ”открывать” те же идеи, как будто бы до него никто с подобными задачами не сталкивался. Обобщение этих частных методов позволит нам в значительной степени овладеть теми способами мышления, которые помогут создавать добротные алгоритмы для решения других проблем, связанных с ЭВМ.

Методы сортировки служат великолепной иллюстрацией идей анализа алгоритмов, т. е. идей, позволяющих оценивать рабочие характеристики алгоритмов, а значит, разумно выбирать среди.

казалось бы, равноценных методов. Читатели, имеющие склонность к математике, найдут в этой главе немало способов оценки скорости работы алгоритмов и методов решения сложных рекуррентных соотношений. С другой стороны, изложение построено так, что читатели, не имеющие такой склонности, могут безболезненно пропускать выкладки.

Прежде чем двигаться дальше, необходимо более четко определить задачу и ввести соответствующую терминологию. Пусть надо упорядочить N элементов Назовем их записями, а всю совокупность N записей назовем файлом. Каждая запись Rj имеет ключ Kj, который и управляет процессом сортировки. Помимо ключа, запись может содержать дополнительную, ”сопутствующую информацию”, которая не влияет на сортировку, но всегда остается в этой записи.

Отношение порядка ”5. [24] В неком университете работает около 1000 преподавателей и имеется 500 комитетов. Считается, что каждый преподаватель является членом по крайней мере двух комитетов. Вам нужно подготовить с помощью машины удобочитаемые списки членов всех комитетов. Вы располагаете колодой из приблизительно 1500 перфокарт, сложенных произвольным образом и содержащих следующую информацию:

Членские карточки: колонка 1—пробел; колонки 2–18—фамилия с последующими пробелами;

колонки 19–20—инициалы; колонки 21–23—номер первого Комитета; колонки 24–26—номер второго комитета;... ; колонки 78–80— номер двадцатого комитета (если нужно) или пробелы.

Комитетские карточки: колонка 1—”*”; колонки 2–77—название комитета; колонки 78–80— номер комитета. Как вы должны действовать? (Опишите свой метод достаточно подробно.) 6. [20] Вы работаете с двумя вычислительными системами, в которых по-разному упорядочены литеры (буквы и цифры). Как заставить первую ЭВМ сортировать файлы с буквенно-цифровой информацией, предназначенные для использования на второй ЭВМ?

7. [18] Имеется довольно большой список людей, родившихся в США, с указанием штата, в котором они родились. Как подсчитать число людей, родившихся в каждом штате? (Предполагается, что ни один человек не указан в списке более одного раза.) 8. [20] Чтобы облегчить внесение изменений в большие программы, написанные на ФОРТРАНе, вы хотите написать программу, выпечатывающую таблицу ”перекрестных ссылок”. Входными данными для нее служит программа на ФОРТРАНе, а в результате получается листинг исходной 10 Original pages: 004- программы, снабженный указателем всех случаев употребления каждого идентификатора (т. е.

имени) в программе. Как написать такую программу?

9. [33] (Сортировка каталожных карточек.) Способы составления алфавитных каталогов в разных библиотеках несколько отличаются друг от друга. В следующем ”алфавитном” списке содержатся рекомендации, взятые из правил регистрации и хранения каталожных карточек Американской библиотечной ассоциации (Чикаго, 1942):

R. Accademia nazionale dei Lincei, Rome В названиях иностранных (кроме британских) учреждений слово ”royalty” (королевский) игнорируется Biblioth`que d’histoire rvolutionnaire.

Biblioth`que des curiosits.

Brown, Dr. John, 1810–1882 Указание положения (Dr.) игнорируется Brown-Williams, Reginald Makepeace Дефис рассматривается как пробел Brown & Dallison’s Nevada directory. & в английском тексте превращается в ”and” Brownjohn, Alan Den’, Vladimir Eduardovich, 1867– Апостроф в именах игнорируется Den lieben s ssen mdeln.

Le XIXe si`cle francais.

IBM journal of research and development. Аббревиатуры рассматриваются как ряд однобуквенных слов International Business Machines Corporation al-Khuwrizm Muhammad ibn M s, fl. 813–846 Начальное ”аl-” в арабских именах игнорируется Labour; a magazine for all workers. Заменяется на ”Labor” Labor research association Machine-independent computer programming. Дефис рассматривается как пробел MacMahon, Maj. Percy Alexander, 1854–1929 Указание положения (Maj) игнорируется Mistress of mistresses.

Royal society of London Saint-Sans, Camille, 1835– Seminumerical algorithms.

Uncle Tom’s cabin.

Vandermonde, Alexander Thophile, 1735– Van Valkenburg, Mac Elwyn, 1921– Пробел после префикса в фамилиях игнорируется Von Neumann, John, 1903– The whole art of legerdemain.

Who’s afraid of Virginia Woolf? Апостроф в английском тексте игнорируется Wijngaarden, Adriaan van, 1916– Фамилия никогда не начинается с малой буквы (У большинства из этих правил есть исключения; кроме того, существует много других правил, которые здесь не упомянуты.) Предположим, вам пришлось сортировать большое количество таких карточек с помощью вычислительной машины и впоследствии обслуживать огромную картотеку, причем у вас нет возможности изменить уже сложившиеся порядки заполнения карточек. Как бы вы организовали информацию, чтобы упростить операции включения новых карточек и сортировки?

10. [М21](Дискретные логарифмы.) Пусть известно, что p—(довольно большое) простое число, а a— первообразный корень по модулю p. Следовательно, для любого b в диапазоне 1 b < p существует единственное n, такое, что an mod p = b, 1 n < p. Как по заданному b найти n менее чем за O(n) шагов? [Указание. Пусть m = 11. [М25] (Э. Т. Паркер.) Эйлер выдвинул предположение, что уравнение не имеет решений (за исключением тривиальных) среди целых неотрицательных чисел u, v, w, x, y, z, когда по крайней мере четыре переменные равны нулю. Помимо этого, он предполагал, что уравнение не имеет нетривиальных решений при n 3, но это предположение было опровергнуто: с помощью вычислительной машины найдено тождество 275 + 845 + 1105 + 1335 = 1445 ; см. Л. Дж.

Лэндер, Т. Р. Паркин и Дж. Л. Селфридж, Math. Comp., 21 (1967), 446–459. Придумайте, как можно было бы использовать сортировку для поиска примеров, опровергающих предположение >12. [24] Файл содержит большое количество 30-разрядных двоичных слов: x1,... xN. Придумайте хороший способ нахождения в нем всех дополнительных пар (xi, xj ). (Два слова называются дополнительными, если второе содержит 0 во всех разрядах, в которых были 1 в первом слове, и обратно; таким образом, они дополнительны тогда и только тогда, когда их сумма равна (11... 1)2, если они рассматриваются как двоичные числа.) >13. [25] Имеется файл. содержащий 1000 30-разрядных двоичных слов x1,..., x1000. Как бы вы стали составлять список всех пар (xi, xj ), таких, что xi отличается от xj не более чем в двух разрядах?

14. [22] Как бы вы поступили при отыскании всех пятибуквенных анаграмм, таких, как CARET, CARTE, CATER, CRATE, REACT, TRACE; CRUEL, LUCRE, ULCER; DOWRY, ROWDY, WORDY?

[Если бы вы, скажем, захотели узнать, существуют ли в английском языке наборы из десяти или более анаграмм, кроме замечательной серии:

APERS, ASPER, PARES, PARSE, PEARS, PRASE, RAPES, REAPS, SPARE, SPEAR, к которой можно добавить еще французское слово APRES.] 15. [М28] Пусть даны описания весьма большого числа направленных графов. Каким путем можно сгруппировать изоморфные графы? (Два направленных графа называются изоморфными, если 12 Original pages: 004- существует взаимно однозначное соответствие между их вершинами и взаимно однозначное соответствие между их дугами, причем эти соответствия сохраняют инцидентность вершин и дуг.) 16. [30] В некоторой группе из 4096 человек каждый имеет около 100 знакомых. Был составлен список всех пар людей, знакомых между собой. (Это отношение симметрично, т. е. если x знаком с y, то и y знаком с x. Поэтому список содержит примерно 200000 пар.) Придумайте алгоритм, который по зaдaннoмy k выдавал бы все клики из k человек. (Клика — это группа людей, в которой все между собой знакомы.) Предполагается, что слишком больших клик не бывает.

17. [30] Три миллиона человек с различными именами были уложены рядом непрерывной цепочкой от Нью-Йорка до Калифорнии. Каждому из них дали листок бумаги, на котором он написал свое имя и имя своего ближайшего западного соседа. Человек, находившийся в самой западной точке цепи, не понял, что ему делать, и выкинул свой листок. Остальные 2999999 листков собрали в большую корзину и отправили в Национальный архив, в Вашингтон, округ Колумбия. Там содержимое корзины тщательно перетасовали и записали на магнитные ленты.

Специалист по теории информации определил, что имеется достаточно информации для восстановления списка людей в исходном порядке. Специалист по программированию нашел способ сделать это менее чем за 1000 просмотров лент с данными, используя лишь последовательный доступ к файлам на лентах и небольшое количество памяти с произвольным доступом. Как ему это удалось?

[Другими словами, как, имея расположенные произвольным образом пары (xi, xi+1 ), 1 i < N, где все xi различны, получить последовательность x1, x2,..., xN, применяя лишь методы последовательной обработки данных, пригодные для работы с магнитными лентами? Это задача сортировки в случае, когда трудно определить, какой из двух ключей предшествует другому; мы уже поднимали этот вопрос в упр. 2.2.3–25.]

5.1. * КОМБИНАТОРНЫЕ СВОЙСТВА ПЕРЕСТАНОВОК

Перестановкой конечного множества называется некоторое расположение его элементов в ряд.

Перестановки особенно важны при изучении алгоритмов сортировки, так как они служат для представления неупорядоченных исходных данных. Чтобы исследовать эффективность различных методов сортировки, нужно уметь подсчитывать число перестановок, которые вынуждают повторять некоторый шаг алгоритма определенное число раз.

Мы, конечно, уже не раз встречались с перестановками в гл. 1, 2 и 3. Например, в п. 1.2. обсуждались два основных теоретических метода построения n! перестановок из n объектов; в п.

1.3.3 проанализированы некоторые алгоритмы, связанные с циклической структурой и мультипликативными свойствами перестановок; в п. 3.3.2 изучены их отрезки монотонности. Цель настоящего параграфа—изучить некоторые другие свойства перестановок и рассмотреть общий случай, когда допускается наличие одинаковых элементов. Попутно мы узнаем многое о комбинаторной математике.

Свойства перестановок настолько красивы, что представляют и самостоятельный интерес. Удобно будет дать их систематическое изложение в одном месте, а не разбрасывать материал по всей главе.

Читателям, не имеющим склонности к математике, а также тем, кто жаждет поскорее добраться до самих методов сортировки, рекомендуется перейти сразу к § 5.2, потому что настоящий параграф непосредственного отношения к сортировке почти не имеет.

Пусть a1 a2... an —перестановка множества {1, 2,..., n}. Если i < j, a ai > aj, то пара (ai, aj ) называется инверсией перестановки; например, перестановка 3 1 4 2 имеет три инверсии: (3, 1), (3, 2) и (4, 2). Каждая инверсия—это пара элементов, ”нарушающих порядок”; следовательно, единственная перестановка, не содержащая инверсий,—это отсортированная перестановка 1 2... n. Такая связь с сортировкой и есть главная причина нашего интереса к инверсиям, хотя это понятие уже использовалось нами при анализе алгоритма динамического распределения памяти (см. упр. 2.2.2–9).

Понятие инверсии ввел Г. Крамер в 1750 г. [Intr. a 1’Analyse des Lignes Courbes algbriques e (Geneva, 1750), 657–659; ср. с Томас Мюир, Тhеогу of Determinants, 1 (1906), 11–14] в связи со своим замечательным правилом решения линейных уравнений. В сущности, он определил детерминант n n-матрицы следующим образом:

где сумма берется по всем перестановкам a1 a2... an, а I(a1 a2... an )—число инверсий в перестановке.

Таблицей инверсий перестановки a1 a2... an называется последовательность чисел b1 b2... bn, где bj —число элементов, больших j и расположенных левее j. (Другими словами, bj —число инверсий, у которых второй элемент равен j.) Например, таблицей инверсий перестановки будет поскольку 5 и 9 расположены левее 1; 5, 9, 8—левее 2 и т.д., всего 20 инверсий. По определению Пожалуй, наиболее важный факт, касающийся перестановок, и установленный Маршаллом Холлом, это то, что таблица инверсий единственным образом определяет соответствующую перестановку. [См. Proc. Symp. Applied Math., 6 (American Math. Society, 1956), 203.] Из любой таблицы инверсий b1 b2... bn, удовлетворяющей условиям (3), можно однозначно восстановить перестановку, которая порождает данную таблицу, путем последовательного определения относительного расположения элементов n, n 1,..., 1 (в этом порядке). Например, перестановку, соответствующую (2), можно построить следующим образом: выпишем число 9; так как b8 = 1, то 8 стоит правее 9. Поскольку b7 = 2, то 7 стоит правее 8 и 9. Так как b6 = 2, то 6 стоит правее двух уже выписанных нами чисел;

таким образом, имеем Припишем теперь 5 слева, потому что b5 = 0; помещаем 4 вслед за четырьмя из уже записанных чисел, 3—после шести выписанных чисел (т. е. в правый конец) и получаем Вставив аналогичным образом 2 и 1, придем к (1).

Такое соответствие важно, потому что часто можно заменить задачу, сформулированную в терминах перестановок, эквивалентной ей задачей, сформулированной в терминах таблиц инверсий, которая, возможно, решается проще. Рассмотрим, например, самый простой вопрос: сколько существует перестановок множества {1, 2,..., n}? Ответ должен быть равен числу всевозможных таблиц инверсий, а их легко пересчитать, так как b1 можно выбрать n различными способами, b2 можно независимо от b 1 выбрать n 1 способами,..., bn —одним способом; итого n(n 1)... 1 = n! различных таблиц инверсий. Таблицы инверсий пересчитать легче, потому что b независимы, в то время как a должны быть все различны.

В п. 1:2.10 мы исследовали задачу о числе локальных максимумов перестановки, если читать ее справа налево; иными словами, требовалось подсчитать количество элементов, каждый из которых больше любого из следующих после него. (Например, правосторонние максимумы в (1)—это 9, 8, и 3.) Оно равно количеству индексов j, таких, что bj = n j. Так как b1 принимает значение n с вероятностью 1/n, b2 (независимо) принимает значение n 2 с вероятностью 1/(n 1) и т.д., то из рассмотрения инверсий ясно, что среднее число правосторонних максимумов равно Аналогичным способом легко получить и соответствующую производящую функцию.

Другие применения таблиц инверсий встретятся далее в этой главе в связи с конкретными алгоритмами сортировки.

Ясно, что если поменять местами соседние элементы перестановки, то общее число инверсий увеличится или уменьшится на единицу. На рис. 1 показаны 24 перестановки множества {1, 2, 3, 4};

линиями соединены перестановки, отличающиеся друг от друга положением двух соседних элементов; двигаясь вдоль линии вниз, мы увеличиваем число инверсий на единицу. Следовательно, число инверсий в перестановке n равно длине нисходящего пути из 1 2 3 4 в n на рис. 1; все такие пути должны иметь одинаковую длину.

Заметим, что эту диаграмму можно рассматривать как трехмерное твердое тело—”усеченный октаэдр”, имеющий 8 шестиугольных и 6 квадратных граней. Это один из равномерных многогранников, которые обсуждал Архимед (см. упр. 10).

Picture: Рис. 1. Усеченный октаэдр, на котором показано изменение числа инверсий, когда меняются местами два соседних элемента перестановки;

14 Original pages: 004- Не следует путать ”инверсии” перестановок с обратными перестановками. Вспомним, что перестановку можно записывать в виде двух строк обратной к этой перестановке называется перестановка a1, a2,... an, которая получается, если в (4) поменять местами строки, а затем упорядочить столбцы в возрастающем порядке по верхним элементам:

Например, обратной к перестановке 5 9 1 8 2 6 4 7 3 будет перестановка 3 5 9 7 1 6 8 4 2, так как Можно дать другое определение обратной перестановки: aj = k тогда и только тогда, когда ak = j.

Обратную перестановку впервые ввёл X. А. Роте [в К.F. Hindenburg(ed.)., Sammlung combinatorisch-analytischer Abhandlungen, 2 (Leipzig, 1800), 263–305]; он заметил интересную связь между обратными перестановками и инверсиями: обратная перестановка содержит ровно столько же инверсий, сколько исходная. Роте дал не самое простое доказательство этого факта, но оно поучительно и притом довольно красиво. Построим таблицу размера nn и поставим точки в j-й клетке i-й строки, если ai = j. После этого расставим крестики во всех клетках, снизу от которых (в том же столбце) и справа (в той же строке) есть точки. Например, для 5 9 1 8 2 6 4 7 3 диаграмма будет такой:

Количество крестиков равно числу инверсий, так как нетрудно видеть, что bj равно числу крестиков в j-м столбце. Если мы теперь транспонируем диаграмму (поменяв ролями строки и столбцы), то получим диаграмму для обратной по отношению к исходной перестановке; значит, число крестиков (число инверсий) одинаково в обоих случаях. Роте использовал этот факт для доказательства того, что детерминант матрицы не меняется при транспонировании.

Для анализа некоторых алгоритмов сортировки необходимо знать число перестановок n элементов, содержащих ровно k инверсий. Обозначим это число через In (k); в табл. 1 приведены первые несколько значений этой функции.

Из рассмотрения таблицы инверсий b1 b2....bn ясно, что Ik (0) = 1, In (1) = n 1 и что выполняется свойство симметрии:

Далее, так как значения b можно выбирать независимо друг от друга, то нетрудно видеть, что производящая функция удовлетворяет соотношению Gn (z) = (1 + z + · · · + z n1 )Gn1 (z); следовательно, она имеет довольно, простой вид С помощью этой производящей функции можно легко продолжить табл. 1 и убедиться, что числа, расположенные под ступенчатой линией в таблице, удовлетворяют соотношению (Для чисел над ступенчатой линией это соотношение не выполняется.) Более сложные рассуждения (см. упр. 14) показывают, что на самом деле имеют место формулы Общая формула для In (k) содержит около 1.6 k слагаемых:

где uj = (3j 2 j)/2 — так называемое ”пятиугольное число”.

Разделив Gn (z) на n!, получим производящую функцию gn (z) распределения вероятностей числа инверсий в случайной перестановке n элементов. Она равна произведению где hk (z) = (1+z +z 2 +· · ·+z k1 )/k — производящая функция равномерного распределения случайной величины, принимающей целые неотрицательные значения, меньшие k. Отсюда Таким образом, среднее число инверсий довольно велико—около 1 n2 ; стандартное отклонение также весьма велико—около 1 n3/2.

В качестве интересного завершения изучения инверсий рассмотрим одно замечательное открытие, принадлежащее П. А. Мак-Магону [Amer. J. Math., 35 (1913), 281–322]. Определим индекс перестановки a1 a2... an как сумму всех j, таких, что aj > aj+1, 1 < n. Например, индекс перестановки 5 9 1 8 2 6 4 7 3 равен 2 + 4 + 6 + 8 = 20. Индекс случайно совпал с числом инверсий. Если составить список всех 24 перестановок множества {1, 2, 3, 4}, а именно Перестановка Индекс Инверсии Перестановка Индекс Инверсии 16 Original pages: 004- то видно, что число перестановок, имеющих данный индекс k, равно числу перестановок, имеющих k инверсий.

На первый взгляд этот факт может показаться почти очевидным, однако после некоторых размышлений он начинает казаться чуть ли не мистическим, и не видно никакого простого прямого его доказательства. Мак-Магон нашел следующее остроумное косвенное доказательство: пусть J(a1 a2... an )—индекс перестановки a1 a2... an, и соответствующая производящая функция есть где сумма берется по всем перестановкам множества {1, 2,...., n}. Мы хотели бы доказать, что Hn (z) = Gn (z). Для этого определим взаимно однозначное соответствие между n-ками (q1, q2,..., qn ) неотрицательных целых чисел, с одной стороны, и упорядоченными парами n-ок с другой стороны; здесь a1 a2... an —перестановка множества {1, 2,..., n} и p1 p2... pn 0.. Это соответствие будет удовлетворять условию Производящая функция чисел (q1, q2,..., qn ), равна Qn (z) = 1/(1 z)z ; а производящая функция z p1 +p2 +···+pn, где сумма берется по всем n-кам целых чисел (p1, p2,... pn ), таких, что p1 p2... pn 0, равна, как показано в упр. 15, Существование взаимно однозначного соответствия, которое удовлетворяет условию (15) и которое мы собираемся установить, доказывает равенство Qn (z) = Hn (z)Pn (z), т.е.

Требуемое соответствие определяется с помощью алгоритма ”сортировки”. Начав с пустого списка, при k = 1, 2,..., n (в таком порядке) вставляем в этот список числа qk следующим образом: пусть после k 1 шагов в списке содержатся элементы p1, p2,..., pk1, где p1 p2... pk1, и определена перестановка a1 a2... an множества {n, n 1,..., n k + 2}. Пусть j—единственное целое число, такое, что pj > qk pj+1 ; если qk p1, то полагаем j = 0, а если pk1 > qk, то полагаем j = k 1. Вставим теперь qk в список между pj и pj+1, а целое число (nk +1)—в перестановку между aj, и aj+1. Проделав это для всех k, получим перестановку a1 a2... an множества {1, 2,..., n} и n-ку чисел (p1, p2,..., pn ), Наконец, для 1 j < n вычтем единицу из всех чисел p1,..., pj при всех j, таких, что aj > aj+1.

Полученная пара ((a1, a2,..., an ), (p1, p2,..., pn )) удовлетворяет условию (15).

Пусть, например, n = 6 и (q1,..., q6 ) = (3, 1, 4, 0, 0, 1). Построение происходит следующим образом:

После заключительной корректировки получаем (p1,..., p6 ) = (2, 1, 0, 0, 0, 0).

Нетрудно проверить, что этот процесс обратим; таким образом, требуемое соответствие установлено и теорема Мак-Магона доказана. Аналогичное взаимно однозначное соответствие встретится 1. [10] Какова таблица инверсий для перестановки 2 7 1 8 4 5 9 3 6? Какой перестановке соответствует 2. [M15] Решением задачи Иосифа, сформулированной в упр. 1.3.2–22, является перестановка множества {1, 2,... n}; решение для приведенного там примера (n = 8, m = 4)—перестановка 5 4 3 8 7 2. Соответствующая этой перестановке таблица инверсий—3 6 3 1 0 0 1 0. Найдите простое рекуррентное соотношение для элементов b1 b2... bn таблицы инверсий в общей задаче Иосифа для n человек, если казнят каждого m-го человека.

3. [18] Пусть перестановке a1 a2... an соответствует таблица инверсий b1 b2... bn ; какой перестановке a1 a2... an соответствует таблица инверсий >4. [20] Придумайте алгоритм, годный для реализации на ЭВМ, который по данной таблице инверсий b1 b2... bn, удовлетворяющей условиям (3), строил бы соответствующую перестановку a1 a2... an.

[Указание: вспомните методы работы со связанной памятью.] 5. [35] Для выполнения на типичной ЭВМ алгоритм из упр. 4 требует времени, приблизительно пропорционального n2 ; можно ли создать алгоритм, время работы которого было бы существенно >6. [26] Придумайте алгоритм вычисления таблицы инверсий b1 b2... bn, соответствующей данной перестановке a1 a2... an множества {1, 2,..., n}, время работы которого на типичной ЭВМ было 7. [20] Помимо таблицы b1 b2... bn, определенной в этом пункте, можно определить некоторые другие типы таблиц инверсий, соответствующих данной перестановке a1 a2... an множества {1, 2,..., n}.

В этом упражнении мы рассмотрим три других типа таблиц инверсий, которые возникают в приложениях.

Пусть cj —число инверсий, первая компонента которых равна j, т. е. число элементов, меньших j и расположенных правее j. [Перестановке (1) соответствует таблица 0 0 0 1 4 2 1 5 7; ясно, что 0 cj < j.] Пусть Bj = baj и Cj = caj.

Покажите, что при 1 j n справедливы неравенства 0 Bj < j и 0 Cj n j; покажите также, что перестановку a1 a2... an можно однозначно определить, если задана или таблица c1 c 8. [М24] Сохраним обозначения упр. 7; пусть a1 a2... an —перестановка, обратная к a1 a2... an и пусть соответствующие ей таблицы инверсий— b1 b2... bn, c1 c2... cn, B1 B2... Bn и C1 C2... Cn.

Найдите как можно больше интересных соотношений между aj, bj, cj, Bj, Cj, aj, bj, cj, Bj, Cj.

>9. [М21] Докажите, что в обозначениях упр. 7 перестановка a1 a2... an обратна самой себе тогда и 10. [ВМ20] Рассмотрите рис. 1 как многогранник в трехмерном пространстве. Чему равен диаметр усеченного октаэдра (расстояние между вершинами 1234 и 4321), если все ребра имеют единичную длину?

11. [М25] (а) Пусть = a1 a2... an —перестановка множества {1, 2,..., n}, E(x) = {(ai, aj )|i < j, ai > aj }—множество ее инверсий, a —множество ее ”неинверсий”. Докажите, что E() и E() транзитивны. [Множество S упорядоченных пар называется транзитивным, если для любых (a, b) и (b, c), принадлежащих S, пара (a, c) также принадлежит S.] (b) Обратно, пусть E—любое транзитивное подмножество множества T = {(x, y)|1 y < x n}, дополнение которого T \E транзитивно. Докажите, что существует перестановка, такая, что E() = E.

12. [М28] Используя обозначения предыдущего упражнения, докажите, что если 1 и 2 — перестановки, а E—минимальное транзитивное множество, содержащее E(1 ) E(2 ), то E—тоже транзитивное множество. [Следовательно, если мы будем говорить, что 1 находится ”над” 2, когда E(1 ) E(2 ), то определена решетка перестановок; существует единственная ”самая низкая” перестановка, находящаяся ”над” двумя данными перестановками. Диаграмма решетки при n = 4 представлена на рис. 1.] 1. [М23] Известно, что в разложении определителя половина членов выписывается со знаком +, а половина—со знаком. Другими словами, при n 2 перестановок с четным числом инверсий ровно столько же, сколько с нечетным. Покажите, что вообще при n m количество перестановок с числом инверсий, конгруэнтным t mod m, равно n!/m, независимо от того, каково целое 18 Original pages: 034- 2. [М24] (Ф. Франклин.) Разбиение числа n на k различных частей— это представление n в виде суммы n = p1 + p2 + · · · + pk, где p1 > p2 >... > pk > 0. Например, разбиения числа 7 на различные Picture: Рис. 2. Соответствие Франклина между разбиениями на различные части.

Пусть fk (n)—число разбиений n на k различных частей. Докажите, что k (1)k fk (n) = 0, если только n не представляется в виде (3j 2 ± j)/2 при некотором неотрицательном целом j; в этом случае сумма равна (1)j. Например, для n = 7 сумма равна 1 + 3 1 = 1, потому что 7 = (3 · 22 + 2)/2. [Указание. Представьте разбиения в виде массива точек, в i-й строке которого имеется pi точек, 1 i k. Найдите наименьшее j, такое, что pj+1 < pj 1, и обведите крайние правые точки первых j строк. Если j < pk, то эти j точек можно, как правило изъять из массива, повернуть на 45 и поместить в новую, (k + 1)-ю строку. С другой стороны, если j pk, то обычно можно изъять из массива k-ю строку точек, повернуть ее на 45 и поместить справа от обведенных точек (рис. 2). В результате этого процесса в большинстве случаев разбиения с четным числом строк и разбиения с нечетным числом строк группируются в пары, таким образом, в сумме надо учитывать только непарные разбиения.] Замечание. В качестве следствия получаем формулу Эйлера тем не менее можно следующим образом обеспечить единственность. ”Существует линейное упорядочение на множестве простых перестановок, такое, что каждая перестановка мультимножества имеет единственное разложение 1 2... n на простые множители, удовлетворяющее 11. [М26] Пусть 1, 2,..., t —циклы без повторяющихся элементов. Определим частичное упорядочение на множестве t элементов { x1,..., xt }, полагая xi xj, если i < j и i имеет по крайней мере одну общую букву с j. Докажите следующую связь между теоремой C и понятием ”топологической сортировки” (п. 2.2.3): число различных разложений перестановки 1 2... t на простые множители равно количеству способов топологически отсортировать данное частичное упорядочение. (Например, в соответствии с (22) существует пять способов топологически отсортировать упорядочение x1 x3, x2 x4, x1 x4.) Обратно, если на множестве из t элементов задано какое-то частичное упорядочение, то существует множество циклов которое определяет это частичное упорядочение указанным способом.

12. [М16] Покажите, что соотношения (29) являются следствиями предположений (28).

13. [М21] Докажите, что число перестановок мультимножества { A · a, B · b, C · c, D · d, E · e, F · f }, не содержащих пар стоящих рядом букв c a и d b, равно 14. [M30] Один из способов определить перестановку 1, ”обратную” перестановке, который подсказан нам другими определениями этого пункта, это поменять местами строки двустрочного представления и затем выполнить устойчивую сортировку столбцов, так чтобы элементы верхней строки расположились в неубывающем порядке. Например, если a < b < c < d, то из этого Исследуйте свойства этой операции обращения; имеется ли, например, какая-нибудь простая связь между ней и соединительным произведением? Можно ли подсчитать число перестановок, таких, что = 1 ?

>15. [М25] Докажите, что перестановка a1... an мультимножества где x1 < x2 <... < xn и n1 + n2 + · · · + nm = n, является циклом тогда и только тогда, когда направленный граф с вершинами { x1, x2,..., xm } и дугами из xj в an1 +···+nj содержит ровно один ориентированный цикл. В этом случае число способов представить перестановку в виде цикла равно длине этого ориентированного цикла. Например, направленным графом, соответствующим перестановке а два способа представить перестановку в виде цикла—это (b a d d c a c a b c) и (c a d d c a c b a b).

16. [М35] В предыдущем пункте, формула (8), мы нашли производящую функцию для инверсий перестановок в частном случае, когда в перестановке участвуют элементы множества. Покажите, что в общем случае перестановок мультимножества производящая функция для инверсий равна ”z-мультиномиальному коэффициенту” [Ср. с (3); z-биномиальные коэффициенты определены в формуле (1.2.6-37).] 17. [M24] Пользуясь производящей функцией, найденной в упр. 16, вычислите среднее значение и дисперсию для числа инверсий в случайной перестановке мультимножества.

18. [M30] (П. А. Мак-Магон.) Индекс перестановки a1 a2... an был определен в предыдущем пункте; мы доказали, что число перестановок данного множества, имеющих данный индекс k, равно числу перестановок, имеющих k инверсий. Верно ли это для перестановок заданного мультимножества?

19. [ВМ28] Определим функцию Мёбиуса µ() перестановки : она равна 0, если содержит повторяющиеся элементы, и (1)k в противном случае, если —произведение k простых перестановок.

(Ср. с определением обычной функции Мёбиуса, упр. 4.5.2-10.) (a) Докажите, что если =, то где сумма берется по всем перестановкам, являющимся левыми сомножителями в разложении (т. е. =, где —некоторая перестановка) (b) Докажите, что если x1 < x2 <... < xm ограниченные парами черточек. Например, в перестановке —четыре отрезка. Мы нашли среднее число отрезков длины k в случайной перестановке множества { 1, 2,..., n }, а также ковариацию числа отрезков длины j и длины k. Отрезки важны при изучении алгоритмов сортировки, так как они представляют упорядоченные сегменты данных. Поэтому-то мы теперь вновь вернемся к вопросу об отрезках. Обозначим через число перестановок множества { 1, 2,..., n }, имеющих ровно k возрастающих отрезков. Такие числа n возникают и в других контекстах; их обычно называют числами Эйлера, потому что Эйлер обсудил их в своей знаменитой книге Institutiones calculi differentialis (St. Petersburg, 1755), 485– 487 [Euler, Opera Omnia, (1) 10 (1913), 373–375]; их следует отличать от ”эйлеровых чисел”, о которых идет речь в упр. 5.1.4-22.

Из любой данной перестановки множества { 1, 2,..., n 1 } можно образовать n новых перестановок, вставляя элемент n во все возможные места. Если в исходной перестановке содержалось k отрезков, то ровно k новых перестановок будут иметь k отрезков; в остальных n k перестановках будет по k + 1 отрезков, поскольку всякий раз, когда n вставляется не в конец уже существующего отрезка, число отрезков увеличивается на единицу. Например, среди шести перестановок, полученных из перестановки 3 1 2 4 5, все, кроме второй и последней, содержат по три отрезка вместо исходных двух. Отсюда имеем рекуррентное соотношение Условимся, что т. е. будем считать, что в пустой перестановке содержится один отрезок. Читатель, возможно, найдет небезынтересным сравнить (2) с рекуррентным соотношением для чисел Стирлинга [формулы (1.2.6В табл. 1 приведены числа Эйлера для малых n.

В табл. 1 можно заметить некоторые закономерности. По определению имеем Выполняется также свойство симметрии которое вытекает из того факта, что каждой перестановке a1 a2... an, содержащей k отрезков, соответствует перестановка an... a2 a1, содержащая n + 1 k отрезков.

Другое важное свойство чисел Эйлера выражается формулой которую можно доказать, используя понятие сортировки. Рассмотримmn последовательностей a1 a2... an, где 1 ai m. Любую такую последовательность можно устойчиво отсортировать таким образом, чтобы элементы расположились в неубывающем порядке:

где i1 i2... in —однозначно определенная перестановка множества { 1, 2,..., n }, такая, что ij < ij+1, если aij = aij+1 ; другими словами, из ij > ij+1 следует aij < aij+1. Покажем, что если в перестановке i1 i2... in содержится k отрезков, то число соответствующих ей последовательностей a1 a2... an равно m+nk ; тем самым будет доказана формула (8), если заменить k на n + 1 k.

30 Original pages: 046- Пусть, например, n = 9, i1 i2... in = 3 5 7 1 6 8 9 4 2 и требуется подсчитать число последовательностей a1 a2... a9, таких, что оно равно числу последовательностей b1 b2... b9, таких, что так как можно положить b1 = a3, b2 = a5 + 1, b3 = a7 + 2, b4 = a1 + 2, b5 = a6 + 3 и т. д. Число способов, которыми можно выбрать элементы b, равно просто-напросто числу способов выбрать 9 предметов из m + 5, т. е. m+5 ; аналогичное доказательство годится для произвольных n и k и любой перестановки i1 i2... in с k отрезками.

Так как в обеих частях равенства (8) стоят полиномы от m, то вместо m можно подставить любое действительное число, получив интересное выражение степеней через последовательные биномиальные коэффициенты:

Например, В основном благодаря именно этому свойству числа Эйлера весьма полезны при изучении дискретной математики. Положив в (11) x = 1, докажем еще раз, что поскольку биномиальные коэффициенты обращаются в 0 во всех слагаемых, кроме последнего. Положив x = 2, получим Подставив x = 3, 4,..., убедимся, что все числа полностью определяются соотношением (11), и придем к формуле, впервые найденной Эйлером:

Изучим теперь производящую функцию для отрезков. Если положить то коэффициент при z k равен вероятности того, что случайная перестановка множества { 1, 2,..., n } содержит ровно k отрезков. Поскольку k отрезков в перестановке столь же вероятны, как и n + 1 k, то среднее число отрезков должно равняться 1 (n + 1), и, следовательно, gn (1) = 1 (n + 1). В упр. 2(b) показано, что имеет место простая формула для всех производных функции gn (z) в точке z = 1:

Так, в частности, дисперсия gn (1) + gn (1) gn (1)2 равна (n + 1)/12 при n 2, что указывает на довольно устойчивое распределение около среднего значения. (Мы нашли эту же величину в упр. 3.3.2-18; там она называлась covar(R1, R1 ).) Функция gn (z)—полином, поэтому с помощью формулы (15) можно разложить ее в ряд Тейлора Второе равенство следует из первого, так как по свойству симметрии (7) Из рекуррентного соотношения для чисел Стирлинга получаются два чуть более простых представления:

Производящая функция от двух переменных равна, следовательно, это еще одно соотношение, обсуждавшееся Эйлером.

Другие свойства чисел Эйлера можно найти в обзорной статье Л. Карлица [Math. Magazine, (1959), 247–260]; см. также Дж. Риордан, Введение в комбинаторный анализ, ИЛ, М., 1963, стр. 50, 253, 254.

Рассмотрим теперь длину отрезков; какова в среднем длина отрезка? В п. 3.3.2 мы уже изучили математическое ожидание числа отрезков данной длины; средняя длина отрезка равна примерно 2 в согласии с тем фактом, что в случайной перестановке длины n содержится в среднем 1 (n+1) отрезков.

Применительно к алгоритмам сортировки полезна несколько отличная точка зрения; рассмотрим длину k-го слева отрезка перестановки при k = 1, 2,....

Какова, например, длина первого (крайнего слева) отрезка случайной перестановки a1 a2... an ?

Его длина всегда 1; она 2 ровно в половине случаев (а именно, если a1 < a2 ). Его длина 3 ровно для 1/6 случаев (если a1 < a2 < a3 ). Вообще его длина m с вероятностью qm = 1/m! при 1 m n.

Следовательно, вероятность того, что длина этого отрезка равна в точности m, есть Средняя длина равна, таким образом, Предел при n равен e 1 = 1.71828..., а для конечных n это значение равно e 1 n, где n довольно мало:

В оригинале ”super generating function”. Соответствующего термина в отечественной литературе не существует.—Прим. ред.

32 Original pages: 046- Поэтому для практических целей удобно рассмотреть отрезки случайной бесконечной последовательности различных чисел под ”случайностью” последовательности мы здесь подразумеваем то, что все n! возможных взаимных расположении первых n элементов последовательности равновероятны. Так что средняя длина первого отрезка случайной бесконечной последовательности равна e 1.

Несколько усовершенствовав этот метод, можно установить среднюю длину k-го отрезка случайной последовательности. Пусть qkm —вероятность того, что общая длина первых k отрезков m; тогда qkm равно величине 1/m!, умноженной на число перестановок множества { 1, 2,..., m }, содержащих не более k отрезков:

Вероятность того, что общая длина первых k отрезков равна m, есть qkm qk(m+1). Следовательно, обозначив через Lk среднюю длину k-го отрезка, находим, что Вычитая L1 + · · · + Lk1 и используя значения qkm, из (23) получаем нужную нам формулу:

Поскольку k = 0 при k = 1, значение Lk оказывается равным коэффициенту при z k в производящей функции g(z, 1) z. (см. (19)); таким образом, имеем Из формулы Эйлера (13) получим представление Lk в виде полинома от e:

Эту формулу для Lk впервые получила Б. Дж. Гэсснер [CACM, 10 (1967), 89–93]. Имеем, в частности, Итак, следует ожидать, что второй отрезок будет длиннее первого, а третий отрезок будет в среднем еще длиннее! На первый взгляд это может показаться странным, но после минутного размышления становится ясно, что, поскольку первый элемент второго отрезка будет скорее всего малым числом (именно это служит причиной окончания первого отрезка), у второго отрезка больше шансов оказаться длиннее, чем у первого. Тенденция такова, что первый элемент третьего отрезка будет даже меньше, чем первый элемент второго отрезка.

Числа Lk важны в теории сортировки посредством выбора с замещением (п. 5.4.1), поэтому интересно подробно изучить их значения. В табл. 2, вычисленной Дж. У. Ренчем (мл.), приведены первые 18 значений Lk с точностью до 15 десятичных знаков. Рассуждения, приведенные в предыдущем абзаце, могут вызвать подозрение, что Lk+1 > Lk ; на самом же деле значения колеблются, то возрастая, то убывая. Заметим, что Lk быстро приближаются к предельному значению 2; весьма примечательно то, что эти нормированные полиномы от трансцендентного числа e так быстро сходятся к рациональному числу 2! Полиномы (26) представляют некоторый интерес и с точки зрения численного анализа, будучи прекрасным примером потери значащих цифр при вычитании почти равных чисел; используя 19-значную арифметику с плавающей точкой, Гэсснер пришла к неверному заключению о том, что L12 > 2, а Ренч отметил, что 42-значная арифметика с плавающей точкой дает L28 лишь с точностью до 29 значащих цифр.

Асимптотическое поведение Lk можно определить, исходя из простых положений теории функций комплексного переменного.

Рис. 3 Корни уравнения ez1 = z. Пунктирная линия соответствует уравнеPicture:

Знаменатель в (25) обращается в нуль лишь при ez1 = z, т. е. (полагая z = x + iy) когда На рис. 3, где нанесены оба графика этих уравнений, видно, что они пересекаются в точках z = z0, z1, z1, z2, z2,... ; здесь z0 = 1, и при больших k мнимая часть (zk+1 ) равна приблизительно (zk ) + 2. Так как и этот предел равен 2 при k = 0, то функция не имеет особенностей в комплексной плоскости при |z| < |zm+1 |. Значит, Rm (z) можно разложить в степенной ряд k k z k, который сходится абсолютно при |z| < |zm+1 |; отсюда следует, что k M k при k, где M = |zm+1 |. Коэффициентами для L(z) служат коэффициенты разложения функции а именно если положить Отсюда можно проследить асимптотическое поведение Ln. Имеем 34 Original pages: 061- таким образом, главный вклад в Ln 2 дают r1 и 1, и ряд (29) сходится очень быстро. Приведенные здесь значения r1 и 1 найдены Дж. У. Ренчем (мл.) Дальнейший анализ [W. W. Hooker, CACM, 12 (1969), 411–413] показывает, что Rm (z) z при m ; следовательно, ряд 2 k0 zk cos nk действительно сходится к Ln при n > 1.

Можно провести более тщательное исследование вероятностей, чтобы полностью определить распределение вероятностей для длины k-го отрезка и для общей длины первых k отрезков (см. упр. 9, 10, 11), Оказывается сумма L1 + · · · + Lk асимптотически приближается к 2k 1/3.

В заключение этого пункта рассмотрим свойства отрезков в случае, когда в перестановке допускаются одинаковые элементы. Бесчисленные пасьянсы, которым посвящал свои досуги знаменитый американский астроном 19-го века Саймон Ньюкомб, имеют непосредственное отношение к интересующему нас вопросу. Он брал колоду карт и складывал их в одну стопку до тех пор, пока они шли в неубывающем порядке по старшинству; как только следующая карта оказывалась младше предыдущей, он начинал новую стопку. Он хотел найти вероятность того, что в результате вся колода окажется разложенной в заданное количество стопок.

Задача Саймона Ньюкомба состоит, следовательно, в нахождении распределения вероятностей для отрезков случайной перестановки мультимножества. В общем случае ответ довольно сложен (см. упр. 12), хотя мы уже видели, как решать задачу в частном случае, когда все карты различны по старшинству. Мы удовлетворимся здесь выводом формулы для среднего числа стопок в этом пасьянсе.

Пусть имеется m различных типов карт и каждая встречается ровно p раз. Например, в обычной колоде для бриджа m = 13, а p = 4, если пренебрегать различием масти. Замечательную симметрию обнаружил в этом случае П. А. Мак-Магон [Combinatory Analysis (Cambridge, 1915), том 1, стр. 212– 213]: число перестановок с k + 1 отрезками равно числу перестановок с mp p k + 1 отрезками.

Это соотношение легко проверить при p = 1 (формула (7)), однако при p > 1 оно кажется довольно неожиданным.

Можно доказать это свойство симметрии, установив взаимно однозначное соответствие между перестановками, такое, что каждой перестановке с k + 1 отрезками соответствует другая, с mp p k+1 отрезками. Мы настойчиво рекомендуем читателю самому попробовать найти такое соответствие, прежде чем двигаться дальше.

Какого-нибудь очень простого соответствия на ум не приходит; доказательство Мак-Магона основано на производящих функциях, а не на комбинаторном построении. Однако установленное Фоатой соответствие (теорема 5.1.2В) позволяет упростить задачу, так как там утверждается существование взаимно однозначного соответствия между перестановками с k + 1 отрезками и перестановками, в двустрочном представлении которых содержится ровно k столбцов x, таких, что x < y.

Пусть дано мультимножество { p · 1, p · 2,..., p · m }; рассмотрим перестановку с двустрочным обозначением Сопоставим с ней другую перестановку того же мультимножества:

где x = m + 1 x. Если перестановка (32) содержит k столбцов вида x, таких, что x < y, то (33) содержит (m 1)p k таких столбцов, потому что необходимо рассмотреть лишь случай y > 1, а неравенство x < y эквивалентно x m + 2 y. Поскольку (32) соответствует перестановке с k + 1 отрезками, а (33)—перестановке с mp p k + 1 отрезками и преобразование, переводящее (32) в (33), обратимо (оно же переводит (33) в (32)), то тем самым доказано условие симметрии Мак-Магона.

Пример этого построения содержится в упр. 14.

В силу свойства симметрии среднее число отрезков в случайной перестановке должно равняться 1 ((k + 1) + (mp p k + 1)) = 1 + 1 p(m 1). Например, для стандартной колоды среднее число стопок в пасьянсе Ньюкомба равно 25 (так что раскладывание этого пасьянса вряд ли покажется столь уж увлекательным занятием).

На самом деле, используя весьма простое рассуждение, можно определить среднее число отрезков в общем случае для любого данного мультимножества { n1 · x1, n2 · x2,..., nm · xm }, где все x различны.

Пусть n = n1 +n2 +· · ·+nm, и представим себе, что все перестановки a1 a2... an этого мультимножества записаны в явном виде; посмотрим, как часто ai оказывается больше ai+1 при каждом фиксированном значении i, 1 i < n. Число случаев, когда ai > ai+1, равно в точности половине числа случаев, когда ai = ai+1, и нетрудно видеть, что ai = ai+1 = xj ровно в N nj (nj 1)/n(n 1) случаях, где N — общее число перестановок. Следовательно, ai = ai+1 ровно в случаях, a ai > ai+1 ровно в случаях. Суммируя по i и прибавляя N, потому что в каждой перестановке один отрезок кончается элементом an, получим общее число отрезков во всех N перестановках:

Поделив на N, получим искомое среднее число отрезков.

Так как отрезки важны при изучении ”порядковых статистик”, имеется весьма обширная литература, посвященная им, в том числе и некоторым другим типам отрезков, не рассмотренным здесь.

Дополнительную информацию можно найти в книге Ф. Н. Дэвид и Д. Э. Бартона Combinatorial Chance (London: Griffin, 1962), гл. 10, и в обзорной статье Д. Э. Бартона и К. Л. Мэллоуза [Annals of Math.

Statistics, 36 (1965), 236–260]. Дальнейшие связи между числами Эйлера и перестановками рассматриваются в работе Д. Фоаты и М. П. Шюценберже Thorie Gomtrique des Polyn^ mes Eulriens (Lecture Notes in Math., 138 (Berlin: Springer, 1970), 94 стр.).

1. [М26] Выведите формулу Эйлера (13).

>2. [М22] (а) Попытайтесь дальше развить идею, использованную в тексте при доказательстве тождества (8): рассмотрите последовательности a1 a2... an, содержащие ровно q различных элементов, и докажите, что (b) Используя это тождество, докажите, что 4. [М21] Чему равна сумма 5. [М20] Найдите значение k mod p, если p—простое число.

>6. [М21] Мистер Тупица заметил, что из формул (4) и (13) можно получить Произведя суммирование сначала по k, затем по j, он обнаружил, что k0 (1)kj n+1 = 0 при kj всех j 0, отсюда n! = 0 при любом n 0. Не допустил ли он какой-нибудь ошибки?

7. [ВМ40] Является ли распределение вероятностей для отрезков, задаваемое формулой (14), асимптотически нормальным? (Ср. с упр. 1.2.10-13.) 8. [М24] (П. А. Мак-Магон ) Покажите, что вероятность того, что длина первого отрезка достаточно длинной перестановки есть l1, длина второго есть l2,..., а длина k-го отрезка lk, равна 9. [M30] Пусть hk (z) = (бесконечной) случайной последовательности равна m. Найдите ”простые” выражения для h1 (z), h2 (z) и для производящих функций h(z, x) = k hk (z)xk от двух переменных.

36 Original pages: 061- 10. [BM30] Определите асимптотическое поведение среднего значения и дисперсии распределения hk (z) из предыдущего упражнения при больших k.

ной (бесконечной) последовательности равна m. Выразите H1 (z), H2 (z) и производящую функцию H(z, x) = k Hk (z)xk от двух переменных через известные функции.

12. [M33] (П.А. Мак-Магон.) Обобщите формулу (13) на случай перестановок мультимножества, доказав, что число перестановок мультимножества { n1 · 1, n2 · 2,..., nm · m }, имеющих ровно 13. [05] Каким будет среднее число стопок в пасьянсе Ньюкомба, если пользоваться обычной колодой для бриджа (из 52 карт), игнорируя старшинство карт, но считая, что 14. [M17] Перестановка 3 1 1 1 2 3 1 4 2 3 3 4 2 2 4 4 содержит 5 отрезков; найдите с помощью приведенного в тексте построения для условия симметрии Мак-Магона соответствующую перестановку с >15. [М21] (Перемежающиеся отрезки.) В классической литературе 19-го века по комбинаторному анализу не изучался вопрос об отрезках в перестановках, которые рассматриваем мы, но было несколько статей, посвященных попеременно возрастающим и убывающим ”отрезкам”. Так, считалось, что перестановка 5 3 2 4 7 6 1 8 содержит 4 отрезка (Первый отрезок будет возрастающим или убывающим в зависимости от того, a1 < a2 или a1 > a2 ;

содержат одинаковое число перемежающихся отрезков.) Максимальное число отрезков этого типа в перестановке n элементов равно n 1.

Найдите среднее число перемежающихся отрезков в случайной перестановке множества { 1, 2,..., n }.

[Указание: разберите вывод формулы (34).] 16. [M30] Продолжим предыдущее упражнение. Пусть n —число перестановок множества { 1, 2,..., n }, которые имеют ровно k перемежающихся отрезков. Найдите рекуррентное соотношение, с помощью которого можно вычислить таблицу значений n ; найдите также соответствующее рекуррентное соотношение для производящей функции Gn (z) = k n z k n!. Используя это последнее рекуррентное соотношение, найдите простую формулу для дисперсии числа перемежающихся отрезков в случайной перестановке множества { 1, 2,..., n }.

17. [M25] Существует всего 2n последовательностей a1 a2 an, где каждый элемент aj —либо 0, либо 1.

Сколько среди них последовательностей, содержащих ровно k отрезков (т. е. содержащих ровно k 1 элементов aj, таких, что aj > aj+1 )?

18. [M27] Существует всего n! последовательностей a1 a2... an, где каждый элемент aj —целое число, лежащее в диапазоне 0 aj n j; сколько среди них последовательностей, содержащих ровно k отрезков (т. е. содержащих ровно k 1 элементов aj, таких, что aj > aj+1 )?

>19. [M26] (Дж. Риордан.) (а) Сколькими способами можно расположить n неатакующих ладей (т.е.

никакие две не должны находиться на одной вертикали Picture: Рис. 4. Неатакующие ладьи на шахматной доске при заданном числе ладей или горизонтали) на шахматной доске размера n n так, чтобы ровно k из них находились на заданной стороне от главной диагонали? (b) Сколькими способами можно расположить k неатакующих ладей на заданной стороне от главной диагонали шахматной доски размера n n?

Например, на рис. 4 показан один из 15619 способов расположить восемь неатакующих ладей на обычной шахматной доске с тремя ладьями на незаштрихованном участке ниже главной диагонали, а также один из 1050 способов расположить три неатакующие ладьи на треугольной доске.

>20. [М21] Говорят, что перестановка требует k чтений, если ее нужно просмотреть k раз, слева направо, чтобы прочитать все элементы в неубывающем порядке. Например, перестановка требует четырех чтений: при первом чтении получаем 1, 2, 3; при втором—4, 5, 6, 7; затем 8; затем 9.

Найдите связь между отрезками и чтениями.

21. [M22] Если перестановка a1 a2... an множества { 1, 2,..., n } содержит k отрезков и требует j чтений в смысле упр. 20, то что можно сказать о перестановке an... a2 a1 ?

22. [M26] (Л. Карлиц, Д. П. Розель и Р. А. Скоувилл.) Покажите, что не существует перестановки множества { 1, 2,..., n } с n + 1 r отрезками, требующей s чтений, если rs < n, однако такая перестановка существует, если n n + 1 r s 1, rs n.

23. [BM42] (Вальтер Вейссблюм.) ”Удлиненные отрезки” перестановки a1 a2... an получаются, если вставлять вертикальные черточки в тех местах, где нарушается установившаяся монотонность;

удлиненные отрезки бывают как возрастающими, так и убывающими в зависимости от того, в каком порядке расположены первые два элемента, так что длина каждого удлиненного отрезка (кроме, возможно, последнего) 2. Например, перестановка 7 5|6 2|3 8 9|1 4 содержит четыре удлиненных отрезка. Найдите средние длины первых двух удлиненных отрезков бесконечной перестановки и докажите, что в пределе длина удлиненного отрезка равна 24. [M30] Выразите в виде функции от p среднее число отрезков в последовательностях, полученных методом, который описан в упр. 5.1.1-18.

В заключение нашего обзора комбинаторных свойств перестановок обсудим некоторые замечательные отношения, связывающие перестановки с массивами целых чисел, называемыми табло.

Табло Янга формы (n1, n2,..., nm ), где n1 n2... nm 0, это расположение n1 + n2 + · · · + nm различных целых чисел в массив строк, выровненных по левому краю, где в i-й строке содержится ni элементов; при этом в каждой строке элементы возрастают слева направо, а элементы каждого столбца возрастают сверху вниз. Например, —табло Янга формы (6, 4, 4, 1). Такие расположения ввел Альфред Янг в 1900 г. в качестве вспомогательного средства при изучении матричного представления перестановок. [См., например, D. Е. Rutherford, Substitutional Analysis (New York: Hafiier, 1968)]. Для краткости мы будем вместо ”табло Янга” говорить просто ”табло”.

Инволюция—это перестановка, обратная самой себе. Например, существует 10 инволюций множества { 1, 2, 3, 4 }:

Термин ”инволюция” первоначально использовался в классических задачах геометрии; инволюции в общем смысле, рассматриваемые здесь, были впервые изучены X. А. Роте, когда он ввел понятие обратной перестановки (см. п. 5.1.1).

Может показаться странным, что мы рассматриваем табло и инволюции вместе, но существует удивительная связь между этими понятиями, не имеющими, казалось бы, друг к другу никакого отношения: число инволюций множества { 1, 2,..., n } равно числу табло, которые можно сформировать из элементов { 1, 2,..., n }. Например, из { 1, 2, 3, 4 } можно сформировать ровно 10 табло 38 Original pages: 061- что соответствует 10 инволюциям (2).

Эта связь между инволюциями и табло отнюдь не очевидна, и, по-видимому, не существует простого способа ее доказать. Доказательство, которое мы обсудим, включает интересный алгоритм построения табло, обладающий и некоторыми другими неожиданными свойствами; он основан на особой процедуре вставки в табло новых элементов.

Предположим, например, что нужно вставить элемент 8 в табло Метод, которым мы будем пользоваться, состоит в том, чтобы сначала поместить 8 в 1-ю строку, в клетку, ранее занимаемую 9, поскольку 9—наименьший из элементов этой строки, больших 8.

Элемент 9 ”вытесняется” вниз, в строку 2, где он замещает 10. Затем 10 ”вытесняет” 13 из 3-й строки в 4-ю и, поскольку в 4-й строке нет элемента больше 13, процесс завершается добавлением 13 в правый конец строки 4. Наше табло преобразовалось в Точное описание этого процесса с доказательством того, что он всегда сохраняет свойства табло, содержится в алгоритме I.

Алгоритм I. (Вставка в табло.) Пусть P = (Pij )—табло целых положительных чисел, а x—целое положительное число, не содержащееся в P. Этот алгоритм преобразует P в другое табло, содержащее x наряду с исходными элементами P. Новое табло имеет ту же форму, что и старое, с той лишь разницей, что на пересечении строки s и столбца t появился новый элемент, где s и t—величины, определяемые алгоритмом.

(В этом алгоритме замечания в круглых скобках предназначены для доказательства его правильности, поскольку по индукции легко проверить, что эти замечания справедливы и что массив P продолжает оставаться табло на протяжении всего процесса. Для удобства будем предполагать, что табло ограничено нулями сверху и слева и символами справа и снизу, так что элемент Pij определен при всех i, j 0. Если ввести отношение D5 [Определить x.] Установить x x1 и закончить работу алгоритма. (Теперь 0 < x <.) Пояснения к алгоритмам I и D, заключенные в круглые скобки, не только полезны для доказательства того факта, что эти алгоритмы сохраняют структуру табло, но они позволяют убедиться, что алгоритмы I и D взаимно обратны. Если сначала выполнить алгоритм I с данным табло P и некоторым целым положительным числом x P, то он вставит x в P и определит целые положительные числа s, t, удовлетворяющие условиям (8). Алгоритм D, примененный к полученному результату, восстановит значения x и первоначальный вид P. Обратно, если сначала выполнить алгоритм D с данным табло P и некоторыми целыми положительными числами s, t, удовлетворяющими условиям (8), то он модифицирует P, удалив некоторое целое положительное число x. Алгоритм I, примененный к полученному результату, восстановит значения s, t и первоначальный вид P. Причина заключается в том, что содержание пояснений к шагам I3 и D4 совпадает так же, как и к шагам I4 и D3; они однозначно определяют значение j. Следовательно, вспомогательные последовательности (9), (10) одинаковы, в обоих случаях.

Теперь мы подготовлены к доказательству основного свойства табло.

Теорема A. Существует взаимно однозначное соответствие между множеством всех перестановок множества { 1, 2,..., n } и множеством всех упорядоченных пар табло (P, Q), где P и Q—табло одинаковой формы из элементов { 1, 2,..., n }.

(Пример к этой теореме содержится в приведенном ниже доказательстве.) Доказательство. Удобнее доказать несколько более общий результат. По произвольному двустрочному массиву построим соответствующие два табло P и Q, где P состоит из элементов { p1, p2,..., pn }, а Q—из элементов { q1, q2,..., qn }, причем P и Q имеют одинаковую форму.

40 Original pages: 061- Пусть P и Q вначале пусты. При i = 1, 2,..., n (именно в таком порядке) проделаем следующую операцию: вставим Pi в табло P при помощи алгоритма I; затем установим Qst ql, где s и t определяют вновь заполненную позицию в P.

Из построения ясно, что P и Q всегда имеют одинаковую форму. Кроме того, поскольку элементы всегда добавляются на границу Q и в возрастающем порядке, то Q—табло.

Обратно, если заданы два табло одинаковой формы, то соответствующий двустрочный массив (11) можно построить так. Пусть —элементы Q. Пусть при i = n,..., 2, 1 (именно в таком порядке) pi —элемент x, который удаляется из P по алгоритму D с использованием значений s, t, таких, что Qst = qi.

Например, если применить это построение к табло (13) и производить вычисления, обратные (12), Поскольку алгоритмы I и D взаимно обратны, то взаимно обратны и описанные здесь два построения; таким образом, требуемое взаимно однозначное соответствие установлено.

Соответствие, определенное в доказательстве теоремы A, обладает множеством поразительных свойств, и теперь мы приступим к выводу некоторых из них. Убедительная просьба к читателю, прежде чем двигаться дальше, испытать себя на примерах из упр. 1, чтобы освоиться с этими построениями.

Как только элемент вытеснен из строки 1 в строку 2, он уже больше не влияет на строку 1;

кроме того, строки 2, 3,... строятся из последовательности ”вытесненных” элементов точно так же, как строки 1, 2,... строятся из исходной перестановки. Эти факты наводят на мысль о том, что на построение в теореме A можно взглянуть иначе, обращая внимание лишь на первые строки P и Q.

Например, перестановка вызывает следующие действия над строкой 1 [ср. с (12)]:

Таким образом, первая строка P —это 2 3, а первая строка Q—это 1 5. Кроме того, остальные строки P и Q составляют табло, соответствующие ”вытесненному” двустрочному массиву Чтобы понять, как строится строка 1, можно изучить элементы, попадающие в данный столбец этой строки. Будем говорить, что пара (qi, pi ) принадлежит классу t относительно двустрочного массива если pi = P1t после применения алгоритма I последовательно к p1, p2,..., pi, начиная с пустого табло P.

(Напомним, что алгоритм I всегда вставляет данный элемент в 1-ю строку.) Легко видеть, что (qi, pi ) принадлежит классу 1 тогда и только тогда, когдаpi имеет (i1) инверсий, т. е. pi = min{ p1, p2,..., pi }—”левосторонний минимум”. Если в массиве (16) вычеркнуть столбцы класса 1, то получится другой двустрочный массив:

такой, что пара (q, p) принадлежит классу t относительно (17) тогда и только тогда, когда она принадлежит классу t + 1 относительно массива (16). Операция перехода от (16) к (17) соответствует удалению крайней левой позиции строки 1. Это дает систематический способ определения классов.

Например, в перестановке левосторонними минимумами являются элементы 7 и 2, так что класс 1—это { (1, 7), (3, 2) }; в оставшемся массиве все элементы минимальны, так что класс 2—это { (5, 9), (6, 5), (8, 3) }. В ”вытесненном” массиве (15) класс 1—это { (3, 7), (8, 5) }, а класс 2—{ (6, 9) }.

Для любого фиксированного t элементы класса t можно пометить так чтобы выполнялись неравенства поскольку при работе алгоритма вставки позиция табло P1t принимает убывающую последовательность значений pi1,..., pik. В конце построения а вытесненный двустрочный массив, которым определяются строки 2, 3,... табло P и Q, содержит столбцы а также другие столбцы, аналогичным образом полученные из других классов.

Эти наблюдения приводят к простому методу вычисления P и Q вручную (см. упр. 3), а также предоставляют средства для доказательства одного весьма неожиданного результата.

Теорема B. Если в построении из теоремы A перестановка соответствует табло (P, Q), то обратная ей перестановка соответствует табло (Q, P ).

Это довольно удивительный факт, потому что в теореме A табло P и Q формируются совершенно разными способами, и обратная перестановка получается в результате весьма причудливой перетасовки столбцов двустрочного массива.

Доказательство. Предположим, у нас есть двустрочный массив (16); поменяв местами его строки и отсортировав столбцы так, чтобы элементы новой верхней строки расположились в неубывающем порядке, получим ”обратный” массив 42 Original pages: 061- Покажем, что эта операция соответствует замене (P, Q) на (Q, P ) в построении из теоремы A.

В упр. 2 наши замечания об определении классов переформулированы таким образом, что класс, к которому относится пара (qi, pi ), не зависит от того факта, что элементы q1, q2,..., qn расположены в возрастающем порядке. Поскольку результирующие условия симметричны относительно p и q, то операция (21) не нарушает структуру классов; если (q, p) принадлежит классу t относительно (16), то (p, q) принадлежит классу t относительно (21). Поэтому, если разместить элементы этого последнего класса t так, чтобы [ср. с (18)], то получим как в (19), а столбцы войдут в вытесненный массив, как в (20). Следовательно, первые строки P и Q меняются местами.

Кроме того, вытесненный двустрочный массив для (21) является обратным по отношению к вытесненному двустрочному массиву для (16), так что доказательство завершается применением индукции по числу строк в табло.

Следствие. Количество табло, которые можно сформировать из элементов { 1, 2,..., n }, равно количеству инволюций множества { 1, 2,..., n }.

Доказательство. Если —инволюция, соответствующая паре табло (P, Q), то = 1 соответствует паре (Q, P ). Следовательно, P = Q. Обратно, если —какая-либо перестановка, соответствующая паре (P, P ), то 1 тоже соответствует паре (P, P ); отсюда = 1. Таким образом, существует взаимно однозначное соответствие между инволюциями и табло P.

Ясно, что элемент в левом верхнем углу табло всегда наименьший. Это наводит на мысль о возможном способе сортировки множества чисел. Сначала можно составить из них табло, многократно применяя алгоритм I, в результате наименьший элемент окажется в углу. Затем этот наименьший элемент удаляется, а остальные элементы переразмещаются так, чтобы образовалось другое табло;

потом удаляется новый минимальный элемент и т.д.

Поэтому давайте посмотрим, что происходит, когда мы удаляем угловой элемент из табло После удаления 1 на освободившееся место необходимо поставить 2. Затем можно поднять 4 на место двойки, однако 11 нельзя поднять на место 4, но на это место можно подвинуть 10, а потом 13 на место 10. В общем случае приходим к следующей процедуре.

Алгоритм S. (Удаление углового элемента.) Этот алгоритм удаляет элемент из левого верхнего угла табло P и перемещает остальные элементы так, чтобы сохранились свойства табло. Используются те же обозначения, что и в алгоритмах I и D.

S1 [Начальная установка.] Установить r 1, s 1.

S2 [Конец?] Если Prs =, то процесс завершен.

S3 [Сравнить.] Если P(r+1)s < Pr(s+1), то перейти к шагу S5. (Сравниваем элементы справа и снизу от свободного места и передвигаем меньший из них.) S4 [Подвинуть влево.] Установить Prs Pr(s+1), s s + 1 и вернуться к S3.

S5 [Подвинуть вверх.] Установить Prs P(r+1)s, r r + 1 и вернуться к S2.

Легко доказать, что после удаления углового элемента с помощью алгоритма S, P —по-прежнему табло (см. упр. 10). Таким образом, применяя алгоритм S до тех пор, пока P не исчерпается, можно прочитать его элементы в возрастающем порядке. К сожалению, этот алгоритм сортировки оказывается не столь эффективным, как другие алгоритмы, которые нам еще предстоит рассмотреть. Минимальное время его работы пропорционально n1.5 ; аналогичные алгоритмы, использующие вместо табло деревья, затрачивают время порядка n log n.

Алгоритм S, хотя и не приводит к особенно эффективному алгоритму сортировки, обладает некоторыми очень интересными свойствами.

Теорема C. (М. П. Шюценберже.) Если P —табло, построенное, как в теореме A, из перестановки a1 a2,... an, и ai = min{ a1, a2,..., an }, то алгоритм S преобразует P в табло, соответствующее перестановке a1... ai1 ai+1... an.

Доказательство. См. упр. 13.

Давайте после применения алгоритма S поместим на вновь освободившееся место удаленный элемент в скобках, указав таким образом, что на самом деле он не является частью табло. Применив, например, эту процедуру к табло (25), мы получили бы а еще два применения приводят к Продолжая до тех пор, пока все элементы не окажутся в скобках, и убрав скобки, получим конфигурацию имеющую ту же форму, что и исходное табло (25). Эту конфигурацию можно назвать двойственным табло, потому что она похожа на табло с той лишь разницей, что применяется ”двойственное отношение порядка” (< и > поменялись ролями). Обозначим двойственное табло, полученное из P таким способом, через P S.

Табло P определяется из P S единственным образом. В самом деле, исходное табло можно получить из P S при помощи того же самого алгоритма (с обратным отношением порядка, поскольку P S — двойственное табло). Например, применение к (26) двух шагов этого алгоритма дает и в конце концов опять получается табло (25). Этот замечательный результат—одно из следствий нашей следующей теоремы.

Теорема D. (К. Шенстед, М. П. Шюценберже.) Пусть —двустрочный массив, соответствующий паре табло (P, Q).

a) Если пользоваться двойственным (обратным) отношением порядка для q, но не для p, то двустрочный массив соответствует паре (P T, (QS )T ).

44 Original pages: 061- (Как обычно, через T обозначена операция транспонирования; P T —табло, a (QS )T — двойственное табло, поскольку элементы q расположены в обратном порядке.) b) Если пользоваться двойственным отношением порядка для p, но не для q, то двустрочный c) Если пользоваться двойственным отношением порядка как для p, так и для q, то двустрочный массив (28) соответствует паре (P S, QS ).

Доказательство. Не известно простого доказательства этой теоремы. То, что случай (a) соответствует паре (P T, X), где X—некоторое двойственное табло, доказано в упр. 6; следовательно, по теореме B, случай (b) соответствует паре (Y, QT ), где Y —некоторое двойственное табло той же формы, Пусть pi = min{ p1,..., pn }; так как pi —”наибольший” элемент при двойственном отношении порядка, то он окажется на границе Y и не вытесняет никаких элементов при построении из теоремы A. Таким образом, если последовательно вставлять элементы p1,..., pi1, pi+1,..., pn, применяя двойственное отношение порядка, то получится Y { pi }, т.е. Y, из которого удален элемент pi. По теореме C, если последовательно вставлять элементы p1,..., pi1, pi+1,..., pn, применяя обычное отношение порядка, построим табло d(P ), которое получается путем применения к P алгоритма S.

Индукция по n дает Y { pi } = (d(P )S )T. Но поскольку по определению операции S, а Y имеет ту же форму, что и (P S )T, то должно иметь место равенство Y = Тем самым доказано утверждение (b); (a) получается применением теоремы B. Последовательное применение (a) и (b) показывает, что случай (c) соответствует паре (((P T )S )T, ((QS )T )T ), a это равно (P S, QS ), так как (P S )T = (P T )S вследствие симметрии операции S по отношению к строкам и столбцам.

Эта теорема, в частности, устанавливает два удивительных факта, касающихся алгоритма вставки в табло. Если в результате последовательной вставки различных элементов p1,..., pn в пустое табло получается табло P, то в результате вставки этих элементов в обратном порядке—pn,..., p1, получится транспонированное табло P T. Если же мы не только станем вставлять элементы в порядке pn,..., p1, но и поменяем ролями < и >, а также 0 и, то получим двойственное табло P S. Настоятельно рекомендуем читателю испытать эти процессы на нескольких простых примерах. Необычная природа этих совпадений может вызвать подозрение о вмешательстве каких-то колдовских сил. До сих пор не известно какого-либо простого объяснения подобных явлений; кажется, не существует простого способа доказать даже то, что случай (c) соответствует табло той же формы, что P и Q.

Соответствие, устанавливаемое теоремой A, найдено Ж. Робинсоном [American J. Math., (1938), 745–760, Sec. 5] в несколько иной и довольно туманной форме как часть решения весьма сложной задачи из теории групп. Нетрудно проверить, что его построение в сущности идентично приведенному здесь. Он сформулировал теорему B без доказательства. Много лет спустя К. Шенстед независимо заново открыл это соответствие, которое он сформулировал по существу в той же форме, какую использовали мы [Canadian J. Math., 13 (1961), 179–191]. Он также доказал ”P ”-часть теоремы D (a). М. П. Шюценберже [Math. Scand., 12 (1963), 117–128] доказал теорему B и ”Q”-часть теоремы D (a), из которой следуют (b) и (c). Это соответствие можно распространить и на перестановки мультимножеств; случай, когда p1,..., pn не обязательно различны, рассмотрел Шенстед, а ”максимальное” обобщение на случай, когда и p, и q могут содержать повторяющиеся элементы, исследовано Кнутом [Pacific J. Math., 34 (1970), 709–727].

Обратимся теперь к родственному вопросу: сколько табло, составленных из элементов { 1, 2,..., n }, имеют данную форму (n1, n2,..., nm ), где n1 +n2 +· · ·+nm = n? Обозначим это число через f (n1, n2,..., nm );