Método simbólico (combinatoria)

En combinatoria , el método simbólico es una técnica para contar objetos combinatorios . Utiliza la estructura interna de los objetos para derivar fórmulas para sus funciones generadoras . El método se asocia principalmente con Philippe Flajolet y se detalla en la Parte A de su libro con Robert Sedgewick , Analytic Combinatorics , mientras que el resto del libro explica cómo utilizar el análisis complejo para obtener resultados asintóticos y probabilísticos sobre las funciones generadoras correspondientes.

Durante dos siglos, las funciones generadoras fueron apareciendo a través de las recurrencias correspondientes en sus coeficientes (como se puede ver en los trabajos seminales de Bernoulli , Euler , Arthur Cayley , Schröder , Ramanujan , Riordan , Knuth , Comtet  [fr] , etc.). Luego, lentamente, se comprendió que las funciones generadoras capturaban muchas otras facetas de los objetos combinatorios discretos iniciales, y que esto se podía hacer de una manera formal más directa: La naturaleza recursiva de algunas estructuras combinatorias se traduce, a través de algunos isomorfismos, en identidades notables en las funciones generadoras correspondientes. Siguiendo los trabajos de Pólya , se hicieron más avances en este espíritu en la década de 1970 con usos genéricos de lenguajes para especificar clases combinatorias y sus funciones generadoras, como se encuentra en los trabajos de Foata y Schützenberger ^[1] sobre permutaciones, Bender y Goldman sobre prefabricados, ^[2] y Joyal sobre especies combinatorias . ^[3]

Tenga en cuenta que este método simbólico de enumeración no está relacionado con el "método simbólico de Blissard", que es simplemente otro nombre antiguo para el cálculo umbral .

El método simbólico en combinatoria constituye el primer paso de muchos análisis de estructuras combinatorias, que luego pueden conducir a esquemas de cálculo rápido, a propiedades asintóticas y leyes límites , a generación aleatoria , todas ellas aptas para la automatización mediante álgebra computacional .

Clases de estructuras combinatorias

Consideremos el problema de distribuir objetos dados por una función generadora en un conjunto de n ranuras, donde un grupo de permutación G de grado n actúa sobre las ranuras para crear una relación de equivalencia de configuraciones de ranuras llenas, y preguntar sobre la función generadora de las configuraciones por el peso de las configuraciones con respecto a esta relación de equivalencia, donde el peso de una configuración es la suma de los pesos de los objetos en las ranuras. Primero explicaremos cómo resolver este problema en el caso etiquetado y no etiquetado y usaremos la solución para motivar la creación de clases de estructuras combinatorias .

El teorema de enumeración de Pólya resuelve este problema en el caso no etiquetado. Sea f ( z ) la función generadora ordinaria (FGO) de los objetos, entonces la FGO de las configuraciones viene dada por el índice de ciclo sustituido

${\displaystyle Z(G)(f(z),f(z^{2}),\ldots ,f(z^{n})).}$

En el caso etiquetado, utilizamos una función generadora exponencial (EGF) g ( z ) de los objetos y aplicamos el teorema de enumeración etiquetado , que dice que la EGF de las configuraciones está dada por

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

Podemos enumerar configuraciones de ranuras llenas utilizando PET en el caso no etiquetado o el teorema de enumeración etiquetado en el caso etiquetado. Ahora nos preguntamos por la función generadora de configuraciones obtenidas cuando hay más de un conjunto de ranuras, con un grupo de permutación actuando en cada una. Claramente, las órbitas no se intersecan y podemos agregar las respectivas funciones generadoras. Supongamos, por ejemplo, que queremos enumerar secuencias no etiquetadas de longitud dos o tres de algunos objetos contenidos en un conjunto X . Hay dos conjuntos de ranuras, el primero contiene dos ranuras, y el segundo, tres ranuras. El grupo que actúa en el primer conjunto es , y en la segunda ranura, . Representamos esto mediante la siguiente serie de potencias formales en X : ${\displaystyle E_{2}}$ ${\displaystyle E_{3}}$

