Analítica combinatoria 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 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.
Temas
La parte principal del libro está organizada en tres partes. La primera parte, que cubre tres capítulos y aproximadamente el primer trimestre del libro, se refiere al 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 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 desde el análisis complejo a la función generadora, para comprender las asintóticas. del número de objetos en una clase combinatoria. [3] En particular, para funciones generadoras que se comporten suficientemente bien, la fórmula integral de Cauchy se puede utilizar para recuperar los coeficientes de la serie de potencia (el objeto real 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 funciones racionales y funciones meromórficas , los capítulos restantes de esta parte discuten la forma en que las singularidades de una función pueden usarse 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 de montar 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 las cantidades combinatorias de interés, también estudia los teoremas de límites y la teoría de las grandes desviaciones para estas cantidades. Tres apéndices proporcionan antecedentes sobre combinatoria y asintótica, en análisis complejo y en teoría de probabilidades. [3]
Las estructuras combinatorias que se investigan a lo largo del libro abarcan ampliamente secuencias , lenguajes formales , particiones y composiciones , permutaciones , gráficos y rutas en gráficos y rutas de celosía . Con estos temas, el análisis del libro se conecta a aplicaciones en otras áreas, como el álgebra abstracta , la teoría de números y el análisis de algoritmos . [2] [4]
Audiencia y recepción
La Combinatoria Analítica no es principalmente un libro de texto; por ejemplo, no tiene ejercicios. [4] No obstante, se puede utilizar como libro de texto para una electiva 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 "ha 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 completo" sino "una lectura interesante". [3] El crítico Christopher Hanusa escribe que "el estilo de escritura es acogedor, el material de la asignatura 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 altamente 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, concluye Bóna, "Ahora se define la Combinatoria Analítica. Los autores escribieron el libro sobre ella". [2]
Referencias
- ^ a b c d e f Pemantle, Robin (septiembre de 2010), "Revisión de Combinatoria analítica ", Revisión de SIAM , 52 (3): 572-576, JSTOR 20780175
- ^ a b c d e f Bóna, Miklós (junio de 2010), "Review of Analytic Combinatorics " (PDF) , ACM SIGACT News , 41 (2): 11, doi : 10.1145 / 1814370.1814373
- ^ a b c d e f g h Mansour, Toufik, "Revisión de la combinatoria analítica ", zbMATH , Zbl 1165.05001
- ^ a b c d Hanusa, Christopher (julio de 2009), "Revisión de Combinatoria Analítica " , Revisiones MAA , Asociación Matemática de América
- ^ a b c "Premios Leroy P. Steele 2019" (PDF) , Notices of the American Mathematical Society , 66 (4): 594–598, abril de 2019
enlaces externos
- Sitio web del autor de Analytic Combinatorics , que incluye una copia descargable de texto completo del libro