Combinatoria analítica

En matemáticas , específicamente en combinación , la combinatoria analítica (en inglés  : combinatoria analítica ) es un conjunto de técnicas que describen problemas combinatorios en el lenguaje de funciones generadoras y, en particular, se basan en el análisis complejo para obtener resultados asintóticos sobre objetos combinatorios iniciales.

Los resultados de la combinatoria analítica permiten, en particular, un análisis fino de la complejidad de ciertos algoritmos .

Introducción

La combinatoria analítica se basa fundamentalmente en dos enfoques: el primer enfoque, combinatorio, también denominado a veces método simbólico , permite describir relaciones entre objetos matemáticos discretos transcribiéndolos directamente en términos de operaciones algebraicas sobre la serie generadora asociada; el segundo enfoque, analítico, utiliza o desarrolla herramientas de análisis complejo para extraer de estas series generadoras información sobre el comportamiento asintótico del número de objetos enumerados. Por tanto, la naturaleza de las singularidades de estas series es la clave para el estudio del comportamiento asintótico de los objetos discretos iniciales. Una aplicación importante es el estudio de propiedades probabilísticas de grandes estructuras aleatorias .

Esta teoría ha sido ampliamente desarrollada en particular por Philippe Flajolet y su escuela. Se detalla en su libro con Robert Sedgewick , Analytic Combinatorics . Encuentra su fuente en el trabajo de precursores como Leonhard Euler , Arthur Cayley , Srinivasa Ramanujan , Gaston Darboux , George Pólya y Donald Knuth .

Clases combinatorias

El método simbólico se basa en el concepto de clase combinatoria , es decir, conjuntos de objetos, donde cada objeto tiene un tamaño . El método hace posible traducir operaciones de conjuntos en las clases en operaciones algebraicas en la serie generadora asociada. El resultado es un proceso de traducción puramente formal que se puede automatizar. En la práctica, las llamadas series generadoras ordinarias se utilizan a menudo para estructuras no etiquetadas y series generadoras exponenciales para estructuras etiquetadas. Sin embargo, también se pueden utilizar otros tipos de series generadoras (Dirichlet, Poisson, Bell, Lambert, Wright, ...).

Definiciones

Una clase combinatoria es por definición un conjunto provisto de una aplicación llamada tamaño que, con cada elemento del conjunto, asocia un entero natural . También pedimos que, para cada uno , el número de elementos de tamaño sea finito . PARA{\ Displaystyle {\ mathcal {A}}}|⋅|:PARA→NO{\ Displaystyle | \ cdot |: {\ mathcal {A}} \ to \ mathbb {N}}Para{\ Displaystyle a}PARA{\ Displaystyle {\ mathcal {A}}}|Para|{\ Displaystyle | a |}no{\ Displaystyle n}no{\ Displaystyle n}

Como sugiere la definición, el mismo conjunto puede tener varios tamaños diferentes. Por tanto, el tamaño de los árboles binarios puede ser su número de vértice; otro tamaño es su altura. Pero el número de hojas no es un tamaño válido, porque hay un número infinito de árboles binarios "filiformes" (donde cada nodo tiene un solo hijo) que tienen una sola hoja. En general, un objeto de cierto tamaño está formado por componentes elementales que a veces se denominan átomos (como los vértices de un gráfico, por ejemplo).

Sea ahora una matriz combinatoria, y el número de elementos significativos de . La serie generadora ordinaria asociada con es por definición la serie definida por PARA{\ Displaystyle {\ mathcal {A}}}Parano{\ Displaystyle a_ {n}}no{\ Displaystyle n}PARA{\ Displaystyle {\ mathcal {A}}}PARA{\ Displaystyle {\ mathcal {A}}}PARA(z){\ Displaystyle A (z)}

PARA(z)=∑no=0∞Paranozno{\ Displaystyle A (z) = \ sum _ {n = 0} ^ {\ infty} a_ {n} z ^ {n}}.

A veces es conveniente considerar otra expresión equivalente para la serie, a saber:

PARA(z)=∑Para∈PARAz|Para|{\ Displaystyle A (z) = \ sum _ {a \ in {\ mathcal {A}}} z ^ {| a |}}.

También consideramos, en el caso de estructuras etiquetadas, series generadoras exponenciales que se discutirán a continuación.

En general, las series generadoras asociadas con la enumeración de objetos combinatorios son series formales , que pueden manejarse sin considerar la convergencia (en el sentido de convergencia en reales o en complejos), pero de hecho existe una noción de convergencia en el anillo. de serie formal que se basa en la valoración de la serie y que da un marco riguroso a todas las manipulaciones que se mencionan a continuación. En el contexto de la combinatoria analítica, las cuestiones de convergencia juegan un papel, ya que estudiamos el comportamiento de las series en puntos precisos, en el marco del análisis complejo. La observación fundamental utilizada, que se explica más adelante, es que la naturaleza de la singularidad en el eje real positivo proporciona información precisa sobre el crecimiento del número de objetos de tamaño . Parano{\ Displaystyle a_ {n}}no{\ Displaystyle n}

Una notación útil para extraer coeficientes de una serie generadora es la siguiente: denotamos por el coeficiente de la variable , de modo que, para F(z){\ Displaystyle f (z)}[zno]{\ Displaystyle [z ^ {n}]}zno{\ Displaystyle z ^ {n}}

F(z)=∑no=0∞Fnozno{\ Displaystyle f (z) = \ sum _ {n = 0} ^ {\ infty} f_ {n} z ^ {n}},

se tiene :

[zno]F(z)=Fno{\ Displaystyle [z ^ {n}] f (z) = f_ {n}}.

En el resto de este artículo, a veces hablaremos con un ligero abuso de lenguaje de los coeficientes de una función, para designar los coeficientes de la expansión de Taylor en 0 de esta función.

Ejemplos de

Algunos ejemplos comunes son los siguientes.

• Clase de palabras en un alfabeto binario, el tamaño es la longitud de la palabra. Hay palabras de largo . La serie de generadores es .2no{\ Displaystyle 2 ^ {n}}no{\ Displaystyle n}11-2z{\ displaystyle {\ frac {1} {1-2z}}}
• Composiciones de enteros (una composición de un entero positivo es una secuencia de enteros positivos como ). Cada entero positivo tiene composiciones. La serie de generadores es .no{\ Displaystyle n}(pag1,pag2,...,pagr){\ Displaystyle (p_ {1}, p_ {2}, \ ldots, p_ {r})}pag1+pag2+⋯+pagr=no{\ Displaystyle p_ {1} + p_ {2} + \ cdots + p_ {r} = n}no{\ Displaystyle n}2no-1{\ Displaystyle 2 ^ {n-1}}z1-2z{\ Displaystyle {\ frac {z} {1-2z}}}
• Árboles binarios completos. El número de árboles binarios completos con nodos internos es , y la serie del generador es .no{\ Displaystyle n}1no+1(2nono){\ Displaystyle {\ frac {1} {n + 1}} {\ binom {2n} {n}}}1-1-4z2z{\ Displaystyle {\ frac {1 - {\ sqrt {1-4z}}} {2z}}}

