Fórmula exponencial

En matemáticas combinatorias , la fórmula exponencial (llamada expansión polimérica en física ) establece que la función generadora exponencial para estructuras en conjuntos finitos es el exponencial de la función generadora exponencial para estructuras conexas. La fórmula exponencial es una versión en serie de potencias de un caso especial de la fórmula de Faà di Bruno .

Enunciado algebraico

He aquí un enunciado puramente algebraico , como primera introducción al uso combinatorio de la fórmula.

Para cualquier serie de potencias formales de la forma tenemos donde y el índice recorre todas las particiones del conjunto . (Cuando el producto está vacío y por definición es igual a ). $${\displaystyle f(x)=a_{1}x+{a_{2} \over 2}x^{2}+{a_{3} \over 6}x^{3}+\cdots +{a_{n} \over n!}x^{n}+\cdots \,}$$ $${\displaystyle \exp f(x)=e^{f(x)}=\sum _{n=0}^{\infty }{b_{n} \over n!}x^{n},\,}$$ $${\displaystyle b_{n}=\sum _{\pi =\left\{\,S_{1},\,\dots ,\,S_{k}\,\right\}}a_{\left|S_{1}\right|}\cdots a_{\left|S_{k}\right|},}$$ ${\displaystyle \pi }$ ${\displaystyle \{S_{1},\ldots ,S_{k}\}}$ ${\displaystyle \{1,\ldots ,n\}}$ ${\displaystyle k=0,}$ ${\displaystyle 1}$

Fórmula en otras expresiones

La fórmula se puede escribir de la siguiente forma: y por tanto donde es el ésimo polinomio de Bell completo . $${\displaystyle b_{n}=B_{n}(a_{1},a_{2},\dots ,a_{n}),}$$ $${\displaystyle \exp \left(\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}\right)=\sum _{n=0}^{\infty }{B_{n}(a_{1},\dots ,a_{n}) \over n!}x^{n},}$$ ${\displaystyle B_{n}(a_{1},\ldots ,a_{n})}$ ${\displaystyle n}$

Alternativamente, la fórmula exponencial también se puede escribir utilizando el índice de ciclo del grupo simétrico , de la siguiente manera: donde representa el polinomio de índice de ciclo para el grupo simétrico , definido como: y denota el número de ciclos de de tamaño . Esto es una consecuencia de la relación general entre y los polinomios de Bell : $${\displaystyle \exp \left(\sum _{n=1}^{\infty }a_{n}{x^{n} \over n}\right)=\sum _{n=0}^{\infty }Z_{n}(a_{1},\dots ,a_{n})x^{n},}$$ ${\displaystyle Z_{n}}$ ${\displaystyle S_{n}}$ $${\displaystyle Z_{n}(x_{1},\cdots ,x_{n})={\frac {1}{n!}}\sum _{\sigma \in S_{n}}x_{1}^{\sigma _{1}}\cdots x_{n}^{\sigma _{n}}}$$ ${\displaystyle \sigma _{j}}$ ${\displaystyle \sigma }$ ${\displaystyle j\in \{1,\cdots ,n\}}$ ${\displaystyle Z_{n}}$ $${\displaystyle Z_{n}(x_{1},\dots ,x_{n})={1 \over n!}B_{n}(0!\,x_{1},1!\,x_{2},\dots ,(n-1)!\,x_{n}).}$$

Interpretación combinatoria

En aplicaciones combinatorias, los números cuentan la cantidad de algún tipo de estructura "conectada" en un conjunto de puntos y los números cuentan la cantidad de estructuras (posiblemente desconectadas). Los números cuentan la cantidad de clases de isomorfismo de estructuras en puntos, donde cada estructura se pondera por el recíproco de su grupo de automorfismo , y los números cuentan las clases de isomorfismo de estructuras conectadas de la misma manera. ${\displaystyle a_{n}}$ ${\displaystyle n}$ ${\displaystyle b_{n}}$ ${\displaystyle b_{n}/n!}$ ${\displaystyle n}$ ${\displaystyle a_{n}/n!}$

Ejemplos

• ${\displaystyle b_{3}=B_{3}(a_{1},a_{2},a_{3})=a_{3}+3a_{2}a_{1}+a_{1}^{3},}$porque hay una partición del conjunto que tiene un solo bloque de tamaño , hay tres particiones de que lo dividen en un bloque de tamaño y un bloque de tamaño , y hay una partición de que lo divide en tres bloques de tamaño . Esto también se deduce de , ya que uno puede escribir el grupo como , utilizando la notación cíclica para permutaciones . ${\displaystyle \{1,2,3\}}$ ${\displaystyle 3}$ ${\displaystyle \{1,2,3\}}$ ${\displaystyle 2}$ ${\displaystyle 1}$ ${\displaystyle \{1,2,3\}}$ ${\displaystyle 1}$ ${\displaystyle Z_{3}(a_{1},a_{2},a_{3})={1 \over 6}(2a_{3}+3a_{1}a_{2}+a_{1}^{3})={1 \over 6}B_{3}(a_{1},a_{2},2a_{3})}$ ${\displaystyle S_{3}}$ ${\displaystyle S_{3}=\{(1)(2)(3),(1)(23),(2)(13),(3)(12),(123),(132)\}}$
• Si es el número de gráficos cuyos vértices son un conjunto de puntos dado , entonces es el número de gráficos conexos cuyos vértices son un conjunto de puntos dado. ${\displaystyle b_{n}=2^{n(n-1)/2}}$ ${\displaystyle n}$ ${\displaystyle a_{n}}$ ${\displaystyle n}$
• Existen numerosas variaciones del ejemplo anterior donde el gráfico tiene ciertas propiedades: por ejemplo, si cuenta gráficos sin ciclos, entonces cuenta árboles (gráficos conexos sin ciclos). ${\displaystyle b_{n}}$ ${\displaystyle a_{n}}$
• Si cuenta los gráficos dirigidos cuyos bordes (en lugar de vértices) son un conjunto de puntos dado, entonces cuenta los gráficos dirigidos conexos con este conjunto de bordes. ${\displaystyle b_{n}}$ ${\displaystyle n}$ ${\displaystyle a_{n}}$
• En la teoría cuántica de campos y en la mecánica estadística , las funciones de partición , o más generalmente funciones de correlación , se dan mediante una suma formal sobre diagramas de Feynman . La fórmula exponencial muestra que puede escribirse como una suma sobre diagramas de Feynman conexos, en términos de funciones de correlación conexas . ${\displaystyle Z}$ ${\displaystyle \ln(Z)}$

Véase también

• Sobreyección de espacios de Fréchet  – Caracterización de la sobreyección

Referencias

• Stanley, Richard P. (1999), Combinatoria enumerativa. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press , ISBN 978-0-521-56069-6, MR  1676282, ISBN 978-0-521-78987-5 Capítulo 5 página 3