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.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   Глава 10. Свойства делимости функций разбиений 168 10.1.  Введение 168 10.2.  Теорема Рёдсета о двоичных разбиениях 170 10.3.  Гипотеза Рамануджана для 5n 175 Задачи 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 становятся корректными, если кольцо многочленов от счётного числа переменных рассматривать как топологическое кольцо.

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

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

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

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

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

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

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

Сразу оговорим, что термин «разбиение» имеет в математике целый ряд значений. Вообще, под разбиением принято понимать всякое расчленение целого на части. Для нас разбиение — это, прежде всего, «разбиение числа 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 учебного года. Считаю себя обязанным отдать великий долг благодарности многим сотрудникам этих четырёх университетов. Особенно хотел бы поблагодарить тех, кто своими ценными советами и замечаниями помогал мне в самом процессе подготовки этой книги, именно, Аски, Баклавский, Берндт, Карлитц.

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