El método simbólico

El método simbólico es un proceso que permite traducir directamente relaciones entre clases combinatorias en la correspondiente serie generadora. El algoritmo consiste en partir de clases combinatorias muy simples y componerlas utilizando operadores de comportamiento conocido. Estos operadores de conjuntos comprenden varias operaciones simples, como la unión disjunta , el producto cartesiano ; otras operaciones, como el conjunto de partes , la formación de secuencias , de multijuegos son un poco más complejas. Finalmente, son posibles las definiciones recursivas . El atractivo del método es que la definición del conjunto, o simbólico , se traduce directamente en relaciones algebraicas sobre las funciones generadoras .

Generalmente se utilizan dos tipos de series de generadores en combinatoria, series de generadores ordinarios , para clases combinatorias de objetos sin etiquetar, y series de generadores exponenciales , para clases combinatorias de objetos etiquetados,

Es costumbre, en esta teoría, denotar las clases combinatorias con letras cursivas, y su serie generadora con las mismas letras, líneas rectas. Así, las series asociadas con clases combinatorias o se denotan respectivamente y . PARA,B{\ displaystyle {\ mathcal {A}}, {\ mathcal {B}}}VS{\ Displaystyle {\ mathcal {C}}}PARA(z),B(z){\ Displaystyle A (z), B (z)}VS(z){\ Displaystyle C (z)}

Construcciones elementales

Los ladrillos básicos son clases formadas por un solo objeto. Son útiles dos tipos de clases: aquellas en las que el singleton es de tamaño cero y aquellas en las que el singleton es de tamaño uno. Por tanto, una clase del primer tipo tiene un elemento de tamaño cero y su serie generadora es la función constante . Una clase del segundo tipo tiene un solo elemento, de tamaño uno, y su serie de generador es así . Las operaciones elementales son la unión disjunta, el producto cartesiano, la formación de secuencias. mi={ε}{\ Displaystyle {\ mathcal {E}} = \ {\ varepsilon \}}ε{\ Displaystyle \ varepsilon}mi(z)=1{\ Displaystyle E (z) = 1}Z={z}{\ Displaystyle {\ mathcal {Z}} = \ {z \}}Z(z)=z{\ Displaystyle Z (z) = z}

Unión desarticulada

Escribimos si la clase es la unión disjunta de las clases y . Esta relación se traduce en generar series por PARA=B+VS{\ Displaystyle {\ mathcal {A}} = {\ mathcal {B}} + {\ mathcal {C}}}PARA{\ Displaystyle {\ mathcal {A}}}B{\ Displaystyle {\ mathcal {B}}}VS{\ Displaystyle {\ mathcal {C}}}

PARA(z)=B(z)+VS(z){\ Displaystyle A (z) = B (z) + C (z)}

ya que de hecho

PARA(z)=∑Para∈PARAz|Para|=∑Para∈Bz|Para|+∑Para∈VSz|Para|=B(z)+VS(z){\ Displaystyle A (z) = \ sum _ {a \ in {\ mathcal {A}}} z ^ {| a |} = \ sum _ {a \ in {\ mathcal {B}}} z ^ {| a |} + \ sum _ {a \ in {\ mathcal {C}}} z ^ {| a |} = B (z) + C (z)}. producto cartesiano

Escribimos si la clase es el conjunto de pares , con y . La función de tamaño está definida por . Entonces tenemos, para la serie generadora, la relación PARA=B×VS{\ Displaystyle {\ mathcal {A}} = {\ mathcal {B}} \ times {\ mathcal {C}}}PARA{\ Displaystyle {\ mathcal {A}}}Para=(B,vs){\ Displaystyle a = (b, c)}B∈B{\ Displaystyle b \ in {\ mathcal {B}}}vs∈VS{\ Displaystyle c \ in {\ mathcal {C}}}|Para|=|B|+|vs|{\ Displaystyle | a | = | b | + | c |}

PARA(z)=B(z)VS(z){\ Displaystyle A (z) = B (z) C (z)}. Secuencias

Escribimos cuando es el conjunto de secuencias finitas de elementos de . Esta construcción también se llama la estrella de Kleene en la teoría del lenguaje . Se puede escribir más formalmente como PARA=Smiq(B){\ Displaystyle {\ mathcal {A}} = {\ mathsf {Seq}} ({\ mathcal {B}})}PARA{\ Displaystyle {\ mathcal {A}}}B{\ Displaystyle {\ mathcal {B}}}

PARA=mi+B+B×B+B×B×B+⋯{\ Displaystyle {\ mathcal {A}} = {\ mathcal {E}} + {\ mathcal {B}} + {\ mathcal {B}} \ times {\ mathcal {B}} + {\ mathcal {B} } \ times {\ mathcal {B}} \ times {\ mathcal {B}} + \ cdots}, o incluso .PARA={(B1,...,Bh)∣h≥0,Bj∈B}{\ Displaystyle {\ mathcal {A}} = \ {(b_ {1}, \ ldots, b_ {h}) \ mid h \ geq 0, b_ {j} \ in {\ mathcal {B}} \}}

El tamaño de una suite es la suma de los tamaños de sus componentes. Para que la operación esté bien definida, la clase no debe contener ningún elemento de tamaño 0 porque de lo contrario la clase contendría una infinidad de elementos de un tamaño determinado. La traducción en series generadoras es (B1,...,Bh){\ Displaystyle (b_ {1}, \ ldots, b_ {h})}B{\ Displaystyle {\ mathcal {B}}}PARA{\ Displaystyle {\ mathcal {A}}}

PARA(z)=11-B(z){\ Displaystyle A (z) = {\ frac {1} {1-B (z)}}}.

La serie a veces se denomina cuasi-inversa de la serie . PARA(z){\ Displaystyle A (z)}B(z){\ Displaystyle B (z)}

Definición recursiva

Cuando se cumplen ciertas condiciones bastante técnicas, podemos definir una clase combinatoria de forma recursiva. Aquí hay unos ejemplos.

Árboles binarios