${\displaystyle X^{2}/E_{2}\;+\;X^{3}/E_{3}}$

donde el término se utiliza para denotar el conjunto de órbitas bajo G y , lo que denota de manera obvia el proceso de distribución de los objetos de X con repetición en las ranuras n . De manera similar, considere el problema etiquetado de crear ciclos de longitud arbitraria a partir de un conjunto de objetos etiquetados X . Esto produce la siguiente serie de acciones de grupos cíclicos: ${\displaystyle X^{n}/G}$ ${\displaystyle X^{n}=X\times \cdots \times X}$

${\displaystyle X/C_{1}\;+\;X^{2}/C_{2}\;+\;X^{3}/C_{3}\;+\;X^{4}/C_{4}\;+\cdots .}$

Claramente podemos asignar significado a cualquier serie de potencias de cocientes (órbitas) con respecto a grupos de permutación, donde restringimos los grupos de grado n a las clases de conjugación del grupo simétrico , que forman un dominio de factorización único. (Las órbitas con respecto a dos grupos de la misma clase de conjugación son isomorfas). Esto motiva la siguiente definición. ${\displaystyle \operatorname {Cl} (S_{n})}$ ${\displaystyle S_{n}}$

Una clase de estructuras combinatorias es una serie formal ${\displaystyle {\mathcal {C}}\in \mathbb {N} [{\mathfrak {A}}]}$

${\displaystyle {\mathcal {C}}=\sum _{n\geq 1}\sum _{G\in \operatorname {Cl} (S_{n})}c_{G}(X^{n}/G)}$

donde (la "A" es de "átomos") es el conjunto de primos de la UFD y ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle \{\operatorname {Cl} (S_{n})\}_{n\geq 1}}$ ${\displaystyle c_{G}\in \mathbb {N} .}$

A continuación simplificaremos un poco nuestra notación y escribiremos, por ejemplo:

${\displaystyle E_{2}+E_{3}{\text{ and }}C_{1}+C_{2}+C_{3}+\cdots .}$

para las clases mencionadas anteriormente.

El teorema fundamental de Flajolet-Sedgewick

Un teorema de la teoría de Flajolet-Sedgewick de combinatoria simbólica trata el problema de enumeración de clases combinatorias etiquetadas y no etiquetadas mediante la creación de operadores simbólicos que permiten traducir ecuaciones que involucran estructuras combinatorias directamente (y automáticamente) en ecuaciones en las funciones generadoras de estas estructuras.

Sea una clase de estructuras combinatorias. El OGF de donde X tiene OGF y el EGF de donde X está etiquetado con EGF están dados por ${\displaystyle {\mathcal {C}}\in \mathbb {N} [{\mathfrak {A}}]}$ ${\displaystyle F(z)}$ ${\displaystyle {\mathcal {C}}(X)}$ ${\displaystyle f(z)}$ ${\displaystyle G(z)}$ ${\displaystyle {\mathcal {C}}(X)}$ ${\displaystyle g(z)}$

${\displaystyle F(z)=\sum _{n\geq 1}\sum _{G\in \operatorname {Cl} (S_{n})}c_{G}Z(G)(f(z),f(z^{2}),\ldots ,f(z^{n}))}$

y

${\displaystyle G(z)=\sum _{n\geq 1}\left(\sum _{G\in \operatorname {Cl} (S_{n})}{\frac {c_{G}}{|G|}}\right)g(z)^{n}.}$

En el caso etiquetado tenemos el requisito adicional de que X no contenga elementos de tamaño cero. A veces resultará conveniente añadir uno a para indicar la presencia de una copia del conjunto vacío. Es posible asignar significado a ambos (el ejemplo más común es el caso de conjuntos no etiquetados) y Para demostrar el teorema simplemente aplique PET (teorema de enumeración de Pólya) y el teorema de enumeración etiquetado. ${\displaystyle G(z)}$ ${\displaystyle {\mathcal {C}}\in \mathbb {Z} [{\mathfrak {A}}]}$ ${\displaystyle {\mathcal {C}}\in \mathbb {Q} [{\mathfrak {A}}].}$

