«Аналитическая комбинаторика» — книга по математике комбинаторного перечисления , использующая производящие функции и комплексный анализ для понимания темпов роста числа комбинаторных объектов. Она была написана Филиппом Флажоле и Робертом Седжвиком и опубликована издательством Cambridge University Press в 2009 году. Она получила премию Лероя П. Стила в 2019 году.
Основная часть книги разделена на три части. Первая часть, охватывающая три главы и примерно первую четверть книги, касается символического метода в комбинаторике , в котором классы комбинаторных объектов связываются с формулами, описывающими их структуры, а затем эти формулы переинтерпретируются для получения производящих функций или экспоненциальных производящих функций классов, [1] [2] в некоторых случаях с использованием таких инструментов, как теорема Лагранжа об обращении, как части процесса переинтерпретации. [2] Главы в этой части делят материал на перечисление немаркированных объектов, перечисление маркированных объектов и многомерные производящие функции. [2] [3]
Пять глав второй части книги, составляющие примерно половину текста [3] и «сердце книги», [1] посвящены применению инструментов комплексного анализа к производящей функции для понимания асимптотики чисел объектов в комбинаторном классе. [3] В частности, для достаточно хорошо ведущих себя производящих функций интегральная формула Коши может быть использована для восстановления коэффициентов степенного ряда (реального объекта изучения) из производящей функции, а знание особенностей функции может быть использовано для получения точных оценок полученных интегралов. [1] После вводной главы и главы, дающей примеры возможного поведения рациональных функций и мероморфных функций , в оставшихся главах этой части обсуждается способ использования особенностей функции для анализа асимптотического поведения ее степенного ряда, применяется этот метод к большому количеству комбинаторных примеров и изучается метод седловой точки контурного интегрирования для обработки некоторых более сложных примеров. [1] [3]
В заключительной части исследуется поведение случайных комбинаторных структур, а не общее число структур, с использованием того же набора инструментов. Помимо ожидаемых значений для интересующих комбинаторных величин, в ней также изучаются предельные теоремы и теория больших отклонений для этих величин. Три приложения предоставляют справочную информацию по комбинаторике и асимптотике, комплексному анализу и теории вероятностей. [3]
Комбинаторные структуры, которые исследуются в книге, широко варьируются по последовательностям , формальным языкам , целочисленным разбиениям и композициям , перестановкам , графам и путям в графах , а также решетчатым путям . С этими темами анализ в книге связывается с приложениями в других областях, включая абстрактную алгебру , теорию чисел и анализ алгоритмов . [2] [4]
Аналитическая комбинаторика — это, в первую очередь, не учебник; например, в ней нет упражнений. [4] Тем не менее, ее можно использовать в качестве учебника для факультатива на старших курсах бакалавриата, [5] курса магистратуры, [4] или семинара, [3] хотя рецензент Миклош Бона пишет, что необходим некоторый отбор, поскольку в ней «достаточно материала для трех или более семестров». [2] Она также может быть справочным пособием для исследователей в этой области. [3]
Рецензент Туфик Мансур называет ее не только «всеобъемлющим теоретическим исследованием», но и «интересным чтением». [3] Рецензент Кристофер Хануса пишет, что «стиль письма привлекательный, предметный материал современный и захватывающий», и он рекомендует книгу всем, «кто изучает или работает в области комбинаторики». [4]
Аналитическая комбинаторика выиграла премию Лероя П. Стила за математическое изложение Американского математического общества в 2019 году (посмертно за Флажоле). В наградном листе книга названа «авторитетным и высокодоступным сборником по своему предмету, который демонстрирует глубокий интерфейс между комбинаторной математикой и классическим анализом». [5] Хотя применение аналитических методов в комбинаторике восходит по крайней мере к работам Г. Х. Харди и Сринивасы Рамануджана по функции распределения , [1] в листе также цитируется обзор Робина Пемантла, в котором говорится, что «Это одна из тех книг, которая знаменует собой возникновение подполя», подполя аналитической комбинаторики . [1] [5] Аналогичным образом Бона заключает: «Аналитическая комбинаторика теперь определена. Авторы написали книгу о ней». [2]