El primer ejemplo es el de los árboles binarios. Un árbol binario es el árbol binario vacío o está formado por una raíz y dos subárboles que son árboles binarios. Por tanto, la ecuación de la clase combinatoria de árboles binarios es: B{\ Displaystyle {\ mathcal {B}}}

B=mi+Z×B×B{\ Displaystyle {\ mathcal {B}} = {\ mathcal {E}} + {\ mathcal {Z}} \ times {\ mathcal {B}} \ times {\ mathcal {B}}},

donde se reduce a un elemento de tamaño 0 y se compone de un elemento de tamaño 1. Esta ecuación se traduce en la ecuación mi{\ Displaystyle {\ mathcal {E}}}Z{\ Displaystyle {\ mathcal {Z}}}

B(z)=1+zB(z)2{\ Displaystyle B (z) = 1 + zB (z) ^ {2}}.Árboles unarios-binarios

Un árbol unario-binario es un árbol donde cada nodo interno tiene uno o dos hijos. La ecuación simbólica está escrita

U=Z+Z×B+Z×B×B{\ Displaystyle {\ mathcal {U}} = {\ mathcal {Z}} + {\ mathcal {Z}} \ times {\ mathcal {B}} + {\ mathcal {Z}} \ times {\ mathcal {B }} \ times {\ mathcal {B}}}

de donde deducimos la ecuación funcional

U(z)=z+zU(z)+zU(z)2{\ Displaystyle U (z) = z + zU (z) + zU (z) ^ {2}}.

Ejemplos de

Podemos utilizar el método simbólico incluso en casos muy básicos:

Palabras binarias

Una palabra binaria es una secuencia de símbolos 0 y 1. Tenemos dos clases combinadas y cuya serie generadora . Las palabras binarias vienen dadas por la construcción Z0={0}{\ Displaystyle {\ mathcal {Z}} _ {0} = \ {0 \}}Z1={1}{\ Displaystyle {\ mathcal {Z}} _ {1} = \ {1 \}}z{\ Displaystyle z}

W0=Smiq(Z0+Z1){\ displaystyle {\ mathcal {W}} _ {0} = {\ mathsf {Seq}} ({\ mathcal {Z}} _ {0} + {\ mathcal {Z}} _ {1})},

su serie de generadores es

W(z)=11-(z+z){\ Displaystyle W (z) = {\ frac {1} {1- (z + z)}}} y .[zno]W(z)=2no{\ Displaystyle [z ^ {n}] W (z) = 2 ^ {n}}

Está usando artillería pesada para un ejemplo simple.

Composición restringida de números enteros

El problema es cubrir el segmento con ladrillos de tamaño 1 y 2, es decir escribir el todo como una suma cuyos términos son 1 o 2, y contar el número de formas de hacerlo. Por ejemplo, el entero 4 tiene las cinco publicaciones: [0,no]{\ Displaystyle [0, n]}no{\ Displaystyle n}

4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1 + 1 = 2 + 2.

Es fácil ver directamente que el número de estas composiciones de es , el número de Fibonacci . Para utilizar el método simbólico, consideramos dos clases y están compuestas por un solo elemento de tamaño 1 y tamaño 2 respectivamente. Entonces la clase general es no{\ Displaystyle n}Fno{\ Displaystyle F_ {n}}no{\ Displaystyle n}Z1{\ Displaystyle {\ mathcal {Z}} _ {1}}Z2{\ Displaystyle {\ mathcal {Z}} _ {2}}

F=Smiq(Z1+Z2){\ Displaystyle {\ mathcal {F}} = {\ mathsf {Seq}} ({\ mathcal {Z}} _ {1} + {\ mathcal {Z}} _ {2})}

y la serie del generador es:

F(z)=11-z-z2=1+z+2z2+3z3+5z4+⋯{\ Displaystyle F (z) = {\ frac {1} {1-zz ^ {2}}} = 1 + z + 2z ^ {2} + 3z ^ {3} + 5z ^ {4} + \ cdots}.

Otras construcciones simbólicas

Otras construcciones simbólicas importantes son: Ciclos . Los ciclos son secuencias similares, excepto que dos objetos que se obtienen entre sí mediante una rotación circular no se consideran distintos. La serie de generadores es mucho más complicada; en el caso etiquetado, es más sencillo. Aquí está escrito PARA=VSyvs(B){\ Displaystyle {\ mathcal {A}} = {\ mathsf {Cyc}} ({\ mathcal {B}})}

PARA(z)=∑k=1∞ϕ(k)kIniciar sesión⁡11-B(zk){\ Displaystyle A (z) = \ sum _ {k = 1} ^ {\ infty} {\ frac {\ phi (k)} {k}} \ log {\ frac {1} {1-B (z ^ {k})}}}

donde está la indicatriz de Euler . Clase puntiaguda . La clase está formada por objetos que son "puntiagudos": en cada objeto, se distingue un átomo. Por ejemplo, los árboles enraizados son árboles sin puntas. Formalmente, cada objeto se incrementa en un elemento de tamaño cero en uno de sus átomos. La serie de generadores es ϕ(k){\ Displaystyle \ phi (k) \,}ΘB{\ Displaystyle \ Theta {\ mathcal {B}}}B{\ Displaystyle {\ mathcal {B}}}

z∂∂zB(z){\ Displaystyle z {\ frac {\ parcial} {\ parcial z}} B (z)}.

Sustitución . La clase se obtiene sustituyendo, por cada átomo de un elemento de , un elemento de la clase . La serie de generadores es simple . B∘VS{\ Displaystyle {\ mathcal {B}} \ circ {\ mathcal {C}}}B{\ Displaystyle {\ mathcal {B}}}VS{\ Displaystyle {\ mathcal {C}}}B(VS(z)){\ Displaystyle B (C (z))}

Analizar

Los métodos de análisis complejos se centran en el proceso de extracción de información asintótica a partir de funciones generadoras. Existe un conjunto de resultados que proporcionan una traducción sistemática entre las funciones generadoras y la forma asintótica de los coeficientes.

En la mayoría de las situaciones que surgen en combinatoria, una serie formal

F(z)=∑no≥0Fnozno{\ Displaystyle f (z) = \ sum _ {n \ geq 0} f_ {n} z ^ {n}}

de enumeración puede verse como el desarrollo, alrededor de 0, de una función analítica . El radio de convergencia de la serie viene dado, por ejemplo, por F(z){\ Displaystyle f (z)} R{\ Displaystyle R}

1/R=lim sup|Fno|1/no{\ Displaystyle 1 / R = \ limsup | f_ {n} | ^ {1 / n}}.

