Especies combinatorias

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En matemáticas combinatorias, la teoría de las especies combinatorias es un método abstracto y sistemático para derivar las funciones generatrices de estructuras discretas, que permite no solo contar estas estructuras sino dar pruebas biyectivas que las involucran. Ejemplos de especies combinatorias son grafos (finitos), permutaciones, árboles, etc.; cada uno de estos tiene una función generadora asociada que cuenta cuántas estructuras hay de un tamaño determinado. Uno de los objetivos de la teoría de las especies es poder analizar estructuras complicadas describiéndolas en términos de transformaciones y combinaciones de estructuras más simples. Estas operaciones corresponden a manipulaciones equivalentes de funciones generadoras, por lo que producir tales funciones para estructuras complicadas es mucho más fácil que con otros métodos. La teoría fue presentada, cuidadosamente elaborada y aplicada por investigadores canadienses en torno a André Joyal.

El poder de la teoría proviene de su nivel de abstracción. El "formato de descripción" de una estructura (como lista de adyacencia versus matriz de adyacencia para gráficos) es irrelevante, porque las especies son puramente algebraicas. La teoría de categorías proporciona un lenguaje útil para los conceptos que surgen aquí, pero no es necesario comprender las categorías antes de poder trabajar con especies.

La categoría de especies es equivalente a la categoría de secuencias simétricas en conjuntos finitos.

Definición de especie

Ilustración esquemática de una estructura de especies combinatorias en cinco elementos utilizando un diagrama de etiqueta

Cualquier estructura, una instancia de una especie en particular, está asociada con algún conjunto y, a menudo, hay muchas estructuras posibles para el mismo conjunto. Por ejemplo, es posible construir varios gráficos diferentes cuyas etiquetas de nodo se extraigan del mismo conjunto dado. Al mismo tiempo, cualquier conjunto podría usarse para construir las estructuras. La diferencia entre una especie y otra es que construyen un conjunto diferente de estructuras a partir del mismo conjunto base.

Esto conduce a la definición formal de un especie combinatoria. Vamos ${mathcal {B}}$ ser la categoría de conjuntos finitos, con los morfismos de la categoría siendo las bijeciones entre estos conjuntos. A especie es un functor

{displaystyle Fcolon {mathcal {B}}to {mathcal {B}}.}

Para cada conjunto finito A dentro ${mathcal {B}}$ , el conjunto finito F[A] se llama el conjunto de F-estructuras en A, o el conjunto de estructuras de especies F on A. Además, por la definición de un functor, si φ es una bijección entre conjuntos A y B, entonces F[φ] es una bijección entre los conjuntos de F-estructuras F[A] y F[B], llamado transporte de F-estructuras a lo largo de φ.

Por ejemplo, las "especies de permutaciones" asigna cada conjunto finito A al conjunto de todas las permutaciones de A, y cada biyección de A a otro conjunto B induce naturalmente una biyección del conjunto de todas las permutaciones de A al conjunto de todas las permutaciones de B. Del mismo modo, las "especies de tabiques" se puede definir asignando a cada conjunto finito el conjunto de todas sus particiones, y la "especie del conjunto potencia" asigna a cada conjunto finito su conjunto potencia. El diagrama adyacente muestra una estructura en un conjunto de cinco elementos: los arcos conectan la estructura (rojo) a los elementos (azul) a partir de los cuales se construye.

Porque existe una bijeción entre dos conjuntos finitos si y sólo si los dos conjuntos tienen la misma cardinalidad (el número de elementos), para cada conjunto finito A, el cardenalismo ${displaystyle F[A]}$ , que es finito, depende sólo de la cardinalidad A. (Esto se deriva de la definición formal de un functor.) En particular, serie de generación exponencial F()x) de una especie F puede definirse:

{displaystyle F(x)=sum _{ngeq 0}operatorname {Card} F[n]{frac {x^{n}}{n!}}}

Donde ${displaystyle operatorname {Card} F[n]}$ es el cardenalismo ${displaystyle F[A]}$ para cualquier conjunto A teniendo n elementos; por ejemplo, ${displaystyle A={1,2,dotsn}}$ .

Algunos ejemplos: escribir ${displaystyle f_{n}=operatorname {Card} F[n]}$ ,

La especie de conjuntos (tradicionalmente llamada E, de los franceses "ensemble", que significa "set") es el functor que mapas A aA}. Entonces... $f_{n}=1$ Así que $E(x)=e^{x}$ .
La especie S of permutations, described above, has $f_{n}=n!$ . $S(x)=1/(1-x)$ .
La especie T₂ de pares (2-tuples) es el functor tomando un conjunto A a A². Entonces... $f_{n}=n^{2}$ y $T_{2}(x)=x(x+1)e^{x}$ .

Cálculo de especies

