Combinatoria analítica (libro)

Combinatoria Analítica es un libro sobre las matemáticas de la enumeración combinatoria , que utiliza funciones generadoras y análisis complejo para comprender las tasas de crecimiento del número 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 sobre el 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 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 ],} tratan sobre la aplicación de herramientas del análisis complejo a la función generadora, con el fin de comprender la asintótica del número de objetos en una clase combinatoria. ^{[ 3 ]} En particular, para funciones generadoras suficientemente bien comportadas, la fórmula integral de Cauchy puede utilizarse para recuperar los coeficientes de la serie de potencias (el verdadero objeto de estudio) a partir de la función generadora, y el conocimiento de las singularidades de la función puede utilizarse 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 meromorfas , los capítulos restantes de esta parte discuten la forma en que las singularidades de una función pueden utilizarse para analizar el comportamiento asintótico de su serie de potencias, aplican este método a un gran número de ejemplos combinatorios y estudian el método del punto de silla de la integración de contorno para manejar algunos ejemplos más complejos. ^{[ 1 ] [ 3 ]}

La parte final investiga el comportamiento de estructuras combinatorias aleatorias, en lugar del número total de estructuras, utilizando el mismo conjunto de herramientas. Además de los valores esperados para cantidades combinatorias de interés, también estudia teoremas límite y la teoría de grandes desviaciones para estas cantidades. Tres apéndices proporcionan información básica sobre combinatoria y asintótica, análisis complejo y teoría de la probabilidad. ^{[ 3 ]}

Las estructuras combinatorias que se investigan a lo largo del libro abarcan una amplia gama de temas, incluyendo secuencias , lenguajes formales , particiones y composiciones de 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 ]}

Combinatoria Analítica no es principalmente un libro de texto; por ejemplo, no tiene ejercicios. ^{[ 4 ]} Sin embargo, puede usarse como libro de texto para una asignatura optativa de nivel superior de pregrado, ^{[ 5 ]} un curso de posgrado, ^{[ 4 ]} o un seminario, ^{[ 3 ]} aunque el revisor Miklós Bóna escribe que es necesaria 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 solo como "un tratamiento teórico exhaustivo" sino también como "una lectura interesante". ^{[ 3 ]} El crítico Christopher Hanusa escribe que "el estilo de escritura es atractivo, el tema es actual y fascinante", y recomienda el libro a cualquiera que "estudie o trabaje en combinatoria". ^{[ 4 ]}

Analytic Combinatorics ganó el Premio Leroy P. Steele a la Exposición Matemática de la Sociedad Matemática Americana en 2019 (póstumamente para Flajolet). La mención del premio describió 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 mención también citó una reseña de Robin Pemantle que afirmaba que "Este es uno de esos libros que marcan el surgimiento de un subcampo", el subcampo de la combinatoria analítica . ^{[ 1 ] [ 5 ]} De manera similar, Bóna concluye: "La combinatoria analítica ya está definida. Los autores escribieron el libro sobre ella". ^{[ 2 ]}

• Sitio web del autor de Combinatoria Analítica , que incluye una copia descargable del texto completo del libro.