El poder de este teorema reside en el hecho de que permite construir operadores sobre funciones generadoras que representan clases combinatorias. De este modo, una ecuación estructural entre clases combinatorias se traduce directamente en una ecuación en las funciones generadoras correspondientes. Además, en el caso etiquetado resulta evidente a partir de la fórmula que podemos reemplazar por el átomo z y calcular el operador resultante, que luego puede aplicarse a las funciones generadoras de electrones. Ahora procedemos a construir los operadores más importantes. El lector puede comparar con los datos de la página del índice de ciclos . ${\displaystyle g(z)}$

El operador de secuencia.mw-parser-output .nobold{font-weight:normal}secuencia

Este operador corresponde a la clase

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

y representa secuencias, es decir, las ranuras no se están permutando y hay exactamente una secuencia vacía. Tenemos

${\displaystyle F(z)=1+\sum _{n\geq 1}Z(E_{n})(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}\left({\frac {1}{|E_{n}|}}\right)g(z)^{n}={\frac {1}{1-g(z)}}.}$

El operador del cicloCiclomotor

Este operador corresponde a la clase

${\displaystyle 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 conjunto SET y sus restricciones a grados específicos, se utilizan para calcular estadísticas de permutación aleatoria . Existen dos restricciones útiles de este operador, a saber, a ciclos pares e impares.

El operador de ciclo par etiquetado CYC es _par

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

que 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 _odd

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

viene 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)}}.}$

El operador multiconjunto/conjuntoConjunto M / Conjunto

La serie es

${\displaystyle 1+S_{1}+S_{2}+S_{3}+\cdots }$

es decir, el grupo simétrico se aplica a las ranuras. Esto crea conjuntos múltiples en el caso sin etiquetar y conjuntos en el caso etiquetado (no hay conjuntos múltiples en el caso etiquetado 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 etiquetado como en el caso sin etiquetar.

El caso sin etiquetar se realiza mediante la función

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

de modo que

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

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

${\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).}$

Procedimiento

Por lo general, se comienza con la clase neutral , que contiene un único objeto de tamaño 0 (el objeto neutral , a menudo denotado por ), y una o más clases atómicas , cada una de las cuales contiene un único objeto de tamaño 1. A continuación, las relaciones de teoría de conjuntos que involucran varias operaciones simples, como uniones disjuntas , productos , conjuntos , secuencias y multiconjuntos definen clases más complejas en términos de las clases ya definidas. Estas relaciones pueden ser recursivas . La elegancia de la combinatoria simbólica radica en que las relaciones de teoría de conjuntos, o simbólicas , se traducen directamente en relaciones algebraicas que involucran las funciones generadoras. ${\displaystyle {\mathcal {E}}}$ ${\displaystyle \epsilon }$ ${\displaystyle {\mathcal {Z}}}$

En este artículo, seguiremos la convención de utilizar letras mayúsculas para denotar clases combinatorias y las letras simples correspondientes para las funciones generadoras (de modo que la clase tenga función generadora ). ${\displaystyle {\mathcal {A}}}$ ${\displaystyle A(z)}$

Hay dos tipos de funciones generadoras que se utilizan comúnmente en la combinatoria simbólica: funciones generadoras ordinarias , utilizadas para clases combinatorias de objetos no etiquetados, y funciones generadoras exponenciales , utilizadas para clases de objetos etiquetados.

Es trivial demostrar que las funciones generadoras (ya sean ordinarias o exponenciales) para y son y , respectivamente. La unión disjunta también es simple: para conjuntos disjuntos y , implica . Las relaciones correspondientes a otras operaciones dependen de si estamos hablando de estructuras etiquetadas o no etiquetadas (y de funciones generadoras ordinarias o exponenciales). ${\displaystyle {\mathcal {E}}}$ ${\displaystyle {\mathcal {Z}}}$ ${\displaystyle E(z)=1}$ ${\displaystyle Z(z)=z}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {A}}={\mathcal {B}}\cup {\mathcal {C}}}$ ${\displaystyle A(z)=B(z)+C(z)}$