La aritmética de las funciones generadoras corresponde a ciertas funciones "naturales" operaciones sobre especies. Las operaciones básicas son la suma, la multiplicación, la composición y la diferenciación; también es necesario definir la igualdad de especies. La teoría de categorías ya tiene una forma de describir cuándo dos funtores son equivalentes: un isomorfismo natural. En este contexto, solo significa que para cada A hay una biyección entre estructuras F en A y G-estructuras en A, que tiene un "buen comportamiento" en su interacción con el transporte. Las especies con la misma función generadora pueden no ser isomorfas, pero las especies isomorfas siempre tienen la misma función generadora.

Adición

La adición de especies se define por la unión disjunta de conjuntos, y corresponde a una elección entre estructuras. Para las especies F y G, defina (F + G)[A] ser la unión disjunta (también escrita "+") de F[A] y G[ A]. De ello se deduce que (F + G)(x) = F(x) + G(x). Como demostración, tome E⁺ como la especie de conjuntos no vacíos, cuya función generadora es E⁺(x) = e^x − 1, y 1 la especie de el conjunto vacío, cuya función generadora es 1(x) = 1. Se sigue que E = 1 + E⁺: en palabras, "un conjunto está vacío o no está vacío". Ecuaciones como esta pueden interpretarse como una referencia a una sola estructura, así como a la colección completa de estructuras.

Multiplicación

Multiplicar especies es un poco más complicado. Es posible tomar simplemente el producto cartesiano de conjuntos como definición, pero la interpretación combinatoria de esto no es del todo correcta. (Consulte a continuación el uso de este tipo de producto). En lugar de juntar dos estructuras no relacionadas en el mismo conjunto, el operador de multiplicación usa la idea de dividir el conjunto en dos componentes, construyendo una F- estructura en uno y una estructura G en el otro.

(Fcdot G)[A]=sum _{{A=B+C}}F[B]times G[C].

Esta es una unión separada de todas las posibles particiones binarias de A. Es sencillo mostrar que la multiplicación es asociativa y conmutativa (hasta el isomorfismo) y distributiva sobre la suma. En cuanto a la serie generadora, (F · G)(x) = F(x)G(x).

El siguiente diagrama muestra una estructura posible (F · G) en un conjunto con cinco elementos. La estructura F (roja) recoge tres elementos del conjunto base, y la estructura G (azul claro) toma el resto. Otras estructuras tendrán F y G dividiendo el conjunto de forma diferente. El conjunto (F · G)[A], donde A es el conjunto base, es la unión disjunta de todas esas estructuras.

La suma y la multiplicación de especies son la expresión más completa de las reglas de conteo de suma y producto.

Composición

Composición, también llamada sustitución, es nuevamente más complicada. La idea básica es reemplazar los componentes de F con estructuras G, formando (F∘G). Al igual que con la multiplicación, esto se hace dividiendo el conjunto de entrada A; los subconjuntos disjuntos se le dan a G para hacer estructuras G, y el conjunto de subconjuntos se le da a F, para hacer el Estructura F que une las estructuras G. Se requiere que G mapee el conjunto vacío a sí mismo, para que la composición funcione. La definición formal es:

{displaystyle (Fcirc G)[A]=sum _{pi in P[A]}(F[pi ]times prod _{Bin pi }G[B]).}

