Combinatoria analítica 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 los números 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 cubre tres capítulos y aproximadamente el primer cuarto del libro, se refiere al método simbólico en combinatoria , en el que 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 enumeración de objetos sin etiquetar, enumeración de objetos etiquetados y 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] se refieren a la aplicación de herramientas del análisis complejo a la función generadora, con el fin de comprender las asintóticas. del número de objetos en una clase combinatoria. [3] En particular, para funciones generadoras que se comportan suficientemente bien, 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 ofrece ejemplos de los posibles comportamientos de funciones racionales y funciones meromorfas , los capítulos restantes de esta parte analizan la forma en que se pueden utilizar las singularidades de una función para analizar el comportamiento asintótico de su serie de potencias. aplique este método a una gran cantidad de ejemplos combinatorios y estudie el método de integración de contornos del punto de silla para manejar algunos ejemplos más complicados. [1] [3]
La parte final investiga el comportamiento de estructuras combinatorias aleatorias, en lugar del número total de estructuras, utilizando la misma caja de herramientas. Más allá de los valores esperados para cantidades combinatorias de interés, también estudia teoremas de límites y teoría de grandes desviaciones para estas cantidades. Tres apéndices proporcionan antecedentes sobre combinatoria y asintótica, análisis complejos y teoría de la probabilidad. [3]
Las estructuras combinatorias que se investigan a lo largo del libro abarcan ampliamente secuencias , lenguajes formales , particiones y composiciones de enteros , permutaciones , gráficos y caminos en gráficos y caminos de celosía . Con estos temas, el análisis del libro se conecta con aplicaciones en otras áreas, incluida el álgebra abstracta , la teoría de números y el análisis de algoritmos . [2] [4]
La combinatoria analítica no es principalmente un libro de texto; por ejemplo, no tiene ejercicios. [4] Sin embargo, se puede utilizar como libro de texto para una materia optativa de nivel superior de pregrado, [5] un curso de posgrado, [4] o un seminario, [3] aunque el crítico Miklós Bóna escribe que se necesita cierta selección, ya que "tiene material suficiente para tres o más semestres". [2] También puede ser una referencia para los investigadores en este tema. [3]
El crítico Toufik Mansour lo llama no sólo "un tratamiento teórico integral" sino también "una lectura interesante". [3] El crítico Christopher Hanusa escribe que "el estilo de escritura es atractivo, el material temático es contemporáneo y fascinante", y recomienda el libro a cualquiera que "aprenda o trabaje en combinatoria". [4]
La combinatoria analítica ganó el premio Leroy P. Steele de exposición matemática de la American Mathematical Society en 2019 (póstumamente para Flajolet). La mención 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 cita una reseña 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]