Suma combinatoria

La restricción de las uniones a uniones disjuntas es importante; sin embargo, en la especificación formal de la combinatoria simbólica, es demasiado complicado llevar un registro de qué conjuntos son disjuntos. En su lugar, hacemos uso de una construcción que garantiza que no haya intersección ( tenga cuidado, sin embargo; esto también afecta la semántica de la operación ). Al definir la suma combinatoria de dos conjuntos y , marcamos los miembros de cada conjunto con un marcador distinto, por ejemplo para los miembros de y para los miembros de . La suma combinatoria es entonces: ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle \circ }$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \bullet }$ ${\displaystyle {\mathcal {B}}}$

${\displaystyle {\mathcal {A}}+{\mathcal {B}}=({\mathcal {A}}\times \{\circ \})\cup ({\mathcal {B}}\times \{\bullet \})}$

Esta es la operación que corresponde formalmente a la suma.

Estructuras sin etiquetar

En el caso de estructuras no etiquetadas, se utiliza una función generadora ordinaria (FGO). La FGO de una secuencia se define como ${\displaystyle A_{n}}$

${\displaystyle A(x)=\sum _{n=0}^{\infty }A_{n}x^{n}}$

Producto

El producto de dos clases combinatorias y 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 y , . Esta debería ser una definición bastante intuitiva. Ahora observamos que el número de elementos en de tamaño n es ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle a\in {\mathcal {A}}}$ ${\displaystyle b\in {\mathcal {B}}}$ ${\displaystyle |(a,b)|=|a|+|b|}$ ${\displaystyle {\mathcal {A}}\times {\mathcal {B}}}$

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

Usando la definición de 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).}$

Secuencia

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

${\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 , o un par ordenado, triple ordenado, etc. Esto conduce a la relación ${\displaystyle {\mathcal {B}}}$

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

Colocar

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

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

lo que conduce 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.

Conjunto múltiple

La construcción de multiconjuntos , denotada como , 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 {\mathcal {A}}={\mathfrak {M}}\{{\mathcal {B}}\}}$

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

Esto nos lleva 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 manera similar a la construcción del conjunto anterior, expandimos , intercambiamos las sumas y sustituimos por el OGF de . ${\displaystyle \ln(1-z^{n})}$ ${\displaystyle {\mathcal {B}}}$

Otras construcciones elementales

Otras construcciones elementales importantes son:

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

Las derivaciones de estas construcciones son demasiado complicadas para mostrarlas aquí. A continuación se muestran los resultados:

Ejemplos

