Especies combinatorias

En matemáticas combinatorias , la teoría de especies combinatorias es un método abstracto y sistemático para derivar las funciones generadoras de estructuras discretas, que permite no solo contar estas estructuras sino también dar pruebas biyectivas que las involucran. Ejemplos de especies combinatorias son los grafos (finitos) , las permutaciones , los árboles , etc.; cada uno de estos tiene una función generadora asociada que cuenta cuántas estructuras hay de un cierto tamaño. Un objetivo de la teoría de 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 introducida, 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 una lista de adyacencia versus una matriz de adyacencia para grafos) 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 especie es equivalente a la categoría de secuencias simétricas en conjuntos finitos. ^[1]

Definición de especie

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

Cualquier especie consiste en estructuras combinatorias individuales construidas sobre los elementos de algún conjunto finito: por ejemplo, un grafo combinatorio es una estructura de aristas entre un conjunto dado de vértices, y la especie de grafos incluye todos los grafos en todos los conjuntos finitos. Además, un miembro de una especie puede tener su conjunto subyacente reetiquetado por los elementos de cualquier otro conjunto equinumeroso, por ejemplo, reetiquetar los vértices de un grafo da "la misma estructura de grafo" en los nuevos vértices, es decir, un grafo isomorfo .

Esto nos lleva a la definición formal de una especie combinatoria . Sea la categoría de conjuntos finitos , siendo los morfismos de la categoría las biyecciones entre estos conjuntos. Una especie es un funtor ^[2] ${\displaystyle {\mathcal {B}}}$

${\displaystyle F\colon {\mathcal {B}}\to {\mathcal {B}}.}$

Para cada conjunto finito A en , el conjunto finito F [ A ] ^{[nota 1]} se denomina conjunto de F -estructuras en A , o conjunto de estructuras de especie F en A . Además, por la definición de un funtor, si φ es una biyección entre los conjuntos A y B , entonces F [φ] es una biyección entre los conjuntos de F -estructuras F [ A ] y F [ B ], denominada transporte de F-estructuras a lo largo de φ . ^[3] ${\displaystyle {\mathcal {B}}}$

Por ejemplo, la "especie de permutaciones" ^[4] asigna cada conjunto finito A al conjunto S [ A ] de todas las permutaciones de A (todas las formas de ordenar A en una lista), y cada biyección f de A a otro conjunto B induce naturalmente una biyección (un reetiquetado) que lleva cada permutación de A a una permutación correspondiente de B , es decir, una biyección . De manera similar, la "especie de particiones" se puede definir asignando a cada conjunto finito el conjunto de todas sus particiones , y la "especie de conjunto potencia" asigna a cada conjunto finito su conjunto potencia . El diagrama adyacente muestra una estructura (representada por un punto rojo) construida sobre un conjunto de cinco elementos distintos (representados por puntos azules); una estructura correspondiente podría construirse a partir de cinco elementos cualesquiera. ${\displaystyle S[f]:S[A]\to S[B]}$

Dos conjuntos finitos están en biyección siempre que tengan la misma cardinalidad (número de elementos); por lo tanto, por definición, los conjuntos de especies correspondientes también están en biyección, y la cardinalidad (finita) de depende solo de la cardinalidad de A . ^{[nota 2]} En particular, la serie generadora exponencial F ( x ) de una especie F se puede definir: ^[5] ${\displaystyle F[A]}$

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

donde es la cardinalidad de para cualquier conjunto A que tenga n elementos; por ejemplo, . ${\displaystyle \operatorname {Card} F[n]}$ ${\displaystyle F[A]}$ ${\displaystyle A=\{1,2,\dots ,n\}}$

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

