Combinatoria analítica

This article needs attention from an expert in Mathematics. Please add a reason or a talk parameter to this template to explain the issue with the article. WikiProject Mathematics may be able to help recruit an expert. (January 2024)

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]}

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]

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 }$

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 .

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

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.

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 }$

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 .

• 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.

Wikilibros tiene un libro sobre el tema: Combinatoria analítica

• 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) .

• 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

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