Método simbólico (combinatoria)

Este operador corresponde a la clase

${\displaystyle L={\frac {1}{1-X}}=1+X+X^{2}+X^{3}+\cdots }$

y representa secuencias, es decir, las ranuras no se permutan y hay exactamente una secuencia vacía. Tenemos

${\displaystyle F(z)=1+\sum _{n\geq 1}Z(1)(f(z),f(z^{2}),\ldots ,f(z^{n}))=1+\sum _{n\geq 1}f(z)^{n}={\frac {1}{1-f(z)}}}$

y

${\displaystyle G(z)=1+\sum _{n\geq 1}g(z)^{n}={\frac {1}{1-g(z)}}.}$

Este operador corresponde a la clase

${\displaystyle C=C_{1}+C_{2}+C_{3}+\cdots }$

es decir, ciclos que contienen al menos un objeto. Tenemos

${\displaystyle F(z)=\sum _{n\geq 1}Z(C_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))=\sum _{n\geq 1}{\frac {1}{n}}\sum _{d\mid n}\varphi (d)f(z^{d})^{n/d}}$

o

${\displaystyle F(z)=\sum _{k\geq 1}\varphi (k)\sum _{m\geq 1}{\frac {1}{km}}f(z^{k})^{m}=\sum _{k\geq 1}{\frac {\varphi (k)}{k}}\log {\frac {1}{1-f(z^{k})}}}$

y

${\displaystyle G(z)=\sum _{n\geq 1}\left({\frac {1}{|C_{n}|}}\right)g(z)^{n}=\log {\frac {1}{1-g(z)}}.}$

Este operador, junto con el operador de conjuntos SET y sus restricciones a grados específicos, se utilizan para calcular estadísticas de permutación aleatoria . Este operador tiene dos restricciones útiles: a ciclos pares e impares.

El operador de ciclo par etiquetado CYC _even es

${\displaystyle C_{2}+C_{4}+C_{6}+\cdots }$

lo cual produce

${\displaystyle G(z)=\sum _{n\geq 1}\left({\frac {1}{|C_{2n}|}}\right)g(z)^{2n}={\frac {1}{2}}\log {\frac {1}{1-g(z)^{2}}}.}$

Esto implica que el operador de ciclo impar etiquetado CYC _{es impar .}

${\displaystyle C_{1}+C_{3}+C_{5}+\cdots }$

es dado por

${\displaystyle G(z)=\log {\frac {1}{1-g(z)}}-{\frac {1}{2}}\log {\frac {1}{1-g(z)^{2}}}={\frac {1}{2}}\log {\frac {1+g(z)}{1-g(z)}}.}$

La serie es

${\displaystyle E=1+E_{1}+E_{2}+E_{3}+\cdots }$

es decir, el grupo simétrico${\displaystyle S_{n}=E_{n}}$Se aplica a la enésima ranura. Esto crea multiconjuntos en el caso sin etiquetar y conjuntos en el caso con etiquetar (no hay multiconjuntos en el caso con etiquetar porque las etiquetas distinguen múltiples instancias del mismo objeto del conjunto que se coloca en diferentes ranuras). Incluimos el conjunto vacío tanto en el caso con etiquetar como en el caso sin etiquetar.

El caso sin etiquetar se realiza utilizando la función

${\displaystyle M(f(z),y)=\sum _{n\geq 0}y^{n}Z(E_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))}$

de modo que

${\displaystyle {\mathfrak {M}}(f(z))=M(f(z),1).}$

Evaluar${\displaystyle M(f(z),1)}$obtenemos

${\displaystyle F(z)=\exp \left(\sum _{\ell \geq 1}{\frac {f(z^{\ell })}{\ell }}\right).}$

Para el caso etiquetado tenemos

${\displaystyle G(z)=1+\sum _{n\geq 1}\left({\frac {1}{|S_{n}|}}\right)g(z)^{n}=\sum _{n\geq 0}{\frac {g(z)^{n}}{n!}}=\exp g(z).}$

