Combinatoria analítica

La combinatoria analítica utiliza técnicas del análisis complejo para resolver problemas de combinatoria enumerativa , específicamente para encontrar estimaciones asintóticas para los coeficientes de funciones generadoras . ^{[1] [2] [3]}

Historia

Uno de los primeros usos de técnicas analíticas para un problema de enumeración provino del trabajo de Srinivasa Ramanujan y GH Hardy sobre particiones de números enteros , ^{[4] [5]} a partir de 1918, primero utilizando un teorema de Tauber y luego el método del círculo . ^[6]

El artículo de Walter Hayman de 1956 "Una generalización de la fórmula de Stirling" se considera uno de los primeros ejemplos del método del punto de silla. ^{[7] [8] [9]}

En 1990, Philippe Flajolet y Andrew Odlyzko desarrollaron la teoría del análisis de singularidad. ^[10]

En 2009, Philippe Flajolet y Robert Sedgewick escribieron el libro Combinatoria analítica , que presenta la combinatoria analítica con su punto de vista y notación.

Algunos de los primeros trabajos sobre funciones generadoras multivariadas comenzaron en la década de 1970 utilizando métodos probabilísticos. ^{[11] [12]}

El desarrollo de otras técnicas multivariadas comenzó a principios de la década de 2000. ^[13]

Técnicas

Funciones meromórficas

Si es una función meromórfica y su polo es más cercano al origen con orden , entonces ^[14] ${\displaystyle h(z)={\frac {f(z)}{g(z)}}}$ ${\displaystyle a}$ ${\displaystyle m}$

${\displaystyle [z^{n}]h(z)\sim {\frac {(-1)^{m}mf(a)}{a^{m}g^{(m)}(a)}}\left({\frac {1}{a}}\right)^{n}n^{m-1}\quad }$como ${\displaystyle n\to \infty }$

Teorema de Tauber

Si

${\displaystyle f(z)\sim {\frac {1}{(1-z)^{\sigma }}}L({\frac {1}{1-z}})\quad }$como ${\displaystyle z\to 1}$

donde y es una función que varía lentamente , entonces ^[15] ${\displaystyle \sigma >0}$ ${\displaystyle L}$

${\displaystyle [z^{n}]f(z)\sim {\frac {n^{\sigma -1}}{\Gamma (\sigma )}}L(n)\quad }$como ${\displaystyle n\to \infty }$

Véase también el teorema tauberiano de Hardy-Littlewood .

Método del círculo

Para generar funciones con logaritmos o raíces , que tienen singularidades de rama . ^[16]

El método de Darboux

Si tenemos una función donde y tiene un radio de convergencia mayor que y una expansión de Taylor cercana a 1 de , entonces ^[17] ${\displaystyle (1-z)^{\beta }f(z)}$ ${\displaystyle \beta \notin \{0,1,2,\ldots \}}$ ${\displaystyle f(z)}$ ${\displaystyle 1}$ ${\displaystyle \sum _{j\geq 0}f_{j}(1-z)^{j}}$

${\displaystyle [z^{n}](1-z)^{\beta }f(z)=\sum _{j=0}^{m}f_{j}{\frac {n^{-\beta -j-1}}{\Gamma (-\beta -j)}}+O(n^{-m-\beta -2})}$

Véase Szegő (1975) para un teorema similar que trata sobre singularidades múltiples.

Análisis de singularidad

Si tiene una singularidad en y ${\displaystyle f(z)}$ ${\displaystyle \zeta }$

${\displaystyle f(z)\sim \left(1-{\frac {z}{\zeta }}\right)^{\alpha }\left({\frac {1}{\frac {z}{\zeta }}}\log {\frac {1}{1-{\frac {z}{\zeta }}}}\right)^{\gamma }\left({\frac {1}{\frac {z}{\zeta }}}\log \left({\frac {1}{\frac {z}{\zeta }}}\log {\frac {1}{1-{\frac {z}{\zeta }}}}\right)\right)^{\delta }\quad }$como ${\displaystyle z\to \zeta }$

donde entonces ^[18] ${\displaystyle \alpha \notin \{0,1,2,\cdots \},\gamma ,\delta \notin \{1,2,\cdots \}}$

${\displaystyle [z^{n}]f(z)\sim \zeta ^{-n}{\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }\quad }$como ${\displaystyle n\to \infty }$

Método del punto de silla

Para generar funciones que incluyen funciones completas que no tienen singularidades. ^{[19] [20]}

