Analytic Combinatorics es un libro sobre las matemáticas de la enumeración combinatoria , que utiliza funciones generadoras y análisis complejos para comprender las tasas de crecimiento de la cantidad de objetos combinatorios. Fue escrito por Philippe Flajolet y Robert Sedgewick , y publicado por Cambridge University Press en 2009. Ganó el premio Leroy P. Steele en 2019.
La parte principal del libro está organizada en tres partes. La primera parte, que abarca tres capítulos y aproximadamente el primer cuarto del libro, trata del método simbólico en combinatoria , en el que las clases de objetos combinatorios se asocian con fórmulas que describen sus estructuras, y luego esas fórmulas se reinterpretan para producir las funciones generadoras o funciones generadoras exponenciales de las clases, [1] [2] en algunos casos utilizando herramientas como el teorema de inversión de Lagrange como parte del proceso de reinterpretación. [2] Los capítulos de esta parte dividen el material en la enumeración de objetos no etiquetados, la enumeración de objetos etiquetados y las funciones generadoras multivariadas. [2] [3]
Los cinco capítulos de la segunda parte del libro, aproximadamente la mitad del texto [3] y "el corazón del libro", [1] tratan de la aplicación de herramientas del análisis complejo a la función generadora, con el fin de entender la asintótica de los números de objetos en una clase combinatoria. [3] En particular, para funciones generadoras suficientemente bien comportadas, la fórmula integral de Cauchy se puede utilizar para recuperar los coeficientes de la serie de potencias (el verdadero objeto de estudio) de la función generadora, y el conocimiento de las singularidades de la función se puede utilizar para derivar estimaciones precisas de las integrales resultantes. [1] Después de un capítulo introductorio y un capítulo que da ejemplos de los posibles comportamientos de las funciones racionales y funciones meromórficas , los capítulos restantes de esta parte discuten la forma en que las singularidades de una función se pueden utilizar para analizar el comportamiento asintótico de su serie de potencias, aplicar este método a un gran número de ejemplos combinatorios y estudiar el método de punto de silla de integración de contorno para manejar algunos ejemplos más complicados. [1] [3]
La parte final investiga el comportamiento de las estructuras combinatorias aleatorias, en lugar del número total de estructuras, utilizando la misma caja de herramientas. Además de los valores esperados para las cantidades combinatorias de interés, también estudia los teoremas límite y la teoría de las grandes desviaciones para estas cantidades. Tres apéndices proporcionan información de fondo sobre combinatoria y asintótica, en análisis complejo y en teoría de la probabilidad. [3]
Las estructuras combinatorias que se investigan a lo largo del libro abarcan una amplia gama de secuencias , lenguajes formales , particiones y composiciones de números enteros , permutaciones , grafos y caminos en grafos y caminos reticulares . Con estos temas, el análisis del libro se conecta con aplicaciones en otras áreas, como el álgebra abstracta , la teoría de números y el análisis de algoritmos . [2] [4]
Analytic Combinatorics no es principalmente un libro de texto; por ejemplo, no tiene ejercicios. [4] Sin embargo, puede usarse como libro de texto para una optativa de pregrado de nivel superior, [5] un curso de posgrado, [4] o un seminario, [3] aunque el revisor Miklós Bóna escribe que se necesita cierta selección, ya que "tiene suficiente material para tres o más semestres". [2] También puede ser una referencia para investigadores en este tema. [3]
El crítico Toufik Mansour lo califica no sólo de "tratamiento teórico exhaustivo", sino también de "lectura interesante". [3] El crítico Christopher Hanusa escribe que "el estilo de redacción es atractivo, el material temático es contemporáneo y fascinante", y recomienda el libro a cualquiera que "esté aprendiendo o trabajando en combinatoria". [4]
Analytic Combinatorics ganó el Premio Leroy P. Steele de Exposición Matemática de la American Mathematical Society en 2019 (póstumamente para Flajolet). La cita del premio calificó el libro como "un compendio autorizado y muy accesible de su tema, que demuestra la profunda interfaz entre las matemáticas combinatorias y el análisis clásico". [5] Aunque la aplicación de métodos analíticos en combinatoria se remonta al menos al trabajo de GH Hardy y Srinivasa Ramanujan sobre la función de partición , [1] la cita también citó una revisión de Robin Pemantle que afirma que "Este es uno de esos libros que marca el surgimiento de un subcampo", el subcampo de la combinatoria analítica . [1] [5] De manera similar, Bóna concluye: "La combinatoria analítica ahora está definida. Los autores escribieron el libro sobre ella". [2]