GIAN-CARLO ROTA, Editor
ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS
Volume 2


   Section: Number Theory
   Paul Turán, Section Editor


 
The Theory of
Partitions

George E. Andrews

Pennsylvania State University
University Park, Pennsylvania



 
 
  Дж. Эндрюс


 ТЕОРИЯ
РАЗБИЕНИЙ

 


ПЕРЕВОД С АНГЛИЙСКОГО
Б. С. СТЕЧКИНА
  1976

Addison-Wesley Publishing Company

Advanced Book Program
Reading, Massachusetts


London · Amsterdam · Don Mills, Ontario · Sydney · Tokyo
 
  МОСКВА «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
1982
 





 
2754 Кб
 
 
ОГЛАВЛЕНИЕ
О теории разбиений8
От редактора энциклопедии10
Предисловие12
 
Глава 1. Элементарная теория разбиений
15
1.1. Введение15
1.2. Бесконечные произведения производящих функций одного переменного17
1.3. Графическое представление разбиений20
Задачи27
Замечания28
Литература29
 
Глава 2. Ряды производящих функций
30
2.1. Введение30
2.2. Элементарные тождества с рядами и произведениями31
2.3. Приложения к разбиениям37
Задачи42
Замечания44
Литература45
 
Глава 3. Разбиения на ограниченные части и перестановки
47
3.1. Введение47
3.2. Производящая функция для ограниченных разбиений47
3.3. Свойства многочленов Гаусса49
3.4. Перестановки и полиномиальные коэффициенты Гаусса53
3.5. Унимодальное свойство59
Задачи63
Замечания65
Литература65
 
Глава 4. Композиции и проблема Симона Ньюкомба
67
4.1. Введение67
4.2. Композиции чисел67
4.3. Векторные композиции70
4.3. Проблема Симона Ньюкомба72
Задачи75
Замечания77
Литература77
 
Глава 5. Выражения Харди–Рамануджана–Радемахера для p(n)
80
5.1. Введение80
5.2. Формула для p(n)83
Задачи93
Замечания97
Литература97
 
Глава 6. Асимптотика бесконечного произведения производящих функций
100
6.1. Введение100
6.2. Доказательство теоремы 6.2101
6.3. Приложения теоремы 6.2107
Задачи108
Замечания111
Литература111
 
Глава 7. Тождества типа Роджерса–Рамануджана
113
7.1. Введение113
7.2. Производящие функции116
7.3. Тождества Роджерса–Рамануджана и их обобщение Гордона119
7.4. Тождества Гёллница–Гордона и их обобщение124
Задачи126
Замечания128
Литература128
 
Глава 8. Общая теория тождеств с разбиениями
131
8.1. Введение131
8.2. Основания131
8.3. Идеалы разбиений порядка 1134
8.4. Сцепленные идеалы разбиений138
Задачи147
Замечания148
Литература148
 
Глава 9. Методы решета, связанные с разбиениями
149
9.1. Введение149
9.2. Включение-исключение149
9.3. Решето для последовательных рангов153
Задачи166
Замечания167
Литература167
 
Глава 10. Свойства делимости функций разбиений
168
10.1. Введение168
10.2. Теорема Рёдсета о двоичных разбиениях170
10.3. Гипотеза Рамануджана для 5n175
Задачи183
Замечания184
Литература184
 
Глава 11. Многомерные разбиения
186
11.1. Введение186
11.2. Плоские разбиения186
11.3. Соответствие Кнута–Шенстеда191
11.4. Многомерные разбиения196
Задачи205
Замечания206
Литература206
 
Глава 12. Векторные или многокомпонентные разбиения
208
12.1. Введение208
12.2. Многокомпонентные производящие функции209
12.3. Многочлены Белла и формулы для функций многокомпонентных разбиений210
12.4. Ограниченные двукомпонентные разбиения213
Задачи215
Замечания216
Литература216
 
Глава 13. Разбиения в комбинаторике
218
13.1. Введение218
13.2. Разбиения и конечные векторные пространства218
13.3. Разбиения множеств220
13.4. Комбинаторика симметрических функций226
Задачи230
Замечания233
Литература233
 
