Аналитическая комбинаторика - Analytic Combinatorics

Аналитическая комбинаторика это книга по математике комбинаторное перечисление, с помощью производящие функции и комплексный анализ понять темпы роста числа комбинаторных объектов. Это было написано Филипп Флажоле и Роберт Седжвик, и опубликовано Издательство Кембриджского университета в 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]

Рекомендации

  1. ^ а б c d е ж Пемантл, Робин (сентябрь 2010 г.), "Обзор Аналитическая комбинаторика", SIAM Обзор, 52 (3): 572–576, JSTOR  20780175
  2. ^ а б c d е ж Бона, Миклош (июнь 2010 г.), "Обзор Аналитическая комбинаторика" (PDF), Новости ACM SIGACT, 41 (2): 11, Дои:10.1145/1814370.1814373
  3. ^ а б c d е ж грамм час Мансур, Туфик, "Обзор Аналитическая комбинаторика", zbMATH, Zbl  1165.05001
  4. ^ а б c d Хануса, Кристофер (июль 2009 г.), "Обзор Аналитическая комбинаторика", Обзоры MAA, Математическая ассоциация Америки
  5. ^ а б c «Призы Лероя П. Стила 2019» (PDF), Уведомления Американского математического общества, 66 (4): 594–598, апрель 2019 г.

внешняя ссылка