Аналитическая комбинаторика (книга)
Аналитическая комбинаторика — это книга по математике комбинаторного перечисления , в которой используются производящие функции и комплексный анализ для понимания скорости роста числа комбинаторных объектов. Он был написан Филиппом Флажоле и Робертом Седжвиком и опубликован издательством Кембриджского университета в 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]
Ссылки [ править ]
- ^ Перейти обратно: а б с д и ж Пемантл, Робин (сентябрь 2010 г.), «Обзор аналитической комбинаторики », SIAM Review , 52 (3): 572–576, JSTOR 20780175
- ^ Перейти обратно: а б с д и ж Бона, Миклош (июнь 2010 г.), «Обзор аналитической комбинаторики » (PDF) , ACM SIGACT News , 41 (2): 11, doi : 10.1145/1814370.1814373 , S2CID 16443540
- ^ Перейти обратно: а б с д и ж г час Мансур, Туфик, «Обзор аналитической комбинаторики », zbMATH , Zbl 1165.05001
- ^ Перейти обратно: а б с д Хануса, Кристофер (июль 2009 г.), «Обзор аналитической комбинаторики » , MAA Reviews , Математическая ассоциация Америки
- ^ Перейти обратно: а б с «Премии Лероя П. Стила 2019» (PDF) , Уведомления Американского математического общества , 66 (4): 594–598, апрель 2019 г.
Внешние ссылки [ править ]
- Веб-сайт автора аналитической комбинаторики , включая полнотекстовую загружаемую копию книги