¿Cuál es la diferencia entre la combinatoria analítica y la teoría de las especies combinatorias?

Question

Ayer hice la pregunta ¿Por qué un combinador debe conocer la teoría de las categorías? donde Chris Taylor me sugirió que echara un vistazo a las especies combinatorias. Había oído el término antes, pero no he leído más sobre él que su entrada en Wikipedia . Para mí es esencialmente como combinatoria analítica vestido con el lenguaje de las categorías. ¿Es esto correcto? ¿Podemos hacer cosas con las especies que son imposibles con la combinatoria analítica (o viceversa)?

Answer 1

La combinatoria analítica le indica cómo extraer información útil de una función generadora. La teoría de las especies combinatorias es, entre otras cosas, una forma elegante de escribir las funciones generadoras a partir de la descripción de un problema combinatorio. Así que ambas son complementarias.

Recomiendo los libros de Bergeron, Labelle y Leroux _Especies combinatorias y estructuras arbóreas_ para conocer realmente a este último.

Answer 2

La combinatoria analítica utiliza funciones generadoras que son series de potencias de funciones analíticas en alguna región. La ubicación de las singularidades y los residuos o el comportamiento asintótico cerca de las singularidades se utilizan para tratar la asintótica de los coeficientes. Se trata de cálculos no formales que no pueden realizarse de forma directa con series de potencias formales.

La especie es una versión enriquecida del uso completamente formal de las funciones generadoras exponenciales. No es necesario que la serie converja en algún lugar. A grandes rasgos, se trata de un recuento finito, pero manteniendo la pista de los automorfismos u otra "estructura".

Answer 3

Yo ofrecería la siguiente diferencia entre ambos.

La teoría de las especies ofrece un marco extremadamente formal para definir una clase combinatoria. Es lo suficientemente potente como para abordar la cuestión de cuándo tiene sentido una especificación(*), cosa que no hace la combinatoria analítica. Es un contexto en el que se pueden modelar combinatoriamente muchos fenómenos analíticos (especialmente las ecuaciones diferenciales) y abordar cuestiones meta como cuántas clases combinatorias existen. Es un paso más allá de la enumeración de Polya, y como tal no sólo se ocupa de las funciones generadoras exponenciales, también proporciona acceso a las funciones generadoras ordinarias.

Las técnicas de la combinatoria analítica (por ejemplo, en el texto de Flajolet y Sedgewick) son mucho más concretas. Se concentran en unos pocos operadores: ciclos, conjuntos, etc. y luego van mucho más allá en el análisis de la función generadora relacionada. Por ello, se centran más en los algoritmos (y las implementaciones) y en los métodos que funcionan en contextos precisos. Las singularidades cuentan la historia tanto del recuento como de la distribución de los parámetros, lo cual es notable.

Espero que eso ayude.

(*) Este artículo traduce algunas de las condiciones en condiciones notablemente sencillas. http://www.sciencedirect.com/science/article/pii/S0097316512000908 Algoritmos para estructuras combinatorias: Sistemas bien fundados e iteraciones de Newton Carine Pivoteau, Bruno Salvy, Michèle Soria

Answer 4

En el momento de escribir este artículo de la Wikipedia sobre combinatoria analítica no entra en absoluto en el meollo de la combinatoria analítica, que es la parte del análisis complejo. El artículo sólo cubre la parte simbólica que es la primera mitad del libro sobre Combinatoria Analítica: http://algo.inria.fr/flajolet/Publications/book.pdf

La segunda mitad del libro es la parte de análisis sobre asintótica mencionada en la respuesta de zyx.