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 está asociado 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 usar el análisis complejo para obtener resultados asintóticos y probabilísticos en las funciones generadoras correspondientes.
Durante dos siglos, las funciones generadoras fueron apareciendo a través de las correspondientes recurrencias en sus coeficientes (como puede verse en las obras seminales de Bernoulli [ desambiguación necesaria ] , Euler , Arthur Cayley , Schröder , Ramanujan , Riordan , Knuth , Comtet , etc.). Luego se fue dando cuenta lentamente de que las funciones generadoras estaban capturando muchas otras facetas de los objetos combinatorios discretos iniciales, y que esto podría hacerse 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 , en la década de 1970 se hicieron nuevos avances en este espíritu 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 en la enumeración no está relacionado con el "método simbólico de Blissard", que es solo 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ómputo rápido, a propiedades asintóticas y leyes límite , a generación aleatoria , todos ellos aptos para la automatización vía álgebra computacional .
Clases de estructuras combinatorias
Considere 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 acerca de la función generadora de las configuraciones por 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 sin etiquetar. Sea f ( z ) la función generadora ordinaria (OGF) de los objetos, entonces el OGF de las configuraciones viene dado por el índice de ciclo sustituido
En el caso etiquetado usamos una función generadora exponencial (EGF) g ( z ) de los objetos y aplicamos el teorema de enumeración etiquetado , que dice que el EGF de las configuraciones está dado por
Podemos enumerar configuraciones de ranuras llenas utilizando PET en el caso sin etiquetar o el teorema de enumeración etiquetado en el caso etiquetado. Ahora preguntamos acerca de la función generadora de configuraciones obtenidas cuando hay más de un conjunto de ranuras, con un grupo de permutación actuando sobre cada una. Claramente, las órbitas no se cruzan y podemos agregar las respectivas funciones generadoras. Supongamos, por ejemplo, que queremos enumerar secuencias no marcadas de longitud dos o tres de algunos objetos contenidos en un conjunto X . Hay dos juegos de ranuras, el primero contiene dos ranuras y el segundo, tres ranuras. El grupo que actúa en el primer set es, y en la segunda ranura, . Representamos esto mediante la siguiente serie de potencias formales en X :
donde el término se utiliza para denotar el conjunto de órbitas bajo G y, que denota de forma obvia el proceso de distribución de los objetos de X con repetición en las n ranuras. De manera similar, considere el problema etiquetado de crear ciclos de longitud arbitraria a partir de un conjunto de objetos X etiquetados . Esto produce la siguiente serie de acciones de grupos cíclicos:
Claramente, podemos asignar significado a cualquier serie de cocientes de potencias (órbitas) con respecto a los 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.
Una clase de estructuras combinatorias es una serie formal
dónde (la "A" es para "átomos") es el conjunto de números primos de la UFD y
A continuación, simplificaremos un poco nuestra notación y escribiremos, por ejemplo,
para las clases mencionadas anteriormente.
El teorema fundamental de Flajolet-Sedgewick
Un teorema de la teoría de combinatoria simbólica de Flajolet-Sedgewick 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 directa (y automáticamente) en ecuaciones en las funciones generadoras. de estas estructuras.
Dejar ser una clase de estructuras combinatorias. El OGF de donde X tiene OGF y el EGF de donde X está etiquetado con EGF son dadas por
y
En el caso etiquetado tenemos el requisito adicional de que X no contenga elementos de tamaño cero. A veces resultará conveniente agregar uno apara 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 sin etiquetar) y Para probar el teorema, simplemente aplique PET (teorema de enumeración de Pólya) y el teorema de enumeración etiquetado.
El poder de este teorema radica en el hecho de que permite construir operadores sobre funciones generadoras que representan clases combinatorias. Una ecuación estructural entre clases combinatorias se traduce así directamente en una ecuación en las funciones generadoras correspondientes. Además, en el caso etiquetado es evidente a partir de la fórmula que podemos reemplazarpor el átomo zy calcular el operador resultante, que luego se puede aplicar a los EGF. Ahora procedemos a construir los operadores más importantes. Es posible que el lector desee comparar con los datos de la página de índice del ciclo .
El operador de secuencia SEQ
Este operador corresponde a la clase
y representa secuencias, es decir, las ranuras no se están permutando y hay exactamente una secuencia vacía. Tenemos
y
El operador de ciclo CYC
Este operador corresponde a la clase
es decir, ciclos que contienen al menos un objeto. Tenemos
o
y
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 . Hay dos restricciones útiles de este operador, a saber, ciclos pares e impares.
El operador de ciclo par etiquetado CYC even es
cuyos rendimientos
Esto implica que el operador de ciclo impar etiquetado CYC impar
es dado por
El operador multiset / set MSET / SET
La serie es
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 sin etiquetar.
El caso sin etiquetar se realiza mediante la función
así que eso
Evaluar obtenemos
Para el caso etiquetado tenemos
En el caso etiquetado, denotamos al operador por SET , y en el caso no etiquetado, por MSET . Esto se debe a que en el caso etiquetado no hay conjuntos múltiples (las etiquetas distinguen los constituyentes de una clase combinatoria compuesta) mientras que en el caso no etiquetado hay conjuntos múltiples y conjuntos, siendo este último dado por
Procedimiento
Normalmente, uno comienza con la clase neutral. , que contiene un solo objeto de tamaño 0 (el objeto neutral , a menudo denotado por), y una o más clases atómicas , cada una contiene un solo objeto de tamaño 1. A continuación, las relaciones teóricas de conjuntos que involucran varias operaciones simples, como uniones disjuntas , productos , conjuntos , secuencias y multijuegos 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 teóricas o simbólicas de conjuntos se traducen directamente en relaciones algebraicas que involucran funciones generadoras.
En este artículo, seguiremos la convención de usar letras mayúsculas del script para denotar clases combinatorias y las letras simples correspondientes para las funciones generadoras (por lo que la clase tiene función generadora ).
Hay dos tipos de funciones generadoras que se usan comúnmente en combinatoria simbólica: funciones generadoras ordinarias , que se usan para clases combinatorias de objetos sin etiquetar, y funciones generadoras exponenciales , que se usan para clases de objetos etiquetados.
Es trivial mostrar que las funciones generadoras (ordinarias o exponenciales) para y están 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 funciones generadoras ordinarias o exponenciales).
Suma combinatoria
La restricción de los sindicatos a los sindicatos disjuntos es importante; sin embargo, en la especificación formal de la combinatoria simbólica, es demasiado complicado hacer un seguimiento de los conjuntos que están separados. En su lugar, utilizamos una construcción que garantiza que no hay 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 miembros de y para miembros de . La suma combinatoria es entonces:
Esta es la operación que formalmente corresponde a la suma.
Estructuras sin etiquetar
Con estructuras no etiquetadas, se utiliza una función generadora ordinaria (OGF). El OGF de una secuencia Se define como
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. Así tenemos para y , . Esta debería ser una definición bastante intuitiva. Ahora notamos que el número de elementos ende tamaño n es
Usando la definición de OGF y algo de álgebra elemental, podemos demostrar que
- implica
Secuencia
La construcción de la secuencia , denotada por Se define como
En otras palabras, una secuencia es el elemento neutral o un elemento de , o un par ordenado, triple ordenado, etc. Esto conduce a la relación
Colocar
La construcción del conjunto (o conjunto de potencias ) , denotado por Se define como
que lleva a la relación
donde la expansion
se utilizó para pasar de la línea 4 a la línea 5.
Multiset
La construcción multiset , denotadaes una generalización de la construcción del set. En la construcción del conjunto, cada elemento puede aparecer cero o una vez. En un conjunto múltiple, cada elemento puede aparecer un número arbitrario de veces. Por lo tanto,
Esto conduce a la relación
donde, de forma similar a la construcción del conjunto anterior, expandimos , intercambiar las sumas y sustituir el OGF de .
Otras construcciones elementales
Otras construcciones elementales importantes son:
- la construcción ciclo (), como secuencias excepto que las rotaciones cíclicas no se consideran distintas
- señalando (), en el que cada miembro de se aumenta con un puntero neutro (tamaño cero) a uno de sus átomos
- sustitución (), en el que cada átomo de un miembro de es reemplazado por un miembro de .
Las derivaciones de estas construcciones son demasiado complicadas para mostrarlas aquí. Aquí están los resultados:
Construcción | Función generadora |
---|---|
(dónde es la función totient de Euler ) | |
Ejemplos de
Se pueden construir muchas clases combinatorias usando estas construcciones elementales. Por ejemplo, la clase de avión árboles (es decir, árboles incrustados en el plano, de modo que el orden de los asuntos subárboles) es especificado por el recursiva relación
En otras palabras, un árbol es un nodo raíz de tamaño 1 y una secuencia de subárboles. Esto da
resolvemos para G ( z ) multiplicando Llegar
restar zy resolver para G (z) usando la fórmula cuadrática da
Otro ejemplo (y un problema clásico de combinatoria) son las particiones enteras . Primero, defina la clase de enteros positivos, donde el tamaño de cada entero es su valor:
El OGF de es entonces
Ahora, defina el conjunto de particiones como
El OGF de es
Desafortunadamente, no existe un formulario cerrado para ; sin embargo, el OGF puede usarse para derivar una relación de recurrencia , o usando métodos más avanzados de combinatoria analítica, calcular el comportamiento asintótico de la secuencia de conteo.
Especificación y clases especificables
Las construcciones elementales mencionadas anteriormente permiten definir la noción de especificación . Esas especificaciones permiten 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 , dónde es una expresión, cuyos átomos son y el 's, 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 usando la especificación con dos clases y . Esas clases deben satisfacer la ecuación y .
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á ( fuerte 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 gráficos etiquetados .
Con estructuras etiquetadas, se utiliza una función generadora exponencial (EGF). El EGF de una secuencia Se define como
Producto
Para las estructuras etiquetadas, debemos utilizar una definición de producto diferente a la de las estructuras no etiquetadas. De hecho, si utilizáramos simplemente el producto cartesiano, las estructuras resultantes ni siquiera estarían bien etiquetadas. En su lugar, utilizamos el llamado producto etiquetado , denotado
Por un par y , deseamos combinar las dos estructuras en una sola estructura. Para que el resultado esté bien etiquetado, esto requiere cierto reetiquetado de los átomos en y . Restringiremos nuestra atención a los cambios de etiqueta que sean coherentes con el orden de las etiquetas originales. Tenga en cuenta que todavía hay varias formas de realizar 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 .
Para ayudar a este desarrollo, definamos una función, , que toma como argumento un objeto etiquetado (posiblemente débilmente) y vuelve a etiquetar sus átomos de una manera coherente en el orden para que está bien etiquetado. Luego definimos el producto etiquetado para dos objetos y como
Finalmente, el producto etiquetado de dos clases y es
El EGF se puede derivar señalando que para objetos de tamaño y , existen formas de hacer el reetiquetado. Por lo tanto, el número total de objetos de tamaño es
Esta relación de convolución binomial para los términos equivale a multiplicar los EGF,
Secuencia
La construcción de la secuencia se define de manera similar al caso sin etiquetar:
y nuevamente, como arriba,
Colocar
En estructuras etiquetadas, un conjunto de elementos corresponde exactamente a secuencias. Esto es diferente del caso sin etiquetar, donde algunas de las permutaciones pueden coincidir. Por lo tanto, para, tenemos
Ciclo
Los ciclos también son más fáciles que en el caso sin etiquetar. Un ciclo de duración corresponde a secuencias distintas. Por lo tanto, para, tenemos
Producto en caja
En estructuras etiquetadas, el producto en caja mínima 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 en caja máxima, denotado por, de la misma manera. Entonces nosotros tenemos,
o equivalente,
Ejemplo
Un árbol Cayley creciente es un árbol etiquetado no plano y enraizado cuyas etiquetas a lo largo de cualquier rama que se deriva de la raíz forman una secuencia creciente. Entonces, dejasea la clase de tales árboles. La especificación recursiva es ahora
Otras construcciones elementales
Los operadores CYC incluso , CYC impar , SET incluso , y SET impar representan ciclos de longitud par e impar, y conjuntos de cardinalidad par e impar.
Ejemplo
Los números de Stirling del segundo tipo pueden derivarse y analizarse utilizando la descomposición estructural
La descomposición
se utiliza para estudiar números de Stirling sin signo del primer tipo y en la derivación de las estadísticas de permutaciones aleatorias . Un examen 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 los números de Stirling y las funciones generadoras exponenciales en la combinatoria simbólica .
Ver también
- Especies combinatorias
Referencias
- ^ Foata, D .; Schützenberger, M. (1970). "Théorie géométrique des polynômes Eulériens". Notas de conferencias en matemáticas . 138 .
- ^ Bender, EA; Goldman, JR (1971). "Usos enumerativos de funciones generadoras". Indiana Univ. Matemáticas. J . 20 : 753–764.
- ^ Joyal, André (1981). "Une théorie combinatoire des séries formelles". Adv. Matemáticas. 42 : 1–82.
- François Bergeron, Gilbert Labelle, Pierre Leroux, Théorie des espèces et combinatoire des structure arborescentes , LaCIM, Montreal (1994). Versión en inglés: Combinatorial Species and Tree-like Structures , Cambridge University Press (1998).
- Philippe Flajolet y Robert Sedgewick, Analítica combinatoria , 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).