Aquí, P es la especie de particiones, así P[A] es el conjunto de todas las particiones de A. Esta definición dice que un elemento de (F∘G[AEstá hecho de un F-estructura en alguna partición de A, y un G-estructura en cada componente de la partición. La serie generadora es $(Fcirc G)(x)=F(G(x))$ .

Una de esas estructuras se muestra a continuación. Tres estructuras G (azul claro) dividen el conjunto base de cinco elementos entre ellas; luego, se construye una estructura F (roja) para conectar las estructuras G.

Estas dos últimas operaciones pueden ilustrarse con el ejemplo de los árboles. Primero, defina X como la especie "singleton" cuya serie generadora es X(x) = x. Entonces la especie Ar de árboles enraizados (del francés "arborescence") se define recursivamente por Ar = X · E(Ar). Esta ecuación dice que un árbol consta de una sola raíz y un conjunto de (sub)árboles. La recursividad no necesita un caso base explícito: solo genera árboles en el contexto de ser aplicado a algún conjunto finito. Una forma de pensar en esto es que el funtor Ar se aplica repetidamente a un "suministro" de elementos del conjunto — cada vez, un elemento es tomado por X, y los otros distribuidos por E entre los subárboles Ar, hasta que haya No quedan más elementos para dar a E. Esto muestra que las descripciones algebraicas de especies son bastante diferentes de las especificaciones de tipos en lenguajes de programación como Haskell.

Asimismo, la especie P se puede caracterizar como P=E()E⁺): "una partición es un conjunto de conjunto de conjuntos no vacíos (utilizando todos los elementos del conjunto de entrada)". La serie de generación exponencial para P es $P(x)=e^{{(e^{x}-1)}}$ , que es la serie para los números de Bell.

Diferenciación

diferenciación de especies corresponde intuitivamente a la construcción de "estructuras con un agujero", como se muestra en la siguiente ilustración.

Formalmente,

(F')[A]=F[Auplus {star }],

Donde $star$ es un nuevo elemento distinguido que no está presente $A$ .

Para diferenciar la serie exponencial asociada, la secuencia de coeficientes debe desplazarse un lugar hacia la "izquierda" (perdiendo el primer término). Esto sugiere una definición de especie: F' [A] = F[A + {*}], donde {*} es un conjunto singleton y "+" es unión disjunta. Las partes más avanzadas de la teoría de las especies usan la diferenciación ampliamente para construir y resolver ecuaciones diferenciales sobre especies y series. La idea de agregar (o eliminar) una sola parte de una estructura es poderosa: puede usarse para establecer relaciones entre especies aparentemente desconectadas.

Por ejemplo, considere una estructura de la especie L de órdenes lineales: listas de elementos del conjunto básico. Eliminar un elemento de una lista lo divide en dos partes (posiblemente vacías); en símbolos, es L' = L·L. La función generadora exponencial de L es L(x) = 1/(1 − x), y de hecho:

{displaystyle {frac {d}{dx}}{(1-x)}^{-1}={(1-x)}^{-2}.}

Las fórmulas de diferenciación generalizada se encuentran en una investigación previa de N. G. de Bruijn, publicada en 1964.

La especie C de permutaciones cíclicas toma un conjunto A al conjunto de todos los ciclos en A. Eliminar un solo elemento de un ciclo lo reduce a una lista: C' = L. Podemos integrar la función generadora de L para producir la de C.

C(x)=int _{0}^{x}{frac {dt}{1-t}}=log {frac {1}{1-x}}.

Un buen ejemplo de integración de una especie es completar una línea (coordinada por un campo) con el punto infinito y obtener una línea proyectiva.

Más operaciones

Hay una variedad de otras manipulaciones que se pueden realizar en las especies. Estos son necesarios para expresar estructuras más complicadas, como gráficos dirigidos o bígrafos.

Señalar selecciona un solo elemento en una estructura. Dada una especie F, la especie puntiaguda correspondiente F^• se define mediante F^•[A] = A × F[A]. Así, cada estructura F^• es una estructura F con un elemento diferenciado. Señalar está relacionado con la diferenciación por la relación F^• = X·F' , entonces F^•(x) = x F' (x). La especie de conjuntos puntiagudos, E^•, es particularmente importante como bloque de construcción para muchas de las construcciones más complejas.

El producto cartesiano de dos especies es una especie que puede construir dos estructuras en el mismo conjunto al mismo tiempo. Se diferencia del operador de multiplicación ordinario en que todos los elementos del conjunto base se comparten entre las dos estructuras. Una estructura (F × G) puede verse como una superposición de una estructura F y una G -estructura. Los bígrafos podrían describirse como la superposición de un grafo y un conjunto de árboles: cada nodo del bígrafo es parte de un grafo y, al mismo tiempo, parte de algún árbol que describe cómo se anidan los nodos. La función generadora (F × G)(x) es el producto de Hadamard o de coeficientes de F(x) y G(x).

Puede verse que la especie E^• × E^• hace dos selecciones independientes del conjunto base. Los dos puntos pueden coincidir, a diferencia de X·X·E, donde están obligados a ser diferentes.

Como functores, especies F y G puede ser combinado por functorial composition: ${displaystyle (F,Box ,G)[A]=F[G[A]]}$ (el símbolo de la caja se utiliza, porque el círculo ya está en uso para la sustitución). Esto construye un F-estructura en el conjunto de todos G-estructuras en el set A. Por ejemplo, si F es el functor tomando un conjunto a su conjunto de potencia, una estructura de la especie compuesta es un subconjunto del G-estructuras en A. Si tomamos ahora G para ser E^• × E^• de arriba, obtenemos la especie de grafitos dirigidos, con auto-ops permitidos. (Un gráfico dirigido es un conjunto de bordes, y los bordes son pares de nodos: por lo que un gráfico es un subconjunto del conjunto de pares de elementos del conjunto del nodo A.) Otras familias de gráficos, así como muchas otras estructuras, pueden definirse de esta manera.

Software

Las operaciones con especies son compatibles con SageMath y, utilizando un paquete especial, también con Haskell.

Variantes

Una especie en clase k es un functor ${mathcal {B}}^{k}rightarrow {mathcal {B}}$ . Aquí, las estructuras producidas pueden tener elementos extraídos de fuentes distintas.
Un functor a ${mathcal {B}}_{R}$ , la categoría de R- Sets de peso para R un anillo de la serie de energía, es un especies ponderadas.

Si se reemplaza "conjuntos finitos con biyecciones" por "espacios vectoriales finitos con transformaciones lineales", entonces se obtiene la noción de funtor polinomial (después de imponer alguna condición de finitud).

Contenido relacionado

Más resultados...