• La especie de conjunto (tradicionalmente llamada E , del francés " ensemble ", que significa "conjunto") es el funtor que asigna A a { A }. Entonces , entonces . ${\displaystyle f_{n}=1}$ ${\displaystyle E(x)=e^{x}}$
• La especie S de permutaciones , descrita anteriormente, tiene . . ${\displaystyle f_{n}=n!}$ ${\displaystyle S(x)=1/(1-x)}$
• La especie T ₂ de pares ordenados (2- tuplas ) es el funtor que toma un conjunto A a A ² . Entonces y . ${\displaystyle f_{n}=n^{2}}$ ${\displaystyle T_{2}(x)=x(x+1)e^{x}}$

Cálculo de especies

La aritmética sobre funciones generadoras corresponde a ciertas operaciones "naturales" 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 sobre 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, simplemente significa que para cada A hay una biyección entre las estructuras F sobre A y las estructuras G sobre A , que se "comporta bien" 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.

Suma

La adición de especies se define por la unión disjunta de conjuntos, y corresponde a una elección entre estructuras. ^[6] Para las especies F y G , defina ( F + G )[ A ] como 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 como la especie del conjunto vacío , cuya función generadora es 1 ( x ) = 1. De ello se deduce que la suma de las dos especies E  =  1  +  E ⁺ : en palabras, "un conjunto es vacío o no vacío". Ecuaciones como ésta pueden leerse como referencias a una única estructura, así como a toda la colección de estructuras.

Multiplicación

La multiplicación de especies es un poco más complicada. Es posible tomar como definición el producto cartesiano de conjuntos, pero la interpretación combinatoria de esto no es del todo correcta (véase más adelante el uso de este tipo de producto). En lugar de juntar dos estructuras no relacionadas en el mismo conjunto, el operador de multiplicación utiliza la idea de dividir el conjunto en dos componentes, construyendo una estructura F en uno y una estructura G en el otro. ^[7]

${\displaystyle (F\cdot G)[A]=\sum _{A=B+C}F[B]\times G[C].}$

Se trata de una unión disjunta sobre todas las particiones binarias posibles de  A. Es sencillo demostrar que la multiplicación es asociativa y conmutativa ( salvo isomorfismo ), y distributiva sobre la suma. En cuanto a la serie generadora, ( F  ·  G )( x ) =  F ( x ) G ( x ).

El diagrama siguiente muestra una posible estructura ( F  ·  G ) en un conjunto con cinco elementos. La estructura F (roja) toma 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 una manera diferente. El conjunto ( F  ·  G )[ A ], donde A es el conjunto base, es la unión disjunta de todas esas estructuras.

La adición y multiplicación de especies son la expresión más completa de las reglas de suma y producto del conteo. ^{[ cita requerida ]}

Composición

La composición , también llamada sustitución, es más complicada. La idea básica es reemplazar componentes de F con estructuras G , formando ( F  ∘  G ). ^[8] Al igual que con la multiplicación, esto se hace dividiendo el conjunto de entrada A ; los subconjuntos disjuntos se dan a G para formar estructuras G , y el conjunto de subconjuntos se da a F , para formar la estructura F que une las estructuras G . Es necesario que G asigne el conjunto vacío a sí mismo para que la composición funcione. La definición formal es:

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

Aquí, P es la especie de particiones, por lo que P [ A ] es el conjunto de todas las particiones de A . Esta definición dice que un elemento de ( F  ∘  G )[ A ] está formado por una estructura F en alguna partición de A y una estructura G en cada componente de la partición. La serie generadora es . ${\displaystyle (F\circ G)(x)=F(G(x))}$

A continuación se muestra una de esas estructuras. 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, definamos X como la especie "singleton" cuya serie generadora es X ( x ) =  x . Luego, la especie Ar de árboles con raíz (del francés " arborescence ") se define recursivamente por Ar  =  X  ·  E ( Ar ). Esta ecuación dice que un árbol consiste en una sola raíz y un conjunto de (sub)árboles. La recursión no necesita un caso base explícito: solo genera árboles en el contexto de ser aplicada a algún conjunto finito. Una forma de pensar en esto es que el funtor Ar se está aplicando 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 no hay más elementos para dar a E . Esto muestra que las descripciones algebraicas de las especies son bastante diferentes de las especificaciones de tipo en lenguajes de programación como Haskell .