En el caso etiquetado denotamos el operador por SET , y en el caso no etiquetado, por MSET . Esto se debe a que en el caso etiquetado no hay multiconjuntos (las etiquetas distinguen los constituyentes de una clase combinatoria compuesta), mientras que en el caso no etiquetado hay multiconjuntos y conjuntos, siendo estos últimos dados por

${\displaystyle F(z)=\exp \left(\sum _{\ell \geq 1}(-1)^{\ell -1}{\frac {f(z^{\ell })}{\ell }}\right).}$

El producto de dos clases combinatorias${\displaystyle {\mathcal {A}}}$y${\displaystyle {\mathcal {B}}}$se especifica definiendo el tamaño de un par ordenado como la suma de los tamaños de los elementos del par. Por lo tanto, tenemos para${\displaystyle a\in {\mathcal {A}}}$y${\displaystyle b\in {\mathcal {B}}}$,${\displaystyle |(a,b)|=|a|+|b|}$. Esta debería ser una definición bastante intuitiva. Ahora observamos que el número de elementos en${\displaystyle {\mathcal {A}}\times {\mathcal {B}}}$de tamaño n es

${\displaystyle \sum _{k=0}^{n}A_{k}B_{n-k}.}$

Utilizando la definición de la OGF y algo de álgebra elemental, podemos demostrar que

${\displaystyle {\mathcal {A}}={\mathcal {B}}\times {\mathcal {C}}}$implica${\displaystyle A(z)=B(z)\cdot C(z).}$

La construcción de secuencia , denotada por${\displaystyle {\mathcal {A}}={\mathfrak {G}}\{{\mathcal {B}}\}}$se define como

${\displaystyle {\mathfrak {G}}\{{\mathcal {B}}\}={\mathcal {E}}+{\mathcal {B}}+({\mathcal {B}}\times {\mathcal {B}})+({\mathcal {B}}\times {\mathcal {B}}\times {\mathcal {B}})+\cdots .}$

En otras palabras, una secuencia es el elemento neutro, o un elemento de${\displaystyle {\mathcal {B}}}$, o un par ordenado, una terna ordenada, etc. Esto conduce a la relación

${\displaystyle A(z)=1+B(z)+B(z)^{2}+B(z)^{3}+\cdots ={\frac {1}{1-B(z)}}.}$

La construcción de conjuntos (o conjuntos potencia ) , denotada por${\displaystyle {\mathcal {A}}={\mathfrak {P}}\{{\mathcal {B}}\}}$se define como

${\displaystyle {\mathfrak {P}}\{{\mathcal {B}}\}=\prod _{\beta \in {\mathcal {B}}}({\mathcal {E}}+\{\beta \}),}$

lo que lleva a la relación

${\displaystyle {\begin{aligned}A(z)&{}=\prod _{\beta \in {\mathcal {B}}}(1+z^{|\beta |})\\&{}=\prod _{n=1}^{\infty }(1+z^{n})^{B_{n}}\\&{}=\exp \left(\ln \prod _{n=1}^{\infty }(1+z^{n})^{B_{n}}\right)\\&{}=\exp \left(\sum _{n=1}^{\infty }B_{n}\ln(1+z^{n})\right)\\&{}=\exp \left(\sum _{n=1}^{\infty }B_{n}\cdot \sum _{k=1}^{\infty }{\frac {(-1)^{k-1}z^{nk}}{k}}\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}}{k}}\cdot \sum _{n=1}^{\infty }B_{n}z^{nk}\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}B(z^{k})}{k}}\right),\end{aligned}}}$

donde la expansión

${\displaystyle \ln(1+u)=\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}u^{k}}{k}}}$

Se utilizó para pasar de la línea 4 a la línea 5.

