Teorema de enumeración etiquetada

En matemáticas combinatorias , el teorema de enumeración etiquetado es la contraparte del teorema de enumeración de Pólya para el caso etiquetado, donde tenemos un conjunto de objetos etiquetados dados por una función generadora exponencial (FGE) g ( z ) que se distribuyen en n ranuras y un grupo de permutación G que permuta las ranuras, creando así clases de equivalencia de configuraciones. Hay una operación especial de reetiquetado que reetiqueta los objetos en las ranuras, asignando etiquetas de 1 a k , donde k es el número total de nodos, es decir, la suma del número de nodos de los objetos individuales. La FGE del número de configuraciones diferentes bajo este proceso de reetiquetado viene dada por ${\displaystyle f_{n}(z)}$

${\displaystyle f_{n}(z)={\frac {g(z)^{n}}{|G|}}.}$

En particular, si G es el grupo simétrico de orden n (por lo tanto, | G | =  n !), las funciones se pueden combinar aún más en una única función generadora : ${\displaystyle f_{n}(z)}$

${\displaystyle F(z,t)=\sum _{n=0}^{\infty }f_{n}(z)t^{n}=\sum _{n=0}^{\infty }{\frac {g(z)^{n}}{n!}}t^{n}=e^{g(z)t}}$

que es exponencial con respecto a la variable z y ordinaria con respecto a la variable t .

Suponemos que un objeto de tamaño representado por contiene nodos internos etiquetados, con etiquetas que van de 1 a m . La acción de G sobre las ranuras se simplifica enormemente en comparación con el caso sin etiquetas, porque las etiquetas distinguen los objetos en las ranuras, y las órbitas bajo G tienen todas el mismo tamaño . (La EGF g ( z ) puede no incluir objetos de tamaño cero. Esto se debe a que no se distinguen por etiquetas y, por lo tanto, la presencia de dos o más de dichos objetos crea órbitas cuyo tamaño es menor que ). Como se mencionó, los nodos de los objetos se vuelven a etiquetar cuando se distribuyen en las ranuras. Digamos que un objeto de tamaño va a la primera ranura, un objeto de tamaño a la segunda ranura, y así sucesivamente, y el tamaño total de la configuración es k , de modo que ${\displaystyle \omega }$${\displaystyle |\omega |}$${\displaystyle z^{|\omega |}/|\omega |!}$${\displaystyle |\omega |=m}$${\displaystyle |G|}$${\displaystyle |G|}$${\displaystyle r_{1}}$${\displaystyle r_{2}}$

${\displaystyle r_{1}+r_{2}+\cdots +r_{n}=k.}$

El proceso de reetiquetado funciona de la siguiente manera: elija uno de

${\displaystyle {k \choose r_{1},r_{2},\ldots ,r_{n}}}$

particiones del conjunto de k etiquetas en subconjuntos de tamaño Ahora, vuelva a etiquetar los nodos internos de cada objeto usando las etiquetas del subconjunto respectivo, conservando el orden de las etiquetas. Por ejemplo, si el primer objeto contiene cuatro nodos etiquetados del 1 al 4 y el conjunto de etiquetas elegido para este objeto es {2, 5, 6, 10}, entonces el nodo 1 recibe la etiqueta 2, el nodo 2, la etiqueta 5, el nodo 3, la etiqueta 6 y el nodo 4, la etiqueta 10. De esta manera, las etiquetas en los objetos inducen un etiquetado único usando las etiquetas del subconjunto elegido para el objeto. ${\displaystyle r_{1},r_{2},\ldots r_{n}.}$${\displaystyle [k]}$

De la construcción de reetiquetado se deduce que hay

${\displaystyle {\frac {1}{|G|}}\sum _{r_{1}+r_{2}+\cdots +r_{n}=k}{k \choose r_{1},r_{2},\ldots ,r_{n}}\;r_{1}![z^{r_{1}}]g(z)\;r_{2}![z^{r_{2}}]g(z)\;\cdots \;r_{n}![z^{r_{n}}]g(z)}$

o

${\displaystyle {\frac {k!}{|G|}}\sum _{r_{1}+r_{2}+\cdots +r_{n}=k}[z^{r_{1}}]g(z)[z^{r_{2}}]g(z)\cdots [z^{r_{n}}]g(z)\;=\;{\frac {k!}{|G|}}[z^{k}]g(z)^{n}}$

diferentes configuraciones de tamaño total k . La fórmula se evalúa a un entero porque es cero para k  <  n (recuerde que g no incluye objetos de tamaño cero) y cuando tenemos y el orden de G divide el orden de , que es , por el teorema de Lagrange . La conclusión es que la EGF de las configuraciones etiquetadas está dada por ${\displaystyle [z^{k}]g(z)^{n}}$${\displaystyle k\geq n}$${\displaystyle n!|k!}$${\displaystyle |G|}$${\displaystyle S_{n}}$${\displaystyle n!}$

${\displaystyle f_{n}(z)=\sum _{k\geq 0}\left({\frac {k!}{|G|}}[z^{k}]g(z)^{n}\right){\frac {z^{k}}{k!}}={\frac {1}{|G|}}\sum _{k\geq 0}z^{k}[z^{k}]g(z)^{n}={\frac {g(z)^{n}}{|G|}}.}$

Esta fórmula también podría obtenerse enumerando secuencias, es decir, el caso en que las ranuras no se permutan, y utilizando el argumento anterior sin el factor para demostrar que su función generadora bajo reetiquetado viene dada por . Finalmente, observe que cada secuencia pertenece a una órbita de tamaño , por lo tanto, la función generadora de las órbitas viene dada por${\displaystyle 1/|G|}$${\displaystyle g(z)^{n}}$${\displaystyle |G|}$${\displaystyle g(z)^{n}/|G|.}$

• François Bergeron, Gilbert Labelle, Pierre Leroux, Théorie des espèces et combinatoire desstructures arborescentes , LaCIM, Montreal (1994). Versión en inglés: Combinatorial Species and Tree-like Structures , Cambridge University Press (1998).