Esto significa que

Fno∼R-noθ(no{\ Displaystyle f_ {n} \ sim R ^ {- n} \ theta (n})

donde es una función sub-exponencial de . Por lo tanto, hay al menos una singularidad en el borde del disco de convergencia, y un teorema de Pringsheim clásico dice que si los coeficientes son positivos, que es el caso de enumerar series, entonces existe una singularidad positiva real en el punto . θ(no){\ Displaystyle \ theta (n)}no{\ Displaystyle n}Fno{\ Displaystyle f_ {n}}z=R{\ Displaystyle z = R}

Caso de serie racional

Para series racionales, una descomposición en elementos simples da una forma cerrada para el término , que por lo tanto se escribe como una suma de términos de la forma . Por tanto, si la singularidad dominante R es de multiplicidad , entonces Fno{\ Displaystyle f_ {n}}vsjnojRj-no{\ Displaystyle c_ {j} n ^ {j} R_ {j} ^ {- n}}k{\ Displaystyle k}

[zno]F(z)∼(limz→RF(z)(z-R)k)×R-nonok-1(k-1)!{\ Displaystyle [z ^ {n}] f (z) \ sim \ left (\ lim _ {z \ rightarrow R} f (z) (zR) ^ {k} \ right) \ times {\ frac {R ^ {-n} n ^ {k-1}} {(k-1)!}}}.

Ejemplo . Consideramos la serie racional

F(z)=(1-z2/2)-5(1-z3)-1(1-2z)-5(1-z-z2)-1{\ Displaystyle f (z) = (1-z ^ {2} / 2) ^ {- 5} (1-z ^ {3}) ^ {- 1} (1-2z) ^ {- 5} (1 -zz ^ {2}) ^ {- 1}}.

Sus singularidades son (donde denota el número áureo). La singularidad dominante es 1/2 y su multiplicidad es 5. Por lo tanto, tenemos 2,-2,1,1/2,ϕ,ϕ¯{\ Displaystyle {\ sqrt {2}}, - {\ sqrt {2}}, 1,1 / 2, \ phi, {\ bar {\ phi}}}ϕ{\ Displaystyle \ phi}

[zno]F(z)∼104857611764914!2nono4{\ Displaystyle [z ^ {n}] f (z) \ sim {\ frac {1048576} {117649}} {\ frac {1} {4!}} 2 ^ {n} n ^ {4}}.

Caso de serie algebraico-logarítmica

Considere ahora la clase de funciones algebraico-logarítmicas, es decir, las sumas y productos de y de . Para generar series que tengan tal forma, los métodos de análisis complejos dan las siguientes asintóticas para sus coeficientes, expresados ​​aquí en el caso donde la singularidad es 1 (siempre podemos volver a ella mediante un cambio de variable): (1-z)α{\ Displaystyle (1-z) ^ {\ alpha}}Iniciar sesión⁡(1-z){\ Displaystyle \ log (1-z)}

Deja y . Se tieneα∈R∖{0,-1,-2,...}{\ Displaystyle \ alpha \ in \ mathbb {R} \ setminus \ {0, -1, -2, \ ldots \}}k∈NO{\ Displaystyle k \ in \ mathbb {N}} [zno]1(1-z)αIniciar sesiónk⁡(11-z)∼noα-1Γ(α)Iniciar sesiónk⁡(no){\ Displaystyle [z ^ {n}] {\ frac {1} {(1-z) ^ {\ alpha}}} \ log ^ {k} \ left ({\ frac {1} {1-z}} \ right) \ sim {\ frac {n ^ {\ alpha -1}} {\ Gamma (\ alpha)}} \ log ^ {k} (n)}, donde es la función Gamma habitual.Γ{\ Displaystyle \ Gamma}

Este equivalente asintótico puede, de hecho, ser empujado a cualquier orden, lo que da, por ejemplo:

Función	Coeficientes
(1-z)3/2{\ Displaystyle (1-z) ^ {3/2}}	1πno5(34+4532no+1155512no2+O(1no3)){\ Displaystyle {\ frac {1} {\ sqrt {\ pi n ^ {5}}}} {\ bigl (} {\ frac {3} {4}} + {\ frac {45} {32n}} + {\ frac {1155} {512n ^ {2}}} + O {\ bigl (} {\ frac {1} {n ^ {3}}} {\ bigr)} {\ bigr)}}
(1-z)1/2{\ Displaystyle (1-z) ^ {1/2}}	-1πno3(12+3dieciséisno+25256no2+O(1no3)){\ Displaystyle - {\ frac {1} {\ sqrt {\ pi n ^ {3}}}} {\ bigl (} {\ frac {1} {2}} + {\ frac {3} {16n}} + {\ frac {25} {256n ^ {2}}} + O ({\ frac {1} {n ^ {3}}}) {\ bigr)}}
(1-z)1/2Iniciar sesión⁡(1-z){\ Displaystyle (1-z) ^ {1/2} \ log (1-z)}	-1πno3(12Iniciar sesión⁡no+γ+2Iniciar sesión⁡2-22+O(Iniciar sesión⁡nono)){\ Displaystyle - {\ frac {1} {\ sqrt {\ pi n ^ {3}}}} {\ bigl (} {\ frac {1} {2}} \ log n + {\ frac {\ gamma + 2 \ log 2-2} {2}} + O {\ bigl (} {\ frac {\ log n} {n}} {\ bigr)} {\ bigr)}}
(1-z)-1/2{\ Displaystyle (1-z) ^ {- 1/2}}	1πno(1-18no+1128no2+51024no3+O(1no4)){\ Displaystyle {\ frac {1} {\ sqrt {\ pi n}}} {\ bigl (} 1 - {\ frac {1} {8n}} + {\ frac {1} {128n ^ {2}} } + {\ frac {5} {1024n ^ {3}}} + O {\ bigl (} {\ frac {1} {n ^ {4}}} {\ bigr)} {\ bigr)}}
(1-z)-1/3{\ Displaystyle (1-z) ^ {- 1/3}}	1Γ(1/3)no2/3(1+O(1no)){\ Displaystyle {\ frac {1} {\ Gamma (1/3) n ^ {2/3}}} {\ bigl (} 1 + O {\ bigl (} {\ frac {1} {n}} { \ bigr)} {\ bigr)}}
(1-z)-1Iniciar sesión2⁡(1-z){\ Displaystyle (1-z) ^ {- 1} \ log ^ {2} (1-z)}	Iniciar sesión2⁡no+2γIniciar sesión⁡no+γ2-π26+O(Iniciar sesión⁡nono){\ Displaystyle \ log ^ {2} n + 2 \ gamma \ log n + \ gamma ^ {2} - {\ frac {\ pi ^ {2}} {6}} + O {\ bigl (} {\ frac {\ log n} {n}} {\ bigr)}}

Tenga en cuenta que la clase de funciones algebraico-logarítmicas no incluye todas las funciones algebraicas, pero cualquier función algebraica tiene una expansión en serie de Puiseux que es una suma infinita de bloques de construcción básicos del tipo , y el truncamiento de esta suma a un orden dado es de hecho una función algebraico-logarítmica. El teorema de transferencia detallado en el siguiente apartado permite vincular la expansión asintótica de los coeficientes de la suma infinita y su truncamiento. (1-z)α{\ Displaystyle (1-z) ^ {\ alpha}}

El teorema de la transferencia

El teorema de la transferencia establece que basta con conocer el comportamiento de dos funciones en torno a su menor singularidad para poder comparar el comportamiento asintótico de sus coeficientes. La declaración es la siguiente.

Sean y ) dos funciones cuya singularidad más pequeña es 1. EntoncesF(z){\ Displaystyle f (z)}gramo(z{\ Displaystyle g (z})- Sí , entonces . - Sí , entonces . - Sí , entonces .F(z)∼z→1gramo(z){\ Displaystyle f (z) \ sim _ {z \ to 1} g (z)}Fno∼gramono{\ Displaystyle f_ {n} \ sim g_ {n}}
F(z)=z→1O(gramo(z)){\ Displaystyle f (z) = _ {z \ to 1} O (g (z))}Fno=O(gramono){\ Displaystyle f_ {n} = O (g_ {n})}
F(z)=z→1o(gramo(z)){\ Displaystyle f (z) = _ {z \ to 1} o (g (z))}Fno=o(gramono){\ Displaystyle f_ {n} = o (g_ {n})}

Un ejemplo

Encontramos a continuación la evaluación asintótica del número de árboles binarios. Partimos de la ecuación simbólica

B=mi+Z×B×B{\ Displaystyle {\ mathcal {B}} = {\ mathcal {E}} + {\ mathcal {Z}} \ times {\ mathcal {B}} \ times {\ mathcal {B}}},

donde se reduce a un elemento de tamaño 0 y se compone de un elemento de tamaño 1. Esta ecuación se traduce en la ecuación mi{\ Displaystyle {\ mathcal {E}}}Z{\ Displaystyle {\ mathcal {Z}}}

B(z)=1+zB(z)2{\ Displaystyle B (z) = 1 + zB (z) ^ {2}}.

Resolvemos la ecuación y encontramos

B(z)=1-1-4z2z{\ Displaystyle B (z) = {\ frac {1 - {\ sqrt {1-4z}}} {2z}}}.

La función tiene una singularidad algebraica en exponente . Alrededor , tenemos z=1/4{\ Displaystyle z = 1/4}1/2{\ Displaystyle 1/2}z=1/4{\ Displaystyle z = 1/4}

B(z)∼2(1-4z)1/2{\ Displaystyle B (z) \ sim 2 (1-4z) ^ {1/2}}

y, por el teorema anterior sobre singularidades algebraico-logarítmicas, obtenemos

[zno]B(z)∼-24nono-3/2Γ(-1/2)=4nono-3/2π{\ Displaystyle [z ^ {n}] B (z) \ sim -2 {\ frac {4 ^ {n} n ^ {- 3/2}} {\ Gamma (-1/2)}} = {\ frac {4 ^ {n} n ^ {- 3/2}} {\ sqrt {\ pi}}}}

porque . Γ(-1/2)=-2π{\ Displaystyle \ Gamma (-1/2) = - 2 {\ sqrt {\ pi}}}

Clases combinatorias etiquetadas

Una clase combinatoria está etiquetada si sus elementos están etiquetados. Por definición, tal objeto combinatorio, de tamaño , también está dotado de una permutación de . Los ejemplos más relevantes de objetos etiquetados son gráficos. no{\ Displaystyle n}{1,...,no}{\ Displaystyle \ {1, \ ldots, n \}}

Para enumerar los objetos de una clase etiquetada, usamos series generadoras exponenciales, donde los coeficientes están normalizados por un factorial.

Definición

Más formalmente, una clase combinatoria etiquetada o , para , el número de objetos de tamaño en esta clase. La serie de generadores exponenciales asociada con es PARA{\ Displaystyle {\ mathcal {A}}}Parano{\ Displaystyle a_ {n}}no≥0{\ Displaystyle n \ geq 0}no{\ Displaystyle n}PARA{\ Displaystyle {\ mathcal {A}}}

PARA(z)=∑no=0∞Paranoznono!{\ Displaystyle A (z) = \ sum _ {n = 0} ^ {\ infty} a_ {n} {\ frac {z ^ {n}} {n!}}}.

Es equivalente a escribir

PARA(z)=∑Para∈PARAz|Para||Para|!{\ Displaystyle A (z) = \ sum _ {a \ in {\ mathcal {A}}} {\ frac {z ^ {| a |}} {| a |!}}} .

Extraer un coeficiente de esta serie da

[zno]PARA(z)=Paranono!{\ Displaystyle [z ^ {n}] A (z) = {\ frac {a_ {n}} {n!}}}, por lo tanto .Parano=no![zno]PARA(z){\ Displaystyle a_ {n} = n! [z ^ {n}] A (z)}

Ejemplos de

Permutaciones . Sea la clase de permutaciones. Su serie de generadores exponenciales es PAG{\ Displaystyle {\ mathcal {P}}}

PAG(z)=∑no≥0no!znono!=11-z{\ Displaystyle P (z) = \ sum _ {n \ geq 0} n! {\ frac {z ^ {n}} {n!}} = {\ frac {1} {1-z}}}.

Gráficos sin aristas . Existe, para cada entero n, un solo gráfico sin aristas. La serie de generadores correspondiente es

∑no≥0znono!=miz{\ Displaystyle \ sum _ {n \ geq 0} {\ frac {z ^ {n}} {n!}} = e ^ {z}}

La misma serie cuenta los gráficos completos.

Gráficos de ciclo . El número de gráficos etiquetados de n vértices formados a partir de un solo ciclo es (n-1)!. Por tanto, su serie de generadores exponenciales es

∑no≥0(no-1)!znono!=∑no≥0znono=Iniciar sesión⁡(11-z){\ Displaystyle \ sum _ {n \ geq 0} (n-1)! {\ frac {z ^ {n}} {n!}} = \ sum _ {n \ geq 0} {\ frac {z ^ { n}} {n}} = \ log {\ bigl (} {\ frac {1} {1-z}} {\ bigr)}}.

Construcciones

Producto

La construcción de una suma disjunta de clases combinatorias se transpone sin modificaciones a las clases etiquetadas. Para el producto, hay que tener más cuidado. Sean y dos clases combinatorias etiquetadas. El producto cartesiano está formado por pares de objetos etiquetados, pero dicho par no está correctamente etiquetado ya que sus elementos no tienen etiquetas distintas. Definimos una estructura asociada, cuyos elementos tienen exactamente las etiquetas , y donde se respeta el orden relativo de las etiquetas de cada elemento. Definimos B{\ Displaystyle {\ mathcal {B}}}VS{\ Displaystyle {\ mathcal {C}}}(B,vs){\ Displaystyle (b, c)}(B′,vs′){\ Displaystyle (b ', c')}{1,...,|B|+|vs|}{\ Displaystyle \ {1, \ ldots, | b | + | c | \}}

B⋆vs{\ Displaystyle b \ star c}

como el conjunto de parejas así reetiquetadas. La familia contiene exactamente elementos. El producto etiquetado clases y es por definición (B′,vs′){\ Displaystyle (b ', c')}B⋆vs{\ Displaystyle b \ star c}(|B|+|vs||B|){\ Displaystyle {\ binom {| b | + | c |} {| b |}}}B{\ Displaystyle {\ mathcal {B}}}VS{\ Displaystyle {\ mathcal {C}}}

PARA=B⋆VS=⋃B∈B,vs∈VSB⋆vs{\ Displaystyle {\ mathcal {A}} = {\ mathcal {B}} \ estrella {\ mathcal {C}} = \ bigcup _ {b \ in {\ mathcal {B}}, c \ in {\ mathcal { C}}} b \ estrella c}.

Para series de generación exponencial, tenemos

PARA(z)=B(z)VS(z){\ Displaystyle A (z) = B (z) C (z)}.

De hecho, para y tenemos B∈B{\ Displaystyle b \ in {\ mathcal {B}}}vs∈VS{\ Displaystyle c \ in {\ mathcal {C}}}

∑Para∈B⋆vsz|Para||Para|!=∑Para∈B⋆vsz|B|+|vs||B|+|vs|!=(|B|+|vs||B|)z|B|+|vs||B|+|vs|!=z|B||B||!z|vs|!|vs|!{\ Displaystyle \ sum _ {a \ in b \ star c} {\ frac {z ^ {| a |}} {| a |!}} = \ sum _ {a \ in b \ star c} {\ frac {z ^ {| b | + | c |}} {| b | + | c |!}} = {\ binom {| b | + | c |} {| b |}} {\ frac {z ^ { | b | + | c |}} {| b | + | c |!}} = {\ frac {z ^ {| b |}} {| b ||!}} {\ frac {z ^ {| c |!}} {| c |!}}},

y entonces

PARA(z)=∑Para∈PARAz|Para||Para|!=∑B∈B∑vs∈VSz|B||B|!z|vs|!|vs|!=B(z)VS(z){\ Displaystyle A (z) = \ sum _ {a \ in {\ mathcal {A}}} {\ frac {z ^ {| a |}} {| a |!}} = \ sum _ {b \ in {\ mathcal {B}}} \ sum _ {c \ in {\ mathcal {C}}} {\ frac {z ^ {| b |}} {| b |!}} {\ frac {z ^ {| c |!}} {| c |!}} = B (z) C (z)}. Secuencia

A partir de la suma disjunta y el producto, construimos el operador de secuencia como en el caso ordinario: Escribimos cuando es el conjunto de secuencias finitas de elementos de ; aquí no tiene ningún elemento de tamaño cero. En otras palabras, PARA=Smiq(B){\ Displaystyle {\ mathcal {A}} = {\ mathsf {Seq}} ({\ mathcal {B}})}PARA{\ Displaystyle {\ mathcal {A}}}B{\ Displaystyle {\ mathcal {B}}}B{\ Displaystyle {\ mathcal {B}}}

PARA=mi+B+B×B+B×B×B+⋯{\ Displaystyle {\ mathcal {A}} = {\ mathcal {E}} + {\ mathcal {B}} + {\ mathcal {B}} \ times {\ mathcal {B}} + {\ mathcal {B} } \ times {\ mathcal {B}} \ times {\ mathcal {B}} + \ cdots},

o donde las suites se vuelven a etiquetar. La serie del generador exponencial es PARA={(B1,...,Bh)∣h≥0,Bj∈B}{\ Displaystyle {\ mathcal {A}} = \ {(b_ {1}, \ ldots, b_ {h}) \ mid h \ geq 0, b_ {j} \ in {\ mathcal {B}} \}}

PARA(z)=∑h≥0B(z)h=11-B(z){\ Displaystyle A (z) = \ sum _ {h \ geq 0} B (z) ^ {h} = {\ frac {1} {1-B (z)}}}.Todas las partes

Las definiciones de conjunto y ciclo que se dan aquí también se aplican a estructuras no etiquetadas. Definimos la clase

Smith(B){\ Displaystyle {\ mathsf {Conjunto}} _ {h} ({\ mathcal {B}})}

como la clase de partes de la clase que contiene elementos. Podemos ver esta clase como la clase cociente de B{\ Displaystyle {\ mathcal {B}}}h{\ Displaystyle h}

Smiqh(B)/R{\ Displaystyle {\ mathsf {Seq}} _ {h} ({\ mathcal {B}}) / {\ mathfrak {R}}},

where es el conjunto de secuencias de elementos de , y where equivale a dos secuencias que son iguales excepto por una permutación de sus elementos. Se tiene Smiqh(B){\ Displaystyle {\ mathsf {Seq}} _ {h} ({\ mathcal {B}})}h{\ Displaystyle h}B{\ Displaystyle {\ mathcal {B}}}R{\ Displaystyle {\ mathfrak {R}}}

|Smiqh(B)|=h!|Smith(B)|{\ Displaystyle | {\ mathsf {Seq}} _ {h} ({\ mathcal {B}}) | = h! | {\ mathsf {Set}} _ {h} ({\ mathcal {B}}) | }.

La clase de las partes de la clase es por definición B{\ Displaystyle {\ mathcal {B}}}

PARA=Smit(B)=⋃h≥0Smith(B){\ displaystyle {\ mathcal {A}} = {\ mathsf {Set}} ({\ mathcal {B}}) = \ bigcup _ {h \ geq 0} {\ mathsf {Set}} _ {h} ({ \ mathcal {B}})},

y la correspondiente serie de generadores exponenciales es

PARA(z)=∑h≥01h!B(z)h=Exp⁡(1-B(z)){\ Displaystyle A (z) = \ sum _ {h \ geq 0} {\ frac {1} {h!}} B (z) ^ {h} = \ exp (1-B (z))}.Ciclo

Definimos la clase

VSyvsh(B){\ Displaystyle {\ mathsf {Cyc}} _ {h} ({\ mathcal {B}})}

como la clase de los ciclos de elementos de la clase . Podemos verlo como el cociente de la clase de secuencias de longitud de elementos por el conjunto de permutaciones circulares de sus elementos. Se tiene h{\ Displaystyle h}B{\ Displaystyle {\ mathcal {B}}}h{\ Displaystyle h}B{\ Displaystyle {\ mathcal {B}}}

|Smiqh(B)|=h|VSyvsh(B)|{\ Displaystyle | {\ mathsf {Seq}} _ {h} ({\ mathcal {B}}) | = h | {\ mathsf {Cyc}} _ {h} ({\ mathcal {B}}) |}.

La clase de los ciclos de la clase es por definición B{\ Displaystyle {\ mathcal {B}}}

PARA=VSyvs(B)=⋃h≥0VSyvsh(B){\ displaystyle {\ mathcal {A}} = {\ mathsf {Cyc}} ({\ mathcal {B}}) = \ bigcup _ {h \ geq 0} {\ mathsf {Cyc}} _ {h} ({ \ mathcal {B}})},

y la correspondiente serie de generadores exponenciales es

PARA(z)=∑h≥01hB(z)h=Iniciar sesión⁡(1-B(z)){\ Displaystyle A (z) = \ sum _ {h \ geq 0} {\ frac {1} {h}} B (z) ^ {h} = \ log (1-B (z))}.

Dos casos particulares son el operador de construcción de ciclos de longitud par, y el de longitud impar, que son respectivamente

⋃h≥0VSyvs2h(B){\ Displaystyle \ bigcup _ {h \ geq 0} {\ mathsf {Cyc}} _ {2h} ({\ mathcal {B}})}y .⋃h≥0VSyvs2h+1(B){\ Displaystyle \ bigcup _ {h \ geq 0} {\ mathsf {Cyc}} _ {2h + 1} ({\ mathcal {B}})}

Sus series generadoras son respectivamente

12Iniciar sesión⁡11-B(z)2{\ Displaystyle {\ frac {1} {2}} \ log {\ frac {1} {1-B (z) ^ {2}}}}y .12Iniciar sesión⁡1+B(z)1-B(z){\ Displaystyle {\ frac {1} {2}} \ log {\ frac {1 + B (z)} {1-B (z)}}}

Ejemplos de

Permutaciones . Una permutación puede verse como un conjunto de ciclos de soporte disjuntos. Esto conduce a la ecuación simbólica

PAG=Smit(VSyvs(Z)){\ Displaystyle {\ mathcal {P}} = {\ mathsf {Set}} ({\ mathsf {Cyc}} ({\ mathcal {Z}}))},

donde es la clase formada por un solo elemento de tamaño 1. La serie generadora exponencial es Z{\ Displaystyle {\ mathcal {Z}}}

PAG(z)=Exp⁡(Iniciar sesión⁡(11-z))=11-z{\ Displaystyle P (z) = \ exp {\ bigl (} \ log {\ bigl (} {\ frac {1} {1-z}} {\ bigr)} {\ bigr)} = {\ frac {1 } {1-z}}}.

Involuciones . Una involución es una permutación tal que . Podemos ver una involución como un conjunto de ciclos de longitud 1 o 2 con soportes disjuntos. Por tanto, la ecuación simbólica es σ{\ Displaystyle \ sigma}σ2=Identificación{\ Displaystyle \ sigma ^ {2} = \ operatorname {Id}}

I=Smit(VSyvs1(Z)+VSyvs2(Z)){\ displaystyle {\ mathcal {I}} = {\ mathsf {Set}} ({\ mathsf {Cyc_ {1}}} ({\ mathcal {Z}}) + {\ mathsf {Cyc_ {2}}} ( {\ mathcal {Z}}))},

y la serie generadora exponencial es . Un cálculo elemental permite obtener la expresión close I(z)=miXpag(z+z2/2){\ Displaystyle I (z) = exp (z + z ^ {2} / 2)}

[zno]I(z)=∑I=0⌈no/2⌉no!I!(no-2I)!2I{\ Displaystyle [z ^ {n}] I (z) = \ sum _ {i = 0} ^ {\ lceil n / 2 \ rceil} {\ frac {n!} {i! (n-2i)! 2 ^ {i}}}}

Disturbios . Una falla es una permutación sin un punto fijo. La definición simbólica es

D=Smit(VSyvsh≥2(Z)){\ Displaystyle {\ mathcal {D}} = {\ mathsf {Set}} ({\ mathsf {Cyc}} _ {h \ geq 2} ({\ mathcal {Z}}))},

y la función del generador exponencial es

D(z)=Exp⁡(z2/2+z3/3+⋯)=Exp⁡(Iniciar sesión⁡(11-z)-z)=mi-z1-z{\ Displaystyle D (z) = \ exp (z ^ {2} / 2 + z ^ {3} / 3 + \ cdots) = \ exp {\ bigl (} \ log {\ bigl (} {\ frac {1 } {1-z}} {\ bigr)} - z {\ bigr)} = {\ frac {e ^ {- z}} {1-z}}}.

Para evaluar el número d_n de perturbaciones de tamaño , observamos que la singularidad de es en . Alrededor de este punto, el desarrollo de es no{\ Displaystyle n}D(z){\ Displaystyle D (z)}z=1{\ Displaystyle z = 1}D(z){\ Displaystyle D (z)}

D(z)∼z→1mi-11-z{\ Displaystyle D (z) \ sim _ {z \ to 1} {\ frac {e ^ {- 1}} {1-z}}}, entonces .Dno=[zno]D(z)∼no!mi{\ Displaystyle d_ {n} = [z ^ {n}] D (z) \ sim {\ frac {n!} {e}}}

Árboles . Un árbol enraizado está formado por una copa y un conjunto de subárboles. Estas son estructuras etiquetadas o no. Para árboles etiquetados, la ecuación simbólica es

T=Z⋆Smit(T){\ Displaystyle {\ mathcal {T}} = {\ mathcal {Z}} \ star {\ mathsf {Set}} ({\ mathcal {T}})},

y la serie exponencial correspondiente es:

T(z)=zExp⁡(T(z)){\ Displaystyle T (z) = z \ exp (T (z))}.

Para un árbol plano enraizado y sin etiquetar, formado por un vértice y una serie de subárboles, la ecuación simbólica es

T=Z×Smiq(T){\ Displaystyle {\ mathcal {T}} = {\ mathcal {Z}} \ times {\ mathsf {Seq}} ({\ mathcal {T}})},

y la serie de generadores ordinarios es:

T(z)=z1-z{\ Displaystyle T (z) = {\ frac {z} {1-z}}}.

Multi-set

La construcción de la clase de conjuntos múltiples o piezas con multiplicidad es similar a la de piezas. En la clase

PARA=METROSmit(B){\ Displaystyle {\ mathcal {A}} = {\ mathsf {MSet}} ({\ mathcal {B}})},

cada elemento de puede aparecer un número arbitrario de veces en un juego. Obtenemos : B{\ Displaystyle {\ mathcal {B}}}

PARA=METROSmit(B)=∏B∈BSmiq({B}).{\ Displaystyle {\ mathcal {A}} = {\ mathsf {MSet}} ({\ mathcal {B}}) = \ prod _ {b \ in {\ mathcal {B}}} {\ mathsf {Seq}} (\ {B \}).}

Esto conduce a la relación (aquí es el número de elementos de tamaño de ): Bno{\ Displaystyle B_ {n}}no{\ Displaystyle n}B{\ Displaystyle {\ mathcal {B}}}

PARA(z)=∏B∈B(1-z|B|)-1=∏no=1∞(1-zno)-Bno=Exp⁡(Iniciar sesión⁡∏no=1∞(1-zno)-Bno)=Exp⁡(∑no=1∞-BnoIniciar sesión⁡(1-zno))=Exp⁡(∑k=1∞B(zk)k),{\ Displaystyle {\ begin {alineado} A (z) & {} = \ prod _ {b \ in {\ mathcal {B}}} (1-z ^ {| b |}) ^ {- 1} = \ prod _ {n = 1} ^ {\ infty} (1-z ^ {n}) ^ {- B_ {n}} \\ & {} = \ exp \ left (\ log \ prod _ {n = 1} ^ {\ infty} (1-z ^ {n}) ^ {- B_ {n}} \ right) = \ exp \ left (\ sum _ {n = 1} ^ {\ infty} -B_ {n} \ log (1-z ^ {n}) \ right) \\ & {} = \ exp \ left (\ sum _ {k = 1} ^ {\ infty} {\ frac {B (z ^ {k})} {k}} \ derecha), \ end {alineado}}}

Una aplicación de ejemplo consta de particiones de números enteros . Primero definimos la clase de enteros positivos, señalada aquí , donde el tamaño de cada entero es su valor I{\ Displaystyle {\ mathcal {I}}}

I=Z×Smiq(Z){\ Displaystyle {\ mathcal {I}} = {\ mathcal {Z}} \ times {\ mathsf {Seq}} ({\ mathcal {Z}})}.

La serie generadora de i es entonces I{\ Displaystyle {\ mathcal {I}}}

I(z)=z1-z.{\ Displaystyle I (z) = {\ frac {z} {1-z}}.}

El conjunto de particiones de enteros es la clase de conjuntos múltiples de enteros positivos. Si lo escribimos , obtenemos la fórmula PAG{\ Displaystyle {\ mathcal {P}}}

PAG=METROSmit(I).{\ Displaystyle {\ mathcal {P}} = {\ mathsf {MSet}} ({\ mathcal {I}}).}

La serie generadora de es PAG{\ Displaystyle {\ mathcal {P}}}

PAG(z)=Exp⁡(I(z)+12I(z2)+13I(z3)+⋯).{\ Displaystyle P (z) = \ exp \ left (I (z) + {\ frac {1} {2}} I (z ^ {2}) + {\ frac {1} {3}} I (z ^ {3}) + \ cdots \ right).}

No existe una fórmula cerrada conocida para esta serie, pero podemos calcular el valor asintótico de sus coeficientes.

Notas y referencias

1. Flajolet y Sedgewick 2008 .
2. Flajolet y Sedgewick 2008 , Cap I, §2.3.
3. Flajolet y Sedgewick 2008 , Teorema VI.2, p.  385.
4. Flajolet y Sedgewick 2008 , Figura VI.5, p.  388.
5. Flajolet y Sedgewick 2008 , Teorema de transferencia, Th. VI.3, p.  390.

(fr) Este artículo está tomado parcial o totalmente del artículo de Wikipedia en inglés titulado "  Analítica combinatoria  " ( consulte la lista de autores ) .

Bibliografía

• 1990  : (en) Herbert Wilf , Generatingfunctionology , Academic Press , 1990, ( ISBN  0-12-751955-6 ) . (leer en línea)
• 1995  : Micha Hofri, Análisis de algoritmos: métodos computacionales y herramientas matemáticas , Oxford University Press (1995).
• 1998  : François Bergeron , Gilbert Labelle y Pierre Leroux , Combinatorial Species and Tree-like Structures , Cambridge University Press, coll.  "Enciclopedia de las Matemáticas y sus Aplicaciones" ( n o  67)1998, 457  p. ( ISBN  978-0-521-57323-8 , leer en línea )- Versión francesa: Teoría de especies y combinatoria de estructuras arbóreas , LaCIM, Montreal (1994).
• 2008  : (en) Philippe Flajolet y Robert Sedgewick , Analytic Combinatorics , Cambridge University Press ,2008( ISBN  0-521-89806-4 , leer en línea )
• 2013 Robin Pemantle y Mark C. Wilson , Combinatoria analítica en varias variables , Cambridge University Press, coll.  "Estudios de Cambridge en Matemáticas Avanzadas" ( n o  140),2013, 392  p. ( ISBN  978-1-107-03157-9 , leer en línea ).
• 2014  : Jérémie Lumbroso y Basile Morcrette, “A Gentle Introduction to Analytic Combinatorics” , en CIMPA Summer School Analysis of Random Structures , An Najah University, Naplouse , Palestina, del 18 al 27 de agosto de 2014 ( leer en línea )
• 2021  : Stephen Melczer, Una invitación a la combinatoria analítica: de una a varias variables , Springer, coll.  "Textos y monografías en computación simbólica",2021, xviii + 418  pág. ( ISBN  978-3-030-67079-5 y 978-3-030-67080-1 , presentación en línea , leer en línea )