La construcción de multiconjunto , denotada${\displaystyle {\mathcal {A}}={\mathfrak {M}}\{{\mathcal {B}}\}}$es una generalización de la construcción de conjuntos. En la construcción de conjuntos, cada elemento puede aparecer cero o una vez. En un multiconjunto, cada elemento puede aparecer un número arbitrario de veces. Por lo tanto,

${\displaystyle {\mathfrak {M}}\{{\mathcal {B}}\}=\prod _{\beta \in {\mathcal {B}}}{\mathfrak {G}}\{\beta \}.}$

Esto conduce a la relación

${\displaystyle {\begin{aligned}A(z)&{}=\prod _{\beta \in {\mathcal {B}}}(1-z^{|\beta |})^{-1}\\&{}=\prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\\&{}=\exp \left(\ln \prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\right)\\&{}=\exp \left(\sum _{n=1}^{\infty }-B_{n}\ln(1-z^{n})\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {B(z^{k})}{k}}\right),\end{aligned}}}$

donde, de forma similar a la construcción de conjuntos anterior, ampliamos${\displaystyle \ln(1-z^{n})}$, intercambia las sumas y sustituye por la OGF de${\displaystyle {\mathcal {B}}}$.

Otras construcciones elementales importantes son:

• la construcción del ciclo (${\displaystyle {\mathfrak {C}}\{{\mathcal {B}}\}}$), como secuencias excepto que las rotaciones cíclicas no se consideran distintas
• señalando (${\displaystyle \Theta {\mathcal {B}}}$), en el que cada miembro de B se ve aumentado por un puntero neutro (de tamaño cero) a uno de sus átomos
• sustitución (${\displaystyle {\mathcal {B}}\circ {\mathcal {C}}}$) , en la que cada átomo de un miembro de B es reemplazado por un miembro de C.

Las deducciones para estas construcciones son demasiado complicadas para mostrarlas aquí. Aquí están los resultados:

Se pueden construir muchas clases combinatorias utilizando estas construcciones elementales. Por ejemplo, la clase de árboles planos (es decir, árboles incrustados en el plano, de modo que el orden de los subárboles importa) se especifica mediante la relación recursiva.

${\displaystyle {\mathcal {G}}={\mathcal {Z}}\times \operatorname {SEQ} \{{\mathcal {G}}\}.}$

En otras palabras, un árbol es un nodo raíz de tamaño 1 y una secuencia de subárboles. Esto da como resultado

${\displaystyle G(z)={\frac {z}{1-G(z)}}}$

resolvemos para G ( z ) multiplicando${\displaystyle 1-G(z)}$Llegar

${\displaystyle G(z)-G(z)^{2}=z}$

restando z y resolviendo para G(z) usando la fórmula cuadrática se obtiene

${\displaystyle G(z)={\frac {1-{\sqrt {1-4z}}}{2}}.}$

Otro ejemplo (y un problema clásico de combinatoria) son las particiones de enteros . Primero, definamos la clase de enteros positivos.${\displaystyle {\mathcal {I}}}$donde el tamaño de cada entero es su valor:

${\displaystyle {\mathcal {I}}={\mathcal {Z}}\times \operatorname {SEQ} \{{\mathcal {Z}}\}}$

El OGF de${\displaystyle {\mathcal {I}}}$es entonces

${\displaystyle I(z)={\frac {z}{1-z}}.}$

Ahora, definamos el conjunto de particiones.${\displaystyle {\mathcal {P}}}$como

${\displaystyle {\mathcal {P}}=\operatorname {MSET} \{{\mathcal {I}}\}.}$

El OGF de${\displaystyle {\mathcal {P}}}$es

${\displaystyle P(z)=\exp \left(I(z)+{\frac {1}{2}}I(z^{2})+{\frac {1}{3}}I(z^{3})+\cdots \right).}$

Lamentablemente, no hay un formulario cerrado para${\displaystyle P(z)}$Sin embargo, la OGF se puede utilizar para derivar una relación de recurrencia o, utilizando métodos más avanzados de combinatoria analítica, calcular el comportamiento asintótico de la secuencia de conteo.