Глава 14. Вычисление функций разбиений
236
14.1. Введение236
14.2. Элементарные алгоритмы236
14.3. Алгоритмы из производящих функций238
14.4. Вычисления для многомерных разбиений240
14.5. Краткие таблицы функций разбиений243
14.6. Таблица функции плоских разбиений243
14.7. Таблица многочленов Гаусса244
14.8. Иные таблицы244
Замечания244
Литература248
 
Добавление. Экстремальные свойства разбиений (Б. С. Стечкин)
249
Указатель обозначений  254



О ТЕОРИИ РАЗБИЕНИЙ

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

Разбиения изучаются в комбинаторике и теории чисел: к классически комбинаторным относятся задачи подсчёта и перечисления разбиений данного типа, в теории чисел решают проблемы об аддитивных представлениях чисел с арифметическими ограничениями на слагаемые (таковы, например, проблемы Гольдбаха и Варинга). При решении задач о разбиениях возникают серьёзные трудности, их преодоление потребовало большой изобретательности и повлекло создание специальных методов теории разбиений [17 (3), 40 (5)]*).

Исторически первым и общим для всей теории разбиений явился метод производящих функций. Разработанный Л. Эйлером, в том числе и для нужд теории разбиений, этот аналитический метод оказался эффективным инструментом и для комбинаторики, и для теории чисел; он был развит до таких тонких форм, как метод производящих функций Дирихле, метод тригонометрических сумм, метод характеристических функций, — методов, применяемых не только в комбинаторике и теории чисел [40, 41, 43 (5)].

Развитие метода производящих функций во многом шло за счёт задач о разбиениях. Один из самых ярких моментов этого развития — создание «кругового» метода, первоначально — для подсчёта всех разбиений фиксированного числа. С качественными этапами решения этой задачи связаны имена Успенского [42 (5)], Харди, Рамануджана и Радемахера [(5)].

Другие методы теории разбиений уже не столь эффективны: алгебраические только зарождаются, а комбинаторные, хотя и несут в себе остроумные соображения, не обладают ещё достаточной степенью общности. Одно из интересных направлений развития этих методов — создание синтезированного (на идейной основе метода производящих функций) комбинаторно-алгебраического подхода к широкому классу задач [24, 37 (13)].

Наблюдается применимость элементов теории разбиений в других областях математики. Имеются и реальные явления, допускающие адекватное описание в терминах разбиений числа [34, 35, 38 (13)].

Книга представляет собой изложение комбинаторных аспектов теории разбиений. В ней хорошо представлены аналитические методы.

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

Все общие комментарии по существу сделаны в нашем предисловии. По части конкретных замечаний должно лишь указать на недостаточную аргументированность рассуждений при использовании формальных степенных рядов в гл. 13. Рассуждения § 13.4 становятся корректными, если кольцо многочленов от счётного числа переменных рассматривать как топологическое кольцо.

27 июля 1981 года  С. М. Воронин
Б. С. Стечкин

* Число в круглых скобках обозначает номер главы, по списку литературы которой цитируется источник. 



ОТ РЕДАКТОРА ЭНЦИКЛОПЕДИИ

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

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

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

*   *   *

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

Профессором Эндрюсом впервые написано столь подробное руководство по этому многоплановому направлению. Специалист будет обращаться к нему за более глубокими результатами, студента заинтересуют многие обманчиво простые факты, а прикладник сможет обнаружить в нём нужное тождество.

Безвременная кончина профессора Турана оставила книгу без предисловия редактора секции. Достойным знаком памяти этому мастеру теории чисел будет служить настоящая книга.

Джиан-Карло Рота


ПРЕДИСЛОВИЕ

Джой, Ами и Кати

Сразу оговорим, что термин «разбиение» имеет в математике целый ряд значений. Вообще, под разбиением принято понимать всякое расчленение целого на части. Для нас разбиение — это, прежде всего, «разбиение числа n», т.е. невозрастающая последовательность положительных целых, сумма которых равна n. Понятие разбиения числа будет расширено при рассмотрении многомерных разбиений, разбиений векторов и разбиений множеств (см. гл. 11, 12, 13). Композиции, или упорядоченные разбиения (т.е. просто последовательности положительных целых), рассматриваются в гл. 4.