Se pueden construir muchas clases combinatorias utilizando estas construcciones elementales. Por ejemplo, la clase de árboles de plátanos (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

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

Resolvemos G ( z ) multiplicando para obtener ${\displaystyle 1-G(z)}$

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

Restando z y resolviendo G(z) usando la fórmula cuadrática obtenemos

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

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

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

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

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

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

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

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

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

Desafortunadamente, no existe una forma cerrada para ; sin embargo, el 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. ${\displaystyle P(z)}$

Especificación y clases especificables

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 es un conjunto de ecuaciones , donde es una expresión, cuyos átomos son y los 's, y cuyos operadores son las construcciones elementales enumeradas anteriormente. ${\displaystyle ({\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r})}$ ${\displaystyle r}$ ${\displaystyle {\mathcal {A}}_{i}=\Phi _{i}({\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r})}$ ${\displaystyle \Phi _{i}}$ ${\displaystyle {\mathcal {E}},{\mathcal {Z}}}$ ${\displaystyle {\mathcal {A}}_{i}}$

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 (o impar, respectivamente) se puede definir utilizando la especificación con dos clases y . Esas clases deben satisfacer la ecuación y . ${\displaystyle {\mathcal {A}}_{\text{even}}}$ ${\displaystyle {\mathcal {A}}_{\text{odd}}}$ ${\displaystyle {\mathcal {A}}_{\text{odd}}={\mathcal {Z}}\times \operatorname {Seq} _{\geq 1}{\mathcal {A}}_{\text{even}}}$ ${\displaystyle {\mathcal {A}}_{\text{even}}={\mathcal {Z}}\times \operatorname {Seq} {\mathcal {A}}_{\text{odd}}}$

Estructuras etiquetadas

Un objeto está débilmente etiquetado si cada uno de sus átomos tiene una etiqueta de número entero no negativo, y cada una de estas etiquetas es distinta. Un objeto está ( fuertemente o bien ) etiquetado si, además, estas etiquetas comprenden los números enteros consecutivos . Nota: algunas clases combinatorias se especifican mejor como estructuras etiquetadas o estructuras no etiquetadas, pero algunas admiten fácilmente ambas especificaciones. Un buen ejemplo de estructuras etiquetadas es la clase de grafos etiquetados . ${\displaystyle [1\ldots n]}$

Con estructuras etiquetadas, se utiliza una función generadora exponencial (EGF). La EGF de una secuencia se define como ${\displaystyle A_{n}}$

${\displaystyle A(x)=\sum _{n=0}^{\infty }A_{n}{\frac {x^{n}}{n!}}.}$

Producto

Para las estructuras etiquetadas, debemos utilizar una definición de producto diferente que para las estructuras no etiquetadas. De hecho, si simplemente utilizáramos el producto cartesiano, las estructuras resultantes ni siquiera estarían bien etiquetadas. En su lugar, utilizamos el llamado producto etiquetado , denotado ${\displaystyle {\mathcal {A}}\star {\mathcal {B}}.}$

Para un par y , deseamos combinar las dos estructuras en una sola estructura. Para que el resultado esté bien etiquetado, esto requiere un reetiquetado de los átomos en y . Restringiremos nuestra atención a los reetiquetados que sean consistentes con el orden de las etiquetas originales. Tenga en cuenta que todavía hay múltiples formas de hacer el reetiquetado; por lo tanto, cada par de miembros determina no un solo 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 etiquetado . ${\displaystyle \beta \in {\mathcal {B}}}$ ${\displaystyle \gamma \in {\mathcal {C}}}$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$

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

${\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 y es ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

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

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

${\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 los EGF,

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

Secuencia

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

${\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 arriba,

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

Colocar

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

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

Ciclo

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

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

Producto en caja

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

${\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).}$

Ejemplo

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

Otras construcciones elementales

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 .

Ejemplo

Los números de Stirling del segundo tipo se pueden derivar y analizar 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 números de Stirling sin signo de primera especie y en la derivación de las estadísticas de permutaciones aleatorias . Se puede encontrar un examen detallado de las funciones generadoras exponenciales asociadas a los números de Stirling dentro de la combinatoria simbólica en la página sobre números de Stirling y funciones generadoras exponenciales en la combinatoria simbólica .

Véase también

• Especies combinatorias

Referencias

1. Foata, Dominique ; Schützenberger, Marcel-P. (1970). "Teoría geométrica de los polinômes Eulériens". Apuntes de conferencias sobre matemáticas . Apuntes de conferencias de matemáticas. 138 . arXiv : matemáticas/0508232 . doi : 10.1007/BFb0060799 . ISBN 978-3-540-04927-2.
2. Bender, Edward A.; Goldman, Jay R. (1971). "Usos enumerativos de funciones generadoras". Indiana University Mathematics Journal . 20 (8): 753–764. doi : 10.1512/iumj.1971.20.20060 .
3. Joyal, André (1981). "Una teoría combinatoria de series formales". Avances en Matemáticas . 42 : 1–82. doi :10.1016/0001-8708(81)90052-9.

• 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).
• Philippe Flajolet y Robert Sedgewick, Analytic Combinatorics , Cambridge University Press (2009). (Disponible en línea: http://algo.inria.fr/flajolet/Publications/book.pdf)
• Micha Hofri, Análisis de algoritmos: métodos computacionales y herramientas matemáticas , Oxford University Press (1995).