De la misma manera, la especie P puede caracterizarse como P  =  E ( E ⁺ ): "una partición es un conjunto disjunto de conjuntos no vacíos (que utiliza todos los elementos del conjunto de entrada)". La serie generadora exponencial para P es , que es la serie para los números de Bell . ${\displaystyle P(x)=e^{(e^{x}-1)}}$

Diferenciación

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

Formalmente, ^[9]

${\displaystyle (F')[A]=F[A\uplus \{\star \}],}$

¿Dónde está algún nuevo elemento distinguido que no está presente en ? ${\displaystyle \star }$ ${\displaystyle A}$

Para diferenciar las series exponenciales asociadas, la secuencia de coeficientes debe desplazarse un lugar hacia la "izquierda" (perdiendo el primer término). Esto sugiere una definición para las especies: F' [ A ] =  F [ A  + {*}], donde {*} es un conjunto unitario y "+" es una unión disjunta. Las partes más avanzadas de la teoría de las especies utilizan ampliamente la diferenciación 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. Al eliminar un elemento de una lista, esta se divide en dos partes (posiblemente vacías); en símbolos, esto 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 NG de Bruijn, publicada en 1964.

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

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

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

Operaciones posteriores

Existe una variedad de otras manipulaciones que pueden realizarse sobre las especies. Estas son necesarias para expresar estructuras más complejas, como grafos dirigidos o bigrafos .

El apuntamiento selecciona un solo elemento en una estructura. ^[10] Dada una especie F , la especie apuntada correspondiente F ^• se define por F ^• [ A ] = A × F [ A ]. Por lo tanto, cada F ^• -estructura es una F -estructura con un elemento distinguido. El apuntamiento está relacionado con la diferenciación por la relación F ^• = X · F' , por lo que F ^• ( x ) = x F' ( x ). La especie de conjuntos apuntados , E ^• , es particularmente importante como un bloque de construcción para muchas de las construcciones más complejas.

El producto cartesiano de dos especies ^{[ cita requerida ]} es una especie que puede construir dos estructuras en el mismo conjunto al mismo tiempo. Es diferente del operador de multiplicación ordinario en que todos los elementos del conjunto base son compartidos entre las dos estructuras. Una ( F × G )-estructura puede verse como una superposición de una F -estructura y una G -estructura. Los bigrafos podrían describirse como la superposición de un grafo y un conjunto de árboles: cada nodo del bigrafo 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 Hadamard o coeficiente a coeficiente de F ( x ) y G ( x ).

Se puede considerar que la especie E ^• × E ^• realiza dos selecciones independientes del conjunto base. Los dos puntos podrían coincidir, a diferencia de X · X · E , donde se ven obligados a ser diferentes.

Como funtores, las especies F y G pueden combinarse por composición funtorial : ^{[ cita requerida ]} (se utiliza el símbolo de caja, porque el círculo ya se utiliza para la sustitución). Esto construye una F -estructura en el conjunto de todas las G -estructuras en el conjunto A . Por ejemplo, si F es el funtor que eleva un conjunto a su conjunto potencia, una estructura de la especie compuesta es algún subconjunto de las G -estructuras en A . Si ahora tomamos G como E ^• × E ^• de arriba, obtenemos la especie de grafos dirigidos, con bucles propios permitidos. (Un grafo dirigido es un conjunto de aristas, y las aristas son pares de nodos: por lo que un grafo es un subconjunto del conjunto de pares de elementos del conjunto de nodos A .) Otras familias de grafos, así como muchas otras estructuras, pueden definirse de esta manera. ${\displaystyle (F\,\Box \,G)[A]=F[G[A]]}$

Software

Las operaciones con especies son soportadas por SageMath ^[11] y, usando un paquete especial, también por Haskell . ^{[12] [13]}

Variantes

• Una especie en k tipos es un funtor . Aquí, las estructuras producidas pueden tener elementos extraídos de distintas fuentes. ^{[ cita requerida ]} ${\displaystyle {\mathcal {B}}^{k}\rightarrow {\mathcal {B}}}$
• Un funtor para , la categoría de conjuntos ponderados R para R un anillo de series de potencias , es una especie ponderada . ^{[ cita requerida ]} ${\displaystyle {\mathcal {B}}_{R}}$

Si se reemplaza “conjuntos finitos con biyecciones” por “espacios vectoriales finitos con transformaciones lineales”, entonces se obtiene la noción de functor polinomial (después de imponer alguna condición de finitud). ^{[ cita requerida ]}

Véase también

• Contenedor (teoría de tipos)

Notas

1. Joyal prefiere escribir para , el valor de F en A . ${\displaystyle F[A]}$ ${\displaystyle F(A)}$
2. Si es una biyección, entonces es una biyección y por lo tanto tienen la misma cardinalidad. ${\displaystyle u:A\to B}$ ${\displaystyle F[u]:F[A]\to F[B]}$ ${\displaystyle F[A],F[B]}$

1. Secuencia simétrica en el laboratorio n
2. Joyal 1981, § 1.1. Definición 1.
3. Federico G. Lastaria, Una invitación a las especies combinatorias. (2002)
4. Joyal 1981, § 1.1. Ejemplo 3.
5. Joyal 1981, § 1.1.1.
6. Joyal 1981, § 2.1.
7. Joyal 1981, § 2.1. Definición 5
8. Joyal 1981, § 2.2. Definición 7
9. Joyal 1981, § 2.3. Definición 8
10. Flajolet, Philippe ; Sedgewick, Robert (2009). Combinatoria analítica .
11. Documentación sabia sobre especies combinatorias.
12. Especies de paquetes Haskell.
13. Brent A., Yorgey (2010). "Especies, funtores y tipos, ¡ay Dios mío!". Actas del tercer simposio de la ACM Haskell sobre Haskell - Haskell '10 . ACM. pp. 147–158. CiteSeerX 10.1.1.165.6421 . doi :10.1145/1863523.1863542. ISBN  978-1-4503-0252-4. Número de identificación del sujeto  511418.

Referencias

• Joyal, André (octubre de 1981). "Una teoría combinatoria de series formales". Avances en Matemáticas . 42 (1): 1–82. doi :10.1016/0001-8708(81)90052-9.
• Bruijn, de, NG (1964). La teoría del conteo de Pólya. En EF Beckenbach (Ed.), Matemáticas combinatorias aplicadas (pp. 144-184)
• Labelle, Jacques. Quelques espèces sur les ensembles de petite cardinalité. , Ana. Carolina del Sur. Matemáticas. Québec 9.1 (1985): 31-58.
• Labelle, J.; Yeh, YN (1989). "La relación entre los anillos de Burnside y las especies combinatorias". Journal of Combinatorial Theory . Serie A. 50 (2): 269–284. doi : 10.1016/0097-3165(89)90019-8 .
• Yves Chiricota, Clasificación de especies moleculares de grado 6 y 7 , Ann. Ciencia. Matemáticas. Québec 17 (1993), núm. 1, 11–37.
• 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 Archivado el 2 de octubre de 2006 en Wayback Machine , Cambridge University Press (1998).
• Kerber, Adalbert (1999), Acciones de grupos finitos aplicados, Algorithms and Combinatorics, 19 (2.ª ed.), Berlín, Nueva York: Springer-Verlag, ISBN 978-3-540-65941-9 , MR 1716962, OCLC 247593131 

Enlaces externos

• Weisstein, Eric W. "Especies". MathWorld .
• especies en el laboratorio n