Теория разбиений числа имеет интересную историю. Отдельные её задачи появлялись ещё в средние века, однако первые глубокие разработки относятся к восемнадцатому столетию, к тому времени, когда Эйлером были доказаны его многочисленные, красивые и важные теоремы о разбиениях. Именно Эйлер заложил основы теории разбиений числа. В дальнейшей разработке этой теории принимали активное участие такие крупные математики, как Гаусс, Кэли, Лагранж, Лежандр, Литлвуд, Радемахер, Рамануджан, Сильвестр, Харди, Шур, Якоби.

Почти не было книг, целиком посвящённых разбиениям; общие комбинаторные аспекты и формальные степенные ряды, относящиеся к разбиениям, находили свое отражение в старых книгах, посвящённых элементарному анализу [1, 2], в энциклопедических обзорах по теории чисел [3, 4] и в книгах по комбинаторному анализу [5, 6, 7, 8]. С другой стороны, асимптотические проблемы, связанные с разбиениями, исследовались в работах по аналитической или аддитивной теории чисел [6, 10, 11, 12, 13].

  1. L. Euler. Introductio in Analysis Infinitorum.
  2. J. Cristal. Texbook of Algebra.
  3. S. Bachman. Niedere Zahlentheorie.
  4. G. Hardy, E. Wright. Introduction to the Theory of Numbers.
  5. P. MacMahon. Combinatory Analysis.
  6. J. Riordan. Introduction to Combinatorial Analysis.
  7. J. Perens. Combinatorial Methods.
  8. L. Comtet. Advanced Combinatorics.
  9. R. Ayoub. Introduction to the Analytic Theory of Numbers.
  10. M. Knopp. Modular Functions in Analytic Number Theory.
  11. E. Grosswald. Topics from the Theory of Numbers.
  12. H. Ostmann. Additive Zahlentheory.
  13. H. Rademacher. Topics in Analytic Number Theory.

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

В главах 1–4 излагаются элементарные разделы теории разбиений; основное внимание здесь уделяется использованию производящих функций. В главах 5 и 6 представлены асимптотические задачи. Главы 7–9 посвящены тождествам с разбиениями. Глава 10 — о делимости функций разбиений — возвращает нас к аналитическим аспектам разбиений. В главах 11–13 рассматривается ряд обобщений понятия разбиения, а в главе 14 кратко обсуждаются некоторые вычислительные аспекты, связанные с разбиениями.

Каждая глава завершается тремя разделами: в разделе «Замечания» излагаются исторические комментарии по изложенному в данной главе материалу, раздел «Литература» представляет собой достаточно полный, но не всегда совершенно исчерпывающий список относящихся к материалу главы книг и отдельных работ и, наконец, в разделе «Задачи» приводятся формулировки результатов, не освещаемых полностью в основном тексте. Примеры, отмеченные звёздочкой, существенны для продвижения по материалу основного текста, остальные же представляют собой упражнения, посредством которых читатель может контролировать своё восприятие материала. Литература по источникам всех этих примеров приводится в тех же главах.

В последнее время стали просматриваться приложения теории разбиений ко многим математическим наукам. Непараметрическим статистикам требуются разбиения с ограничениями, подобные тем, что рассматриваются в главе 3. Ряд перестановочных задач в теории вероятностей и статистике тесно связан с проблемой Симона Ньюкомба из главы 4. Физика частиц использует асимптотики разбиений и тождества, как в главах 5–9. Теория групп (через диаграммы Юнга) тесно связана с материалом главы 12, а связи между разбиениями и общей комбинаторной теорией излагаются в главе 13.

Материал этой книги взращивался в течение многих лет. Первое знакомство с разбиениями состоялось у меня при слушании захватывающих лекций диссертационного руководителя — профессора Ганса Радемахера. Многое из представленного здесь излагалось в курсах Университета Пенсильвании между 1964 и 1975 годами, на семинарах Массачусетского технологического института в течение 1970/71 учебного года, в Университете Эрлангена летом 1975 года и в Университете Висконсина в течение 1975/76 учебного года. Считаю себя обязанным отдать великий долг благодарности многим сотрудникам этих четырёх университетов. Особенно хотел бы поблагодарить тех, кто своими ценными советами и замечаниями помогал мне в самом процессе подготовки этой книги, именно, Аски, Баклавский, Берндт, Карлитц.

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

Джордж Эндрюс


Hosted by uCoz