Las construcciones elementales mencionadas anteriormente nos permiten definir la noción de especificación . Esta especificación nos permite utilizar un conjunto de ecuaciones recursivas, con múltiples clases combinatorias.

Formalmente, una especificación para un conjunto de clases combinatorias${\displaystyle ({\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r})}$es un conjunto de${\displaystyle r}$ecuaciones${\displaystyle {\mathcal {A}}_{i}=\Phi _{i}({\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r})}$, dónde${\displaystyle \Phi _{i}}$es una expresión, cuyos átomos son${\displaystyle {\mathcal {E}},{\mathcal {Z}}}$y el${\displaystyle {\mathcal {A}}_{i}}$de, y cuyos operadores son las construcciones elementales enumeradas anteriormente.

Se dice que una clase de estructuras combinatorias es construible o especificable cuando admite una especificación.

Por ejemplo, el conjunto de árboles cuya profundidad de hojas es par (respectivamente, impar) se puede definir utilizando la especificación con dos clases.${\displaystyle {\mathcal {A}}_{\text{even}}}$y${\displaystyle {\mathcal {A}}_{\text{odd}}}$Esas clases deben satisfacer la ecuación.${\displaystyle {\mathcal {A}}_{\text{odd}}={\mathcal {Z}}\times \operatorname {Seq} _{\geq 1}{\mathcal {A}}_{\text{even}}}$y${\displaystyle {\mathcal {A}}_{\text{even}}={\mathcal {Z}}\times \operatorname {Seq} {\mathcal {A}}_{\text{odd}}}$.

Para estructuras etiquetadas, debemos usar una definición de producto diferente a la de las estructuras no etiquetadas. De hecho, si simplemente usáramos el producto cartesiano, las estructuras resultantes ni siquiera estarían bien etiquetadas. En cambio, usamos el llamado producto etiquetado , denotado${\displaystyle {\mathcal {A}}\star {\mathcal {B}}.}$

Para un par${\displaystyle \beta \in {\mathcal {B}}}$y${\displaystyle \gamma \in {\mathcal {C}}}$, deseamos combinar las dos estructuras en una sola estructura. Para que el resultado esté bien etiquetado, esto requiere un reetiquetado de algunos de los átomos en${\displaystyle \beta }$y${\displaystyle \gamma }$Nos centraremos en los reetiquetados que sean consistentes con el orden de las etiquetas originales. Cabe destacar que existen múltiples maneras de realizar el reetiquetado; por lo tanto, cada par de miembros determina no un único miembro en el producto, sino un conjunto de nuevos miembros. Los detalles de esta construcción se encuentran en la página del teorema de enumeración etiquetada .

Para facilitar este desarrollo, definamos una función,${\displaystyle \rho }$, que toma como argumento un objeto (posiblemente débilmente) etiquetado${\displaystyle \alpha }$y vuelve a etiquetar sus átomos de manera consistente con el orden, de modo que${\displaystyle \rho (\alpha )}$está bien etiquetado. A continuación, definimos el producto etiquetado para dos objetos.${\displaystyle \alpha }$y${\displaystyle \beta }$como

${\displaystyle \alpha \star \beta =\{(\alpha ',\beta '):(\alpha ',\beta '){\text{ is well-labelled, }}\rho (\alpha ')=\alpha ,\rho (\beta ')=\beta \}.}$

Finalmente, el producto etiquetado de dos clases${\displaystyle {\mathcal {A}}}$y${\displaystyle {\mathcal {B}}}$es

${\displaystyle {\mathcal {A}}\star {\mathcal {B}}=\bigcup _{\alpha \in {\mathcal {A}},\beta \in {\mathcal {B}}}(\alpha \star \beta ).}$

La EGF se puede derivar observando que para objetos de tamaño${\displaystyle k}$y${\displaystyle n-k}$, hay${\displaystyle {n \choose k}}$formas de realizar el reetiquetado. Por lo tanto, el número total de objetos de tamaño${\displaystyle n}$es

