Василиса▶ Я жду вашего обращения. Что Вы хотите узнать?
Логотип
Дж.Эндрюс. Теория разбиений
 
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
 


 
ОГЛАВЛЕНИЕ
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.2 101
6.3.  Приложения теоремы 6.2 107
Задачи 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.  Идеалы разбиений порядка 1 134
8.4.  Сцепленные идеалы разбиений 138
Задачи 147
Замечания 148
Литература 148
 
Глава 9 . Методы решета, связанные с разбиениями
149
9.1.  Введение 149
9.2.  Включение-исключение 149
9.3.  Решето для последовательных рангов 153
Задачи 166
Замечания 167
Литература 167
 
Глава 1 0. Свойства делимости функций разбиений
168
10.1.  Введение 168
10.2.  Теорема Рёдсета о двоичных разбиениях 170
10.3.  Гипотеза Рамануджана для 5 n 175
Задачи 183
Замечания 184
Литература 184
 
Глава 1 1. Многомерные разбиения
186
11.1.  Введение 186
11.2.  Плоские разбиения 186
11.3.  Соответствие Кнута–Шенстеда 191
11.4.  Многомерные разбиения 196
Задачи 205
Замечания 206
Литература 206
 
Глава 1 2. Векторные или многокомпонентные разбиения
208
12.1.  Введение 208
12.2.  Многокомпонентные производящие функции 209
12.3.  Многочлены Белла и формулы для функций многокомпонентных разбиений 210
12.4.  Ограниченные двукомпонентные разбиения 213
Задачи 215
Замечания 216
Литература 216
 
Глава 1 3. Разбиения в комбинаторике
218
13.1.  Введение 218
13.2.  Разбиения и конечные векторные пространства 218
13.3.  Разбиения множеств 220
13.4.  Комбинаторика симметрических функций 226
Задачи 230
Замечания 233
Литература 233
 
Глава 1 4. Вычисление функций разбиений
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].

L. Euler. Introductio in Analysis Infinitorum. J. Cristal. Texbook of Algebra. S. Bachman. Niedere Zahlentheorie. G. Hardy, E. Wright. Introduction to the Theory of Numbers. P. MacMahon. Combinatory Analysis. J. Riordan. Introduction to Combinatorial Analysis. J. Perens. Combinatorial Methods. L. Comtet. Advanced Combinatorics. R. Ayoub. Introduction to the Analytic Theory of Numbers. M. Knopp. Modular Functions in Analytic Number Theory. E. Grosswald. Topics from the Theory of Numbers. H. Ostmann. Additive Zahlentheory. 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
© 2014-2020 ЯВИКС - все права защищены.
Наши контакты/Карта ссылок