Intuitivamente, la mayor contribución a la integral del contorno está alrededor del punto de silla y la estimación cerca del punto de silla nos da una estimación para todo el contorno.

Si es una función admisible, ^[21] entonces ^{[22] [23]} ${\displaystyle F(z)}$

${\displaystyle [z^{n}]F(z)\sim {\frac {F(\zeta )}{\zeta ^{n+1}{\sqrt {2\pi f^{''}(\zeta )}}}}\quad }$como ${\displaystyle n\to \infty }$

dónde . ${\displaystyle F^{'}(\zeta )=0}$

Véase también el método del descenso más pronunciado .

Notas

1. Melczer 2021, págs. vii y ix.
2. Pemantle y Wilson 2013, págs.xi.
3. Flajolet y Sedgewick 2009, págs. ix.
4. Melczer 2021, págs. vii.
5. Pemantle y Wilson 2013, págs.62-63.
6. Pemantle y Wilson 2013, págs.62.
7. Pemantle y Wilson 2013, págs.63.
8. Wilf 2006, págs. 197.
9. Flajolet y Sedgewick 2009, págs. 607.
10. Flajolet y Sedgewick 2009, págs. 438.
11. Melczer 2021, págs. 13.
12. Flajolet y Sedgewick 2009, págs. 650 y 717.
13. Melczer 2021, págs. 13-14.
14. Sedgewick 4, págs. 59
15. Flajolet y Sedgewick 2009, págs. 435. Hardy 1949, págs. 166. Utilizo la forma en que lo expresan Flajolet y Sedgewick.
16. Pemantle y Wilson 2013, págs. 55-56.
17. Wilf 2006, págs. 194.
18. Flajolet y Sedgewick 2009, págs. 393.
19. Wilf 2006, págs. 196.
20. Flajolet y Sedgewick 2009, págs. 542.
21. Véase Flajolet y Sedgewick 2009, págs. 565 o Wilf 2006, págs. 199.
22. Flajolet y Sedgewick 2009, págs. 553.
23. Sedgewick 8, págs. 25.

Referencias

• Flajolet, Philippe; Sedgewick, Robert (2009). Combinatoria analítica (PDF) . Cambridge University Press.
• Hardy, GH (1949). Serie Divergente (1.ª ed.). Oxford University Press.
• Melczer, Stephen (2021). Una invitación a la combinatoria analítica: de una a varias variables (PDF) . Springer Textos y monografías sobre computación simbólica.
• Pemantle, Robin; Wilson, Mark C. (2013). Combinatoria analítica en varias variables (PDF) . Cambridge University Press.
• Sedgewick, Robert. "4. Análisis complejo, asintótica racional y meromórfica" (PDF) . Consultado el 4 de noviembre de 2023 .
• Sedgewick, Robert. "8. Asintótica del punto de silla" (PDF) . Consultado el 4 de noviembre de 2023 .
• Szegő, Gabor (1975). Polinomios ortogonales (4ª ed.). Sociedad Matemática Americana.
• Wilf, Herbert S. (2006). Función generadora (PDF) (3.ª ed.). AK Peters, Ltd.

A partir del 4 de noviembre de 2023, este artículo se deriva total o parcialmente de Wikilibros . El titular de los derechos de autor ha autorizado el contenido de manera que permita su reutilización bajo CC BY-SA 3.0 y GFDL . Se deben respetar todos los términos pertinentes.

Lectura adicional

• De Bruijn, NG (1981). Métodos asintóticos en análisis . Publicaciones de Dover.
• Flajolet, Philippe; Odlyzko, Andrew (1990). "Análisis de singularidades de funciones generadoras" (PDF) . Revista SIAM de Matemáticas Discretas . 1990 (3).
• Mishna, Marni (2020). Combinatoria analítica: un enfoque multidimensional . Taylor & Francis Group, LLC.
• Pemantle, Robin; Wilson, Mark C.; Melczer, Stephen (2024). Combinatoria analítica en varias variables (PDF) (2.ª ed.). Cambridge University Press.
• Sedgewick, Robert. "6. Análisis de singularidad" (PDF) .

Enlaces externos

• Curso online de Combinatoria Analítica
• Curso en línea Introducción al análisis de algoritmos
• Proyectos de Combinatoria Analítica en Varias Variables
• Una invitación a la combinatoria analítica

Véase también

• Método simbólico (combinatoria)
• Combinatoria analítica (libro)