${\displaystyle \sum _{k=0}^{n}{n \choose k}A_{k}B_{n-k}.}$

Esta relación de convolución binomial para los términos es equivalente a multiplicar las EGF,

${\displaystyle A(z)\cdot B(z).}$

La construcción de la secuencia${\displaystyle {\mathcal {A}}={\mathfrak {G}}\{{\mathcal {B}}\}}$se define de forma similar al caso sin etiquetar:

${\displaystyle {\mathfrak {G}}\{{\mathcal {B}}\}={\mathcal {E}}+{\mathcal {B}}+({\mathcal {B}}\star {\mathcal {B}})+({\mathcal {B}}\star {\mathcal {B}}\star {\mathcal {B}})+\cdots }$

y de nuevo, como se indicó anteriormente,

${\displaystyle A(z)={\frac {1}{1-B(z)}}}$

En estructuras etiquetadas, un conjunto de${\displaystyle k}$los elementos corresponden exactamente${\displaystyle k!}$secuencias. Esto es diferente del caso sin etiquetar, donde algunas de las permutaciones pueden coincidir. Por lo tanto, para${\displaystyle {\mathcal {A}}={\mathfrak {P}}\{{\mathcal {B}}\}}$, tenemos

${\displaystyle A(z)=\sum _{k=0}^{\infty }{\frac {B(z)^{k}}{k!}}=\exp(B(z))}$

Los ciclos también son más fáciles que en el caso sin etiquetar. Un ciclo de longitud${\displaystyle k}$corresponde a${\displaystyle k}$secuencias distintas. Por lo tanto, para${\displaystyle {\mathcal {A}}={\mathfrak {C}}\{{\mathcal {B}}\}}$, tenemos

${\displaystyle A(z)=\sum _{k=0}^{\infty }{\frac {B(z)^{k}}{k}}=\ln \left({\frac {1}{1-B(z)}}\right).}$

En estructuras etiquetadas, el producto min-boxed${\displaystyle {\mathcal {A}}_{\min }={\mathcal {B}}^{\square }\star {\mathcal {C}}}$es una variación del producto original que requiere el elemento de${\displaystyle {\mathcal {B}}}$en el producto con la etiqueta mínima. De manera similar, también podemos definir un producto max-boxed, denotado por${\displaystyle {\mathcal {A}}_{\max }={\mathcal {B}}^{\blacksquare }\star {\mathcal {C}}}$, de la misma manera. Entonces tenemos,

${\displaystyle A_{\min }(z)=A_{\max }(z)=\int _{0}^{z}B'(t)C(t)\,dt.}$

o equivalentemente,

${\displaystyle A_{\min }'(t)=A_{\max }'(t)=B'(t)C(t).}$

Un árbol de Cayley creciente es un árbol no plano y enraizado con etiquetas, cuyas etiquetas a lo largo de cualquier rama que parta de la raíz forman una secuencia creciente. Entonces, sea${\displaystyle {\mathcal {L}}}$ser la clase de tales árboles. La especificación recursiva es ahora${\displaystyle {\mathcal {L}}={\mathcal {Z}}^{\square }\star \operatorname {SET} ({\mathcal {L}}).}$

Los operadores CYC _even , CYC _odd , SET _even y SET _odd representan ciclos de longitud par e impar, y conjuntos de cardinalidad par e impar.

Los números de Stirling de segundo tipo pueden derivarse y analizarse utilizando la descomposición estructural.

${\displaystyle \operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})).}$

La descomposición

${\displaystyle \operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}}))}$

Se utiliza para estudiar los números de Stirling sin signo de primera especie y en la derivación de la estadística de permutaciones aleatorias . Un análisis detallado de las funciones generadoras exponenciales asociadas a los números de Stirling dentro de la combinatoria simbólica se puede encontrar en la página sobre números de Stirling y funciones generadoras exponenciales en combinatoria simbólica .