Teorema de enumeración etiquetado

Contraparte del teorema de enumeración de Pólya para el caso etiquetado

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. Existe 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 está 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 ademá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 .

El proceso de reetiquetado

Un conjunto de ciclos que se vuelven a etiquetar para formar una permutación. (Hay tres ranuras y .) ${\displaystyle G=S_{3}}$

Suponemos que un objeto de tamaño representado por contiene nodos internos etiquetados, con etiquetas que van desde 1 hasta m . La acción de G en 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 . (El 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 en la primera ranura, un objeto de tamaño en 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 utilizando 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 utilizando las etiquetas del subconjunto de elegido para el objeto. ${\displaystyle r_{1},r_{2},\ldots r_{n}.}$ ${\displaystyle [k]}$

Prueba del teorema

De la construcción del re-etiquetado 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 como 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 se puede obtener enumerando secuencias, es decir, el caso en el que no se permutan las ranuras, y utilizando el argumento anterior sin el factor para mostrar que su función generadora bajo reetiquetado está dada por . Finalmente, observe que cada secuencia pertenece a una órbita de tamaño , por lo tanto, la función generadora de las órbitas está dada por ${\displaystyle 1/|G|}$ ${\displaystyle g(z)^{n}}$ ${\displaystyle |G|}$ ${\displaystyle g(z)^{n}/